Giáo trình Toán rời rạc - Lập trình máy tính

cây 
khung có độ dài nhỏ nhất. Cây khung nh• vậy đ•ợc gọi là cây khung nhỏ nhất 
của đồ thị. 
 Để giải quyết bài toán này ta đi tìm hiểu một số thuật toán sau: 
 2.1. Thuật toán Kruskal 
 ý t•ởng của thuật toán: Thuật toán Kruskal áp dụng cho đồ thị cài đặt bằng 
danh sách cạnh. 
 Tr•ớc hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của trọng 
số. Bắt đầu từ ET=, ở mỗi b•ớc ta sẽ lần l•ợt duyệt trong danh sách cạnh đã sắp 
xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn, để tìm ra cạnh mà việc bổ 
sung nó vào tập ET không tạo thành chu trình trong tập này. Thuật toán sẽ kết 
thúc khi ta thu đ•ợc tập ET gồm n 1 cạnh. 
 Thuật toán: 
 B•ớc 1: sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần 
 B•ớc 2: Thực hiện lặp 
 - Chọn cạnh có trọng số nhỏ nhất ch•a xét 
 - Nếu cạnh này không tạo thành chu trình với các cạnh đã chọn thì bổ 
xung cạnh này vào cây khung T 
 B•ớc 3: Lặp lại b•ớc 2 cho đến khi |T| = n- 1 
 Ví dụ 1: Thực hiện thuật toán Kruskal, tìm cây khung nhỏ nhất của đồ thị 
 20 
sau: v2 v4
 33 8 
 16 
 v1 18 9 v6 
 17 4 14 
 v3 v5 
 37 
 B1: Sắp xếp các cạnh theo thứ tự tăng dần: 
 v3v5 ;v4v6 ;v5v4 ;v5v6 ;v3v4 ;v3v1;v2v3;v2v4 ;v1v2 
 B2: Lặp 
 v3v5;v4v6;v4v5;v1v3;v2v3 
 B3: |T| = 5 = n-1 
 20 
 v2 v
 33 4 8 
 16 
 Cây khung thu đ•ợc: v1 18 9 v6 
 (đ•ờng kẻ đậm) 17 4 14 
 v3 v5 
Nhận xét: 
 - Việc kiểm tra cạnh đang xét có tạo thành chu trình hay không là t•ơng đối 
khó khăn 
 - Trong quá trình xây dựng cây khung T có thể không liên thông. 
 2.2. Thuật toán Prim 
 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị dày (đồ thị 
có số cạnh m n(n 1)/2). Trong tr•ờng hợp đó, thuật toán Prim tỏ ra hiệu quả 
hơn. Thuật toán Prim còn đ•ợc gọi là ph•ơng pháp lân cận gần nhất. 
 Thuật toán: 
 B•ớc 1: Xuất phát từ một đỉnh bất kỳ 
 B•ớc 2: Thực hiện lặp 
 - Tìm đỉnh ch•a chọn có khoảng cách nhỏ nhất với tập các đỉnh đã 
 chọn 
 - Giả sử e là cạnh t•ơng ứng với khoảng cách nhỏ nhất 
 - Bổ sung đỉnh v vào tập các đỉnh đã chọn 
 - Bổ sung cạnh e vào cây khung T 
 B•ớc 3: Tới khi |T| = n – 1 
 Void Prim(v); 
 { 
 VT = v ; T = ; 
 For ( u V \ VT) 
 { 
 d[v] = C[v,u]; 
 truoc[u]=v; 
 } 
 38 
 // thực hiện b•ớc lặp 
 Stop = false; 
 While (!stop ) 
 { 
 Tìm k V \ VT sao cho 
 D[k] = min( d[u]); 
 VT = VT + k; 
 T = T + e ; //với cạnh e = (k,truoc[k]) 
 If(| VT | = n ) 
 Stop = true; 
 Else 
 For( u V \ VT) 
 If(d[u] > C[u,k]); 
 { 
 d[u] = C[u,k]; 
 truoc[u]=k; 
 } 
 } 
 } 
 Ví dụ: Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm các 
 đỉnh A, B, C, D, E, F, H, I đ•ợc cho bởi ma trận trọng số sau 
 A B C D E F H I 
 A 15 16 19 23 20 32 18 
 B 15 33 13 34 19 20 12 
 C 16 33 13 29 21 20 19 
 D 19 13 13 22 30 21 11 
 E 23 34 29 22 34 23 21 
 F 20 19 21 30 34 17 18 
 H 32 20 20 21 23 17 14 
 I 18 12 19 11 21 18 14 
B•ớc lặp A B C D R F H I VT t 
 Khởi 
 tạo [A,15] [A,16] [A,19] [A,23] [A,20] [A,32] [A,18] A  
 1 [A,16] [B,13] [A,23] [B,19] [B,20] [B,12] A, B (A,B) 
 2 [A,16] [I,11] [I,21] [I,18] [I,14] A, B, I (A,B), (B,I) 
 3 [D,13] [I,21] [I,18] [I,14] A, B, I, D (A,B), (B,I), (I,D) 
 39 
B•ớc lặp A B C D R F H I VT t 
 4 [I,21] [I,18] [I,14] A, B, I, D, C (A,B), (B,I), (I,D), (D,C) 
 A, B, I, D, C, (A,B), (B,I), (I,D), 
 5 [I,21] [H,17] 
 H (D,C), (I,H) 
 A, B, I, D, C, (A,B), (B,I), (I,D), 
 6 [I,21] 
 H, F (D,C), (I,H), (H,F) 
 A, B, I, D, C, (A,B), (B,I), (I,D), 
 7 
 H, F, E (D,C), (I,H), (H,F), (I,E) 
 Vậy độ dài cây khung nhỏ nhất là: 
 15 + 12 + 11 + 13 + 14 + 17 + 21 = 103. 
 43. Đồ thị Euler và đồ thị Hamilton 
 3.1. Đồ thị Euler 
 3.1.1. Định nghĩa: Chu trình đơn trong đồ thị G đi qua tất cả các cạnh, mỗi 
 cạnh đúng một lần gọi là chu trình Euler. 
 Đ•ờng đi đơn trong G đi qua tất cả các cạnh, mỗi cạnh đúng một lần gọi là 
 đ•ờng đi Euler. 
 Đồ thị G đ•ợc gọi là đồ thị Euler nếu có chu trình Euler và gọi là đồ thị nửa 
 Euler nếu nó có đ•ờng đi Euler. 
 3.1.2. Định lý: Đồ thị vô h•ớng liên thông G là đồ thị Euler khi và chỉ khi 
 tất cả các đỉnh của G đề có bậc chẵn 
 Chứng minh: 
 Chiều thuận : Giả sử G là đồ thị Euler Trong G có chu trình Euler. 
 đỉnh v V. Ta đi tính bậc của v. 
 Vì G liên thông v thuộc một cạnh e nào đó. Coi v là đỉnh xuất phát của chu 
 trình Euler. Mỗi khi chu trình đi qua v thì bậc của v tăng lên 2 đơn vị (1 ứng với 
 xuất phát, 1 ứng với quay lại) Deg(v) _ Chẵn. 
 Chiều nghịch : Giả sử v V có deg(v) chẵn. Ta cần chứng minh G_Euler 
 - Chứng minh G có chu trình Euler 
 Vì G liên thông  v V deg(v)>0 
 Vì v V, deg(v)_chẵn deg(v) 2. 
 - Lấy đỉnh v tùy ý, xét đ•ờng đi 
 x v x1 x2 ... trong đó xi xi 2 vì deg(xi) 2 
 Theo Dirichlet tồn tại i, j sao cho xi = xj 
 đ•ờng đi là chu trình 
 3.1.3. Hệ quả: Đồ thị G là nửa Euler khi và chỉ khi G có không quá hai đỉnh 
 bậc lẻ. 
 40 
 Chứng minh: Nếu G là nửa Euler thì tồn tại một đ•ờng đi Euler trong G từ 
đỉnh u đến đỉnh v. Gọi G là đồ thị thu đ•ợc từ G bằng cách thêm vào cạnh (u,v). 
Khi đó G là đồ thị Euler nên mọi đỉnh trong G đều có bậc chẵn (kể cả u và v). Vì 
vậy u và v là hai đỉnh duy nhất trong G có bậc lẻ. 
 Đảo lại, nếu có đúng hai đỉnh bậc lẻ là u và v thì gọi G là đồ thị thu đ•ợc từ 
G bằng cách thêm vào cạnh (u,v). Khi đó mọi đỉnh của G đều có bậc chẵn hay G 
là đồ thị Euler. Bỏ cạnh (u,v) đã thêm vào ra khỏi chu trình Euler trong G ta có 
đ•ợc đ•ờng đi Euler từ u đến v trong G hay G là nửa Euler. 
 3.1.4. Thuật toán tìm một chu trình Euler 
Void Euler_Cycle 
{ 
 - Kiểm tra: 
 - G – liên thông 
 - Tất cả các dỉnh bậc chẵn 
 - Dùng ngăn xếp s 
 - Xuất phát từ một đỉnh u tùy ý 
 addStack(u,s); CE =  
 While( !isEmpty(s )) 
 { 
 x = removeStack(s); 
 if (ke(x) ) 
 { 
 y = 1 đỉnh ke(x); 
 addStack(y,s); 
 Ke(x) = ke(x) \ {y}; 
 Ke(y) = ke(y \ {x}; 
 } 
 Else 
 { 
 removeStack(S,x); 
 CE = CE + {x}; 
 } 
 } 
} 
 41 
 Ví dụ: áp dụng thuật toán trên cho đồ thị vô h•ớng với các đỉnh bậc chẵn 
d•ới đây. 
 Hình . Đồ thị vô h•ớng với các đỉnh bậc chẵn 
Ta nhận đ•ợc chu trình Euler là: [1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1]. 
 3.2. Đồ thị Hamilton 
 Năm 1857, nhà toỏn học người Ailen là Hamilton(1805-1865) đưa ra trũ 
chơi “đi vũng quanh thế giới” như sau: 
 Cho một hỡnh thập nhị diện đều (đa diện đều cú 12 mặt, 20 đỉnh và 30 
cạnh), mỗi đỉnh của hỡnh mang tờn một thành phố nổi tiếng, mỗi cạnh của hỡnh 
(nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phỏt từ một 
thành phố, hóy tỡm đường đi thăm tất cả cỏc thành phố khỏc, mỗi thành phố chỉ 
một lần, rồi trở về chỗ cũ. 
 Trũ chơi trờn dẫn tới việc khảo sỏt một lớp đồ thị đặc biệt, đú là đồ thị 
Hamilton. 
 3.2.1. Đường đi Hamilton: Trong đồ thị G = (V,E) đường đi qua tất cả cỏc 
đỉnh của đồ thị mỗi đỉnh đỳng một lần được gọi là đường đi Hamilton. 
 Vớ dụ: Đồ thị cú đường đi Hamilton là a b c d 
 a b 
 d c 
 Hỡnh 2.1. Đồ thị cú đường đi Hamilton, khụng cú chu trỡnh Hamilton 
 3.2.2. Chu trỡnh Hamilton. Chu trỡnh bắt đầu từ một đỉnh v nào đú qua tất 
cả cỏc đỉnh cũn lại mỗi đỉnh đỳng một lần rồi quay trở về v được gọi là chu trỡnh 
Hamilton. 
 3.2.3. Đồ thị Hamilton. Đồ thị G được gọi là đồ thị Hamilton nếu nú chứa 
chu trỡnh Hamilton và gọi là đồ thị nửa Hamilton nếu nú cú đường đi Hamilton. 
 42 
 Rừ ràng đồ thị Hamilton là nửa Hamilton, nhưng điều ngược lại khụng cũn 
đỳng. 
 Vớ dụ về đồ thị Hamilton: 
 Đồ thị Hamilton 
 Bài toỏn chu trỡnh Hamilton (HC) được phỏt biểu như sau: 
 Instance: Một đồ thị G = (V,E). 
 Question: G cú chu trỡnh Hamilton hay khụng? 
 Bài toỏn HC đó được Karp (1972, [15]) chứng minh là bài toỏn NP-C (NP-
đầy đủ), chớnh vỡ thế mà khụng tồn tại thuật toỏn đa thức xỏc định sự tồn tại của 
chu trỡnh Hamilton trong đồ thị cho trước. Cho đến nay chỳng ta vẫn chưa tỡm ra 
điều kiện cần và đủ để kiểm tra xem một đồ thị cho trước cú là Hamilton hay 
khụng, và vấn đề này vẫn cũn là một vấn đề mở. Hiện tại mới chỉ cú cỏc điều 
kiện đủ để một đồ thị là đồ thị Hamilton hay cú đường đi Hamilton. 
 3.2.4. Định lý: Giả sử G là đồ thị Hamilton. Khi đú: 
 a) Mọi đỉnh của đồ thị G phải cú bậc khụng nhỏ hơn 2 
 b) Nếu một đỉnh cú bậc bằng 2 thỡ hai cạnh của nú phải nằm trờn bất kỳ 
một chu trỡnh Hamilton của G 
 c) Nếu một đỉnh cú bậc lớn hơn 2 và hai cạnh liền kề của nú nằm trờn một 
chu trỡnh Hamilton thỡ cỏc cạnh cũn lại của nú khụng nằm trờn chu trỡnh 
Hamilton đú. 
 43 
 4. Bài tập 
 4.1. Có thể tìm đ•ợc một cây có 8 đỉnh và thoả điều kiện d•ới đây hay 
không? Nếu có, vẽ cây đó ra, nếu không, giải thích tại sao? 
 a) Mọi đỉnh đều có bậc 1. 
 b) Mọi đỉnh đều có bậc 2. 
 c) Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. 
 d) Có đỉnh bậc 7 và 7 đỉnh bậc 1. 
 4.2. Cho các đồ thị sau. 
 a. 
 a b c 
 d e f g 
 h i j 
 b. 
 a b 
 c d e 
 g 
 f 
 i j 
 h 
 k l 
 c. 
 42 
 a b 
 4 10 14 3 
 3 1 11 
 c d e f 
 5 20 9 
 15 
 7 
 g h 
 - Tìm cây khung nhỏ nhất của đồ thị theo thuật toán Kruskal 
 - Tìm cây khung nhỏ nhất của đồ thị theo thuật toán Prim. Mô tả bằng 
bảng giá trị? 
 44 
 4.3. Tìm cây khung nhỏ nhất bằng thuật toán Prim, mô tả bằng bảng giá trị 
của đồ thị gồm các đỉnh A, B, C, D, E, F, H, I đ•ợc cho bởi ma trận trọng số sau. 
 A B C D E F G H 
 A 16 15 23 19 18 32 20 
 B 16 13 33 24 20 19 11 
 15 13 13 29 21 20 19 
 C 
 D 23 33 13 22 30 21 12 
 E 19 24 29 22 34 23 21 
 F 18 20 21 30 34 17 14 
 G 32 19 20 21 23 17 18 
 H 20 11 19 12 21 14 18 
 4.4. Duyệt các cây sau đây lần l•ợt bằng các thuật toán DFS và BFS 
 a. b. 
 1 1 
 2 6 3 2 
 3 4 7 5 4 6 7 
 5 8 12 11 10 9 8 
 10 9 12 14 15 
 17 16 
 45 
 Ch•ơng 5: đ•ờng đI ngắn nhất 
 Mã ch•ơng: Mh12.5 
Giới thiệu: Giỳp người học xõy dựng đường đi, tỡm đường đi ngắn nhất trong 
đồ thị. 
Mục tiờu: 
 - Trỡnh bày được khỏi niệm về đường đi ngăn nhất; 
 - Tỡm được đường đi ngắn nhất trờn một đồ thị; 
 - Áp dụng được thuật toỏn Dikstra, Floyd tỡm đường đi ngắn nhất; 
 - Nghiờm tỳc trong học tập, đảm bảo an toàn cho người và trang thiết bị. 
Nội dung chớnh: 
 1. Các khái niệm mở đầu 
 Tr•ớc mỗi chuyến xuất hành, chúng ta th•ờng phải suy nghĩ và chọn ra cho 
mình một hành trình tiết kiệm nhất theo nghĩa tốn ít thời gian, tốn ít nhiên liệu 
hoặc tốn ít tiền nhất Lý thuyết Đồ thị sẽ giúp chúng ta tìm ra giải pháp đó. 
 Bài toán 1: Cho đồ thị G = (V, E) và hai đỉnh a, b. Tìm đ•ờng đi ngắn nhất 
(nếu có) đi từ đỉnh a đến đỉnh b trong đồ thị G. ý nghĩa thực tế: Bài toán này 
giúp chúng ta chọn các hành trình tiết kiệm nhất (quãng đ•ờng, thời gian, chi phí 
...) trong giao thông, lập lịch thi công các công trình một cách tối •u, xử lý trong 
truyền tin ... 
 Ví dụ 1 (Bài toán con sói, con dê và cái bắp cải): 
 Một con sói, một con dê và một cái bắp cải đang ở bờ sông. Ng•ời lái đò 
phải đ•a chúng sang sông. Nh•ng thuyền quá bé nên mỗi chuyến chỉ chở đ•ợc 
một hành khách thôi. Vì những lý do mà ai cũng biết, không thể bỏ mặc sói với 
dê hoặc dê với bắp cải mà không có ng•ời trông. Vậy ng•ời lái đò phải xử trí thế 
nào mà vẫn đ•a đ•ợc sói, dê và bắp cải sang bên kia sông. 
 Xây dựng đồ thị vô h•ớng với các đỉnh thể hiện các hành khách còn lại bên 
phía xuất phát tại mỗi thời điểm khác nhau. Cạnh nối hai đỉnh thể hiện một 
chuyến đò qua sông. 
 L•u ý: L _ ng•ời lái đò 
 S _ sói 
 D _ Dê 
 B _ Bắp cải 
 46 
 Hành trình qua sông của sói, dê và bắp cải 
Bài toán đ•a về việc tìm đ•ờng đi ngắn nhất từ đỉnh a đến đỉnh b trên đồ thị. 
Đ•ờng đi nh• thế đ•ợc chỉ ra bởi các mũi tên ở hình trên. 
 Định nghĩa: Đồ thị G đ•ợc gọi là đồ thị có trọng số nếu trên mỗi cạnh (i, j) 
của đồ thị đ•ợc gán một số nguyên không âm c(i,j). Nhãn c(i,j) trên cạnh (i,j) 
của đồ thị th•ờng biểu diễn chi phí thực tế để đi qua cạnh này. 
 Ta th•ờng ký hiệu đồ thị có trọng số là (G, c). Độ dài của đ•ờng đi trong đồ 
thị có trọng số bằng tổng các trọng số của các cạnh trên đ•ờng đi đó. 
 Bài toán: Cho đồ thị có trọng số (G, c) và hai đỉnh a, b thuộc G. Hãy tìm 
đ•ờng đi có trọng số bé nhất (nếu có) đi từ đỉnh a đến đỉnh b. Độ dài đ•ờng đi 
ngắn nhất từ đi đỉnh a đến đỉnh b còn đ•ợc gọi là khoảng cách từ đỉnh a đến 
đỉnh b trong đồ thị. Nếu không có đ•ờng đi từ a đến b thì đặt khoảng cách bằng 
. 
 2. Thuật toán Dijkstra 
 Năm 1959 E. W. Dijkstra đ•a ra một thuật toán rất hiệu quả để giải bài toán 
đ•ờng đi ngắn nhất. 
Thuật toán thực hiện việc gán và giảm giá trị của nhãn l(i) tại mỗi đỉnh I của đồ 
thị G nh• sau: 
 Thuật toán 4.2 (Tìm đ•ờng đi ngắn nhất): 
 1. Với đỉnh xuất phát a, gán nhãn l(a) := 0. 
 2. Nếu có cạnh (i,j) mà đỉnh i đã đ•ợc gán nhãn và đỉnh j ch•a đ•ợc gán 
 nhãn hoặc đỉnh j đã đ•ợc gán nhãn nh•ng l(i) + c(i,j) < l(j) thì giảm nhãn 
 l(j) := l(i) + c(i,j). 
 3. Lặp lại b•ớc 2. cho đến khi không gán hoặc giảm nhãn đ•ợc nữa. 
Void Dijkstra(a) ; 
 { 
 for (j V ) 
 { 
 L[j] := C[a, j] ; Truoc[j] := a; 
 47 
 } 
 T := V \ {a} ; 
 while ( T  ) 
 { 
 chọn đỉnh i T mà L[i] = min(L[j] sao cho j T); 
 T := T \ i ; 
 for ( j T ) 
 if ( L[j] > L[i] + C[i, j] ) 
 { 
 L[j] := L[i] + C[i, j] ; 
 Truoc[j] := i ; 
 } 
 } 
 } 
 Biến mảng Truoc dùng để khôi phục đ•ờng đi. 
 Ví dụ: Tìm khoảng cách d(a,v) từ a đến mọi đỉnh v của đồ thị và tìm đ•ờng 
đi ngắn nhất từ a đến v cho trong đồ thị G sau. 
 4 6
 b c d 
 1 1 2 2 
 2 2 
 3 4 3 
 a e g h 3 
 5 1
 2 3 
 3 
 n m k 
 6 3 
 Theo thuật toán Dijkstra ta có đ•ờng đi ngắn nhất từ đỉnh a tới tất cả các 
đỉnh nh• sơ đồ sau: 
 48 
 3. Thuật toán Floyd 
 Cho G=(V,E) là một đồ thị có h•ớng, có trọng số. Để tìm đ•ờng đi ngắn 
nhất giữa mọi cặp đỉnh của G, ta có thể áp dụng thuật toán Dijkstra nhiều lần 
hoặc áp dụng thuật toán Floyd đ•ợc trình bày d•ới đây. 
 Giả sử V={v1, v2, ..., vn} và có ma trận trọng số là W  W0. Thuật toán 
Floyd xây dựng dãy các ma trận vuông cấp n là Wk (0 k n) nh• sau: 
private Xác định Wn 
{ 
 for (i = 1;i<=n; i++) 
 for (j = 1;j<=n; j++) 
 W[i,j] := m(vi,vj) ; //W[i,j] là phần tử dòng i cột j của ma trận W0 
 for (k = 1;k<=n; k++) 
 if (W[i,k] +W[k,j] < W[i,j]) 
 W[i,j] := W[i,k] +W[k,j]; 
 //W[i,j] là phần tử dòng i cột j của ma trận Wk 
} 
 49 
 4. Bài tập 
 4.1. Dùng thuật toán Dijkstra tìm đ•ờng đi ngắn nhất từ đỉnh a đến các đỉnh 
khác trong đồ thị sau: 
 4 c 2 
 2 d 
 b 3 7 
 12 
 k e 
 5 4 
 4 1 3 
 5 
 2 h 7 
 11 
 a g 
 4.2. Dùng thuật toán Dijkstra tìm đ•ờng đi ngắn nhất từ đỉnh a đến các đỉnh 
khác trong đồ thị sau: 
 4 
 b f 
 1 
 1 10 2 5 
 4 
 10 c g 2 
 1 
 a 6 4 5 8 k 
 3 
 3 d h 5 
 2 6 3 
 8 
 e i 
 4.3. Cho đồ thị có trọng số nh• hình d•ới đây. Hãy tìm đ•ờng đi ngắn nhất 
từ đỉnh A đến đỉnh N. 
 7 3 8 3 
 A B C D E 
 4 2 2 6 2 2 
 3 5 
 2 3 
 1 F 4 G H 2 I 
 3 5 4 2 
 2 4 3 3 
 J K L M N 
 2 9 5 7 
 50 
 4.4. Tìm đ•ờng đi ngắn nhất từ B đến các đỉnh khác của đồ thị có ma trận 
trọng số sau: 
 A B C D E F G 
 A 3 6 
 B 3 2 4 
 C 6 2 1 4 2 
 D 4 1 2 4 
 E 4 2 2 1 
 F 2 2 4 
 G 4 1 4 
 51