TRƯỜNG ðẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA CÔNG NGHỆ THÔNG TIN
GIÁO TRÌNH
HỌC PHẦN TOÁN RỜI RẠC 2 Trình ñộ ñào tạo
Hệ ñào tạo
:
:
ðại học
Chính quy / lien thông
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Danh mục các hình vẽ ..........................................................................................................4
Bài 1 Các khái niệm cơ bản của Lý thuyết ñồ thị. ..........................................................6
1.1 ðịnh nghĩa cơ bản về ñồ thị........................................................................................6
1.2 ðường ñi. chu trình. ðồ thị liên thông........................................................................9
1.3. Phân loại ñồ thị ........................................................................................................12
1.3.1. ðồ thị vô hướng liên thông ...............................................................................12
1.3.2. ðồ thị có hướng liên thông ...............................................................................14
1.4. Một số loại ñồ thị ñặc biệt .......................................................................................15
Bài 2 Biểu diễn ñồ thị trên máy tính .............................................................................20
2.1. Một số phương pháp biểu diễn ñồ thị trên máy tính................................................20
2.2.1. Ma trận kề. Ma trận trọng số............................................................................20
2.2.2. Danh sách cạnh (cung)......................................................................................22
2.2.3. Danh sách kề .....................................................................................................23
Bài 3 ðồ thị Euler..........................................................................................................28
3.1. ðịnh nghĩa................................................................................................................28
3.2. Các ví dụ ..................................................................................................................29
3.3. ðịnh lý Euler và thuật toán Flor ..............................................................................29
Bài 4 ðồ thị Hamilton ...................................................................................................33
4.1 ðịnh nghĩa.................................................................................................................34
4.2. ðịnh lý và thuật toán liệt kê tất cả các chu trình Hamilton. ....................................35
Bài 5 Thảo luận cài ñặt ñồ thị, các thuật toán liệt kê chu trình Euler và Hamilton. Thảo
luận về bài tập lớn...............................................................................................................38
5.1. Cài ñặt biểu diễn ñồ thị trên máy tính......................................................................38
5.2. Cài ñặt thuật toán liệt kê chu trình Euler .................................................................38
5.3. Cài ñặt thuật toán liệt kê chu trình Hamilton...........................................................40
Bài 6 Thuật toán tìm kiếm trên ñồ thị và ứng dụng ......................................................41
6.1. Duyệt ñồ thị theo chiều rộng (BFS).........................................................................41
6.2. Duyệt ñồ thị theo chiều sâu (DFS) ..........................................................................44
Bài 7 Cây và cây khung.................................................................................................45
7.1. Cây và cây khung.....................................................................................................45
13.1.1 Các bài toán liên quan tới bậc của ñồ thị .........................................................91
13.1.2 Các bài toán liên quan ñến tính liên thông của ñồ thị......................................93
13.1.3 Các bài toán liên quan tới chu trình .................................................................94
13.1.4 Các bài toán có liên quan ñến ñường ñi và chu trình Hamilton......................96
13.1.5 Các bài toán liên quan ñến ñồ thị tô màu.......................................................100
13.1.6 Bài toán về cây...............................................................................................110
13.1.7 Bài toán về ghép cặp ......................................................................................111
13.1.8 ðồ thị Euler....................................................................................................112
13.1.9 Các bài toán có tính tổng hợp ........................................................................112
13.2 Sự liên hệ giữa các tập ñặc biệt trên ñồ thị với các bài toán trên bàn cờ..............115
13.3 Duyệt rộng trên mảng hai chiều............................................................................119
Bài 14 Một số ứng dụng trong ñồ thị ............................................................................126
14.1 Bài toán ñám cưới vùng quê ................................................................................126
14.2 Bài toán về hệ thống ñại diện chung.....................................................................127
14.3 Bài toán tối ưu rời rạc ...........................................................................................128
Bài toán phân nhóm sinh hoạt...................................................................................128
Bài toán lập lịch cho hội nghị ...................................................................................129
14.4 Một số bài toán liên quan ñến việc tổ chức mạng vận chuyển bưu chính............129
Mô hình ñịnh tuyến mạng ñường thư cấp 1..............................................................130
Bài toán lập kế hoạch vận chuyển bưu gửi ...............................................................130
Mô hình mạng ñường thư trong thành phố ...............................................................133
TÀI LIỆU THAM KHẢO ................................................................................................136
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
4
Danh mục các hình vẽ
Hình 1.1 Sơ ñồ mạng máy tính.............................................................................................6
2
, Q
3
. ..........................................................................16
Hình 1.14 ðồ thị hai phía. ..................................................................................................17
Hình 1.15 ðồ thị K
4
là ñồ thị phẳng...................................................................................18
Hình 1.16 Các miền tương ứng với biểu diễn phẳng của ñồ thị.........................................18
Hình 2.1 ðồ thị vô hướng G và ðồ thị có hướng G
1
..........................................................21
Hình 3.1 Mô hình 7 cây cầu ở Konigsberg ........................................................................28
Hình 3.2 ðồ thị G
1
, G
2
, G
3
. ................................................................................................29
Hình 3.3 ðồ thị H
1
, H
2
, H
3
. ................................................................................................29
Hình 3.4 Minh hoạ cho chứng minh ðịnh lý 3.1................................................................31
Hình 4.1 Du lịch 20 thành phố ...........................................................................................33
Hình 4.2 ðồ thị Hamilton G
Hình 12.4 Ví dụ tồi tệ ñối với thuật toán Ford_Fulkerson. ................................................89
Hình 12.5 Tăng luồng dọc theo ñường tăng.......................................................................90
Hình 13.1 Kết quả thi ñấu của 5 ñội bóng chuyền A, B, C, B, E.......................................96
Hình 13.2 Sơ ñồ nhà của 8 học sinh...................................................................................97
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
5
Hình 13.3 10 thành phố ......................................................................................................98
Hình 13.4 bố trí lịch thi cho học sinh THPT với 7 môn thi trong 7 ngày ..........................99
Hình 13.5 Vị trí nhà ở và ñường nối giữa các nhà của 9 học sinh ...................................100
Hình 13.6 Bản ñồ có 6 miền.............................................................................................101
Hình 13.7 Lập lịch thi 7 môn............................................................................................104
Hình 13.8 Tô màu cho ñồ thị lịch thi................................................................................105
Hình 13.9 Phân chia kênh truyền hình .............................................................................107
Hình 13.10 Tô màu cho ñồ thị phân chia kênh truyền hình ............................................107
Hình 13.11 Thanh ghi chỉ số trong CPU ..........................................................................109
Hình 13.12 Tô màu cho ñô thị thanh ghi chỉ số ...............................................................110
Hình 13.13 Kết quả xếp hạng của các ñội........................................................................111
Hình 13.14 Tuyển chọn biên dịch viên ............................................................................114
Hình 13.15 Quy tắc ñi của quân mã .................................................................................116
Hình 13.16 Quy tắc ñi của quân mã trên bàn cờ 4 × 4 .....................................................116
Hình 13.17 Quy tắc ñi của quân tượng trên bàn cờ 4 × 4 ................................................117
Hình 13.18 Quy tắc ñi của quân xe trên bàn cờ 4 × 4 .....................................................117
Hình 13.19 Quy tắc ñi của quân hậu trên bàn cờ 4 × 4 ....................................................118
Hình 13.20 Hướng di chuyển của robot ...........................................................................120
Hình 14.1 Mạng tương ứng với bài toán ñám cưới vùng quê. .........................................127
Giáo trình
Hình 1.2 Sơ ñồ mạng máy tính với ña kênh thoại.
ðịnh nghĩa 1.2
ða ñồ thị vô hướng G= (V, E) bao gồm V là tập các ñỉnh, và E là tập các cặp không có
thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e
1
và e
2
ñược gọi là
cạnh lặp nếu chúng cùng tương ứng với một cặp ñỉnh.
Hình 1.3 Sơ ñồ mạng máy tính với kênh thoại thông báo.
Rõ ràng mỗi ñơn ñồ thị ñều là ña ñồ thị, nhưng không phải ña ñồ thị nào cũng là
ñơn ñồ thị, vì trong ña ñồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp ñỉnh nào
ñó.
Trong mạng máy tính có thể có những kênh thoại nối một náy nào ñó với chính nó
(chẳng hạn vời mục ñính thông báo). Mạng như vậy ñược cho trong hình 3. Khi ñó ña ñồ
thị không thể mô tả ñược mạng như vậy, bởi vì có những khuyên (cạnh nối một ñỉnh với
chính nó). Trong trường hợp nàychúng ta cần sử dụng ñến khái niệm giả ñồ thị vô hướng,
ñược ñịnh nghĩa như sau:
ðịnh nghĩa 1.3
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
8
Giả ñồ thị vô hướng G = (V, E) bao gồm V là tập các ñỉnh và E là tập các cặp không có
thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là cạnh. Cạnh e ñược
gọi là khuyên nếu nó có dạng e = (u, u).
hướng G = (V, E) là dãy x
0
, x
1
,…, x
n-1
, x
n
trong ñó u = x
0
, v = x
n
, (x
i
, x
i+1
)
∈
E, i = 0, 1, 2,…, n-1.
ðường ñi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:
(x
0
, x
1
), (x
1
, x
2
), …, (x
n-1
, (xi, x
i+1
)
∈
E, i = 0, 1, 2,…, n-1.
ðường ñi nói trên còn có thể biểu diễn dưới dạng dãy các cung:
(x
0
, x
1
), (x
1
, x
2
), …, (x
n-1
, x
n
)
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
10
ðỉnh u gọi là ñỉnh ñầu, còn ñỉnh v gọi là ñỉnh cuối của ñường ñi. ðường ñi có ñỉnh ñầu
trùng với ñỉnh cuối (tức là u = v) ñược gọi là chu trình. ðường ñi hay chu trình ñược gọi
là ñơn nếu như không có cạnh nào bị lặp lại.
Ví dụ 1.2 Trên ñồ thị có hướng cho trong Hình 1.5: a, d, c, f, e là ñường ñi ñơn ñộ dài 4.
Còn d, e, c, a không là ñường ñi, do (c,e) không phải là cạnh của ñồ thị. Dãy b, c, f, e, b là
chu trình ñộ dài 4. ðường ñi a, b, e, d, a, b có ñộ dài là 5 không phải là ñường ñi ñơn, do
1
, H
2
, H
3
.
Trong mạng máy tính có thể có những máy (Những kênh nối) mà sự hỏng hóc của
nó sẽ ảnh hưởng ñến việc trao ñổi thông tin trong mạng. Các khái niệm tương ứng với
tình huống này ñược ñưa ra trong ñịnh nghĩa sau.
ðịnh nghĩa 1.10
ðỉnh v ñược gọi là ñỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó
khỏi ñồ thị làm tăng số thành phần liên thông của ñồ thị. Cạnh e ñược gọi là cầu nếu việc
loại bỏ nó khỏi ñồ thị làm tăng số thành phần liên thông của ñồ thị.
Ví dụ 1.5 Trong ñồ thị G ở hình2, ñỉnh d và e là ñỉnh rẽ nhánh, còn các cạnh (d, g) và (e,
f) là cầu.
ðối với ñồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có xét
ñến hướng trên các cung hay không.
ðịnh nghĩa 1.11
ðồ thị có hướng G = (V, A) ñược gọi là liên thông mạnh nếu luôn tìm ñược ñường ñi giữa
hai ñỉnh bất kỳ của nó.
ðịnh nghĩa 1.12
ðồ thị có hướng G = (V, A) ñược gọi là liên thông yếu nếu ñồ thị vô hướng tương ứng với
nó là vô hướng liên thông.
Rõ ràng nếu ñồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng ñiều
ngược lại là không luôn ñúng, như chỉ ra trong ví dụn dưới ñây.
Ví dụ 1.6 Trong Hình 1.7 ñồ thị G là liên thông mạnh, còn H là liên thông yếu nhưng
không là liên thông mạnh.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
13
ðịnh nghĩa 1.13
Hai ñỉnh u và v của ñồ thị vô hướng G ñược gọi là kề nhau nếu (u,v) là cạnh của ñồ thị G.
Nếu e = (u, v) là cạnh của ñồ thị ta nói cạnh này là liên thuộc với hai ñỉnh u và v, hoặc
cũng nói là nối ñỉnh u và ñỉnh v, ñồng thời các ñỉnh u và v sẽ ñược gọi là các ñỉnh ñầu
của cạnh (u, v).
ðể có thể biết có vao nhiêu cạnh liên thuộc với một ñỉnh, ta ñưa vào ñịnh nghĩa sau
ðịnh nghĩa 1.14
Ta gọi bậc của ñỉnh v trong ñồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là
deg(v).
Hình 1.8 ðồ thị vô hướng.
Ví dụ 1.7 Xét ñồ thị cho trong hình 1.9, ta có
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0
ðỉnh bậc 0 gọi là ñỉnh cô lập. ðỉnh bậc 1 ñược gọi là ñỉnh treo. Trong ví dụ trên
ñỉnh g là ñỉnh cô lập, a và d là các ñỉnh treo. Bậc của ñỉnh có tính chất sau:
ðịnh lý 1.2 Giả sử G = (V, E) là ñồ thị vô hướng với m cạnh. Khi ñó tổng bậc của tất cả
các ñỉnh bằng hai lần số cung.
Chứng minh. Rõ ràng mỗi cạnh e = (u, v) ñược tính một lần trong deg(u) và một lần
trong deg(v). Từ ñó suy ra tổng tất cả các bậc của các ñỉnh bằng hai lần số cạnh.
Ví dụ 1.8 ðồ thị với n ñỉnh có bậc là 6 có bao nhiêu cạnh?
Giải: Theo ñịnh lý 1.2 ta có 2m = 6n. Từ ñó suy ra tổng các cạnh của ñồ thị là 3n.
Hệ quả 1.3 Trong ñồ thị vô hướng, số ñỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số
chẵn.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
Ví dụ 1.9 Xét ñồ thị cho trong hình 1.10. Ta có
deg
-
(a)=1, deg
-
(b)=2, deg
-
(c)=2, deg
-
(d)=2, deg
-
(e) = 2.
deg
+
(a)=3, deg
+
(b)=1, deg
+
(c)=1, deg
+
(d)=2, deg
+
(e)=2.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
15
Do mỗi cung (u, v) sẽ ñược tính một lần trong bán bậc vào của ñỉnh v và một lần
trong bán bậc ra của ñỉnh u nên ta có:
ðồ thị ñầy ñủ K
n
có tất cả n(n-1)/2 cạnh, nó là ñơn ñồ thị có nhiều cạnh nhất.
ðồ thị vòng.
ðồ thị vòng C
n
, n≥3. gồm n ñỉnh v
1
, v
2
,. . . .v
n
và các cạnh (v
1
,v
2
), (v
2
,v
3
) . . . (v
n-1
,v
n
),
(v
n
,v
1
).
ñỉnh của C
n
(xem hình 2.3).
Hình 1.12 ðồ thị bánh xe W
3
, W
4
, W
5
, W
6
.
ðồ thị lập phương.
ðồ thị lập phương n ñỉnh Q
n
là ñồ thị với các ñỉnh biểu diễn 2
n
xâu nhị phân ñộ dài
n. Hai ñỉnh của nó gọi là kề nhau nếu như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit.
Hình 1.13 cho thấy Q
n
với n=1,2,3.
Hình 1.13 ðồ thị lập phương Q
1
, Q
2
, Q
3
ðồ thị ñược gọi là ñồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các
cạnh của nó không cắt nhau ngoài ở ñỉnh. Cách vẽ như vậy sẽ ñược gọi là biểu diễn phẳng
của ñồ thị.
Ví dụ ñồ thị K
4
là phẳng, vì có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không
cắt nhau ngoài ở ñỉnh (xem hình 2.6).
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
18
Hình 1.15 ðồ thị K
4
là ñồ thị phẳng.
Một ñiều ñáng lưu ý nếu ñồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với
các cạnh nối là các ñoạn thẳng không cắt nhau ngoài ở ñỉnh (ví dụ xem cách vẽ K
4
trong
hình 2.6).
ðể nhận biết xem một ñồ thị có phải là ñồ thị phẳng có thể sử dụng ñịnh lý
Kuratovski, mà ñể phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh
(u,v) của ñồ thị là việc loại bỏ cạnh này khỏi ñồ thị và thêm vào ñồ thị một ñỉnh mới w
cùng với hai cạnh (u,w), (w, u) . Hai ñồ thị G(V,E) và H=(W,F) ñược gọi là ñồng cấu nếu
chúng có thể thu ñược từ cùng một ñồ thị nào ñó nhờ phép chia cạnh.
ðịnh lý 1.5 (Kuratovski). ðồ thị là phẳng khi và chỉ khi nó không chứa ñồ thị con ñồng
cấu với K
3,3
hoặc K
Euler ñã chứng minh ñược rằng các cách biểu diễn phẳng khác nhau của một ñồ thị
ñều chia mặt phẳng ra thành cùng một số miền. ðể chứng minh ñiều ñó, Euler ñã tìm
ñược mối liên hệ giữa số miền, số ñỉnh của ñồ thị và số cạnh của ñồ thị phẳng sau ñây.
ðịnh lý 1.6 (Công thức Euler). Giả sử G là ñồ thị phẳng liên thông với n ñỉnh, m cạnh.
Gọi r là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi ñó
r = m-n + 2
Có thể chứng minh ñịnh lý bằng qui nạp. Xét Ví dụ minh hoạ cho áp dụng công
thức Euler.
Ví dụ 1.10 Cho G là ñồ thị phẳng liên thông với 20 ñỉnh, mỗi ñỉnh ñều có bậc là 3. Hỏi
mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của ñồ thị G?
Giải. Do mỗi ñỉnh của ñồ thị ñều có bậc là 3, nên tổng bậc của các ñỉnh là 3x20=60. Từ
ñó suy ra số cạnh của ñồ thị m=60/20=30. Vì vậy, theo công thức Euler, số miền cần tìm
là
r = 30-20+2=12.
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
20
Bài 2 Biểu diễn ñồ thị trên máy tính
2.1. Một số phương pháp biểu diễn ñồ thị trên máy tính
ðể lưu trữ ñồ thị và thực hiện các thuật toán khác nhau với ñồ thị trên máy tính cần
phải tìm những cấu trúc dữ liệu thích hợp ñể mô tả ñồ thị. Việc chọn cấu trúc dữ liệu nào
ñể biểu diễn ñồ thị có tác ñộng rất lớn ñến hiệu quả của thuật toán. Vì vậy, việc chọn lựa
cấu trúc dữ liệu ñể biểu diễn ñồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và
thuật toán cụ thể). Trong mục này chúng ta sẽ xét một số phương pháp cơ bản ñược sử
dụng ñể biểu diễn ñồ thị trên máy tính, ñồng thời cũng phân tích một cách ngắn gọn
những ưu ñiểm cũng như những nhược ñiểm của chúng.
2.2.1. Ma trận kề. Ma trận trọng số
Trang
21
Hình 2.1 ðồ thị vô hướng G và ðồ thị có hướng G
1
.
Các tính chất của ma trận kề:
1) Rõ ràng ma trận kề của ñồ thị vô hướng là ma trận ñối xứng, tức là
a[i,j]=a[j,i], i,j =1,2,. . .,n. Ngược lại, mỗi (0,1)-ma trận ñối xứng cấp n sẽ tương ứng,
chính xác ñến cách ñánh số ñỉnh (còn nói là: chính xác ñến ñẳng cấu), với một ñơn ñồ thị
vô hướng n ñỉnh.
2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của ñỉnh i (ñỉnh j).
3) nếu ký hiệu a
ịj
p
, i,j=1, 2,. . . ,n là phần tử của ma trận A
p
=A.A. . .A p thừa số. Khi ñó
a
ịj
p
, i,j=1, 2,. . . ,n cho ta số ñường ñi khác nhau từ ñỉnh i ñến ñỉnh j qua p-1 ñỉnh trung
gian.
Ma trận kề của ñồ thị có hướng ñược ñịnh nghĩa một cách hoàn toàn tương tự.
Ví dụ 2.2 ðồ thị có hướng G
1
cho trong Hình 2.1 có ma trận kề là ma trận sau:
1 2 3 4 5 6
1 0 1 1 0 0 0
2
ñơn vị bộ nhớ ñể lưu trữ ma trận
kề của nó.
2.2.2. Danh sách cạnh (cung)
Trong trường hợp ñồ thị thưa (ñồ thị có số cạnh m thoả mãn bất dẳng thức: m <
6n) người ta thường dùng cách biểu diễn ñồ thị dưới dạng danh sách cạnh.
Trong cách biểu diễn ñồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ danh
sách tất cả các cạnh (cung) của ñồ thị vô hướng (có hướng). Một cạnh (cung) e = (x,y) của
ñồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. như vậy, ñể lưu trữ ñồ thị ta cần sử dụng
2m ñơn vị bộ nhớ. Nhược ñiểm của cách biểu diễn này là ñể xác ñịnh những ñỉnh nào của
ñồ thị là kề với một ñỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua
danh sách tất cả các cạnh của ñồ thị).
Chú ý: Trong trường hợp ñồ thị có trọng số ta cần thêm m ñơn vị bộ nhớ ñể lưu trữ trọng
số của các cạnh.
Ví dụ 2.3 Danh sách cạnh (cung) của ñồ thị G (G
1
) cho trong Hình 2.1 là:
Dau Cuoi Dau Cuoi
1 2 1 2
Giáo trình
TOÁN RỜI RẠC 2 Bộ môn Công nghệ phần mềm - 2010
Trang
23
1 3 1 3
1 5 3 2
2 3 3 4
2 5 5 4
3 4 5 6
4 5 6 5
for u
∈
Ke(v) do
begin . . . end.
Có thể thay thế bởi cấu trúc lệnh cụ thể trên PASCAL như sau
For i:=Tro[v] to Tro[v+1]-1 do
Begin
U:=Ke[i];
. . . .
End;
Trong rất nhiều thuật toán làm việc với ñồ thị chúng ta thường xuyên phải thực
hiện các thao tác: Thêm hoặc bớt một số cạnh. Trong trường hợp này cấu trúc dữ liệu
dùng ở trên là không thuận tiện. Khi ñó nên chuyển sang sử dụng danh sách kề liên kết
(Linked Adjancency List) như mô tả trong chương trình nhập danh sách kề của ñồ thị từ
bàn phím và ñưa danh sách ñó ra màn hình sau ñây:
Program AdjList;
Const
maxV=100;
Type
link=^node;
Copyright: Tài liệu đại học ©