Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất - Nguyễn Đức Nghĩa

Chương 4 Bài toán cây khung nhỏ nhất  
The Minimum Spanning Tree Problem 
2 
Nội dung 
4.1. Cây và các tính chất cơ bản của cây 
4.2. Cây khung của đồ thị 
4.3. Xây dựng tập các chu trình cơ bản của đồ thị 
4.4. Bài toán cây khung nhỏ nhất 
3 
Cây và rừng (Tree and Forest) 
§Þnh nghÜa 1. Ta gäi c©y lµ ®å thÞ v« h­íng liªn th«ng kh«ng cã chu tr×nh. §å thÞ kh«ng cã chu tr×nh ®­îc gäi lµ rõng. 
Nh­ vËy, rõng lµ ®å thÞ mµ mçi thµnh phÇn liªn th«ng cña nã lµ mét c©y. 
T 1 
T 3 
Rừng F gồm 3 cây T 1 , T 2, , T 3 
T 2 
4 
VÍ DỤ 
G 1 , G 2 là cây 
G 3 , G 4 không là cây 
5 
Các tính chất cơ bản của cây 
Định lý 1. Giả sử T= ( V,E ) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương: 
 	 (1) T là liên thông và không chứa chu trình; 
	 (2) T không chứa chu trình và có n-1 cạnh; 
	 (3) T liên thông và có n-1 cạnh; 
	 (4) T liên thông và mỗi cạnh của nó đều là cầu; 
	 (5) Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn; 
	 (6) T không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta thu được đúng một chu trình. 
6 
Nội dung 
4.1. Cây và các tính chất cơ bản của cây 
4.2. Cây khung của đồ thị 
4.3. Xây dựng tập các chu trình cơ bản của đồ thị 
4.4. Bài toán cây khung nhỏ nhất 
7 
Cây khung của đồ thị 
Định nghĩa 2. Giả sử G= ( V,E ) là đồ thị v ô hướng li ê n th ô ng. C â y T= ( V,F ) với F  E được gọi là c â y khung của đồ thị G. 
a 
b 
e 
c 
d 
a 
b 
e 
c 
d 
a 
b 
e 
c 
d 
G 
Đồ thị G và 2 cây khung T 1 và T 2 của nó 
T 2 
T 1 
8 
Số lượng cây khung của đồ thị 
Định lý sau đây cho biết số lượng cây khung của đồ thị đầy đủ K n : 
Định lý 2 (Cayley). Số cây khung của đồ thị K n là n n-2 . 
a 
b 
c 
a 
b 
c 
b 
c 
a 
c 
a 
b 
K 3 
Ba cây khung của K 3 
Arthur Cayley 
(1821 – 1895) 
9 
Bài toán trong hoá học hữu cơ 
Biểu diễn cấu trúc phân tử: 
Mỗi đỉnh tương ứng với một nguy ê n tử 
Cạnh – thể hiện liên kết giữa các nguyên tử 
Bài to á n: Đếm số đồng ph â n của cacbua hydro no chứa một số nguy ê n tử c á cbon cho trước 
10 
C 
H 
H 
H 
H 
C 
H 
H 
H 
H 
C 
H 
H 
C 
H 
H 
H 
H 
C 
H 
H 
C 
H 
H 
C 
H 
H 
H 
H 
C 
H 
H 
C 
H 
H 
C 
H 
H 
methane 
ethane 
propane 
butane 
 saturated hydrocarbons C n H 2n+2 
11 
Nội dung 
4.1. Cây và các tính chất cơ bản của cây 
4.2. Cây khung của đồ thị 
4.3. Xây dựng tập các chu trình cơ bản của đồ thị 
4.4. Bài toán cây khung nhỏ nhất 
12 
Tập các chu trình cơ bản 
Gi¶ sö G = ( V, E ) lµ ®¬n ®å thÞ v« h­íng liªn th«ng, H =( V,T ) lµ c©y khung cña nã. C¸c c¹nh cña ®å thÞ thuéc c©y khung ta sÏ gäi lµ c¸c c¹nh trong, cßn c¸c c¹nh cßn l¹i sÏ gäi lµ c¹nh ngoµi. 
§Þnh nghÜa 3. NÕu thªm mét c¹nh ngoµi e E \ T vµo c©y khung H chóng ta sÏ thu ®­îc ®óng mét chu tr×nh trong H, ký hiÖu chu tr×nh nµy lµ C e . TËp c¸c chu tr×nh 
  = { C e : e E \ T } 
 ®­îc gäi lµ tËp c¸c chu tr×nh c¬ b¶n cña ®å thÞ G. 
13 
Tính chất 
Gi¶ sö A vµ B lµ hai tËp hîp, ta ®­a vµo phÐp to¸n sau 
 A  B = ( A  B ) \ ( A  B ). 
 TËp A  B ®­îc gäi lµ hiÖu ®èi xøng cña hai tËp A vµ B. 
Tªn gäi chu tr×nh c¬ b¶n g¾n liÒn víi sù kiÖn chØ ra trong ®Þnh lý sau ®©y: 
§Þnh lý 3. Gi¶ sö G= ( V,E ) lµ ®å thÞ v« h­íng liªn th«ng, H= ( V,T ) lµ c©y khung cña nã. Khi ®ã mäi chu tr×nh cña ®å thÞ G ®Òu cã thÓ biÓu diÔn nh­ lµ hiÖu ®èi xøng cña mét sè c¸c chu tr×nh c¬ b¶n. 
14 
Ý nghĩa ứng dụng 
Việc tìm tập các chu trình cơ bản giữ một vai trò quan trọng trong vấn đề giải tích mạng điện: 
Theo mỗi chu trình cơ bản của đồ thị tương ứng với mạng điện cần phân tích ta sẽ thiết lập được một phương trình tuyến tính theo định luật Kirchoff: Tổng hiệu điện thế dọc theo một mạch vòng là bằng không. 
Hệ thống phương trình tuyến tính thu được cho phép tính toán hiệu điện thế trên mọi đoạn đường dây của lưới điện. 
15 
Thuật toán xây dựng tập chu trình cơ bản 
Đầu vào: Đồ thị G =( V,E ) ®­îc m« t¶ b»ng danh s¸ch kÒ Ke( v ), v V . 
procedure Cycle(v); 
(* Tìm tập các chu trình cơ bản của thành phần liên thông chứa đỉnh v 
C¸c biÕn d, num, STACK, Index lµ toµn côc *) 
begin 
 d:=d+1; 
 STACK[d] := v; 
 num := num+1; 
 Index[v] := num; 
 for u Ke(v) do 
 if Index[u]=0 then Cycle(u) 
 else 
	 if (u STACK[d-1]) and (Index[v] > Index[u]) then 
 < Ghi nhËn chu tr×nh víi c¸c ®Ønh: 
 STACK[d], STACK[d-1], ... , STACK[c], víi STACK[c]=u >; 
 d := d-1; 
end; 
16 
Thuật toán xây dựng tập chu trình cơ bản 
(* Main Program *) 
BEGIN 
 for v V do Index[v] := 0; 
 num := 0; d := 0; 
 STACK[0] := 0; 
 for v V do 
 if Index[v] = 0 then Cycle(v); 
END. 
Độ phức tạp: O (| V |+| E |) 
17 
Nội dung 
4.1. Cây và các tính chất cơ bản của cây 
4.2. Cây khung của đồ thị 
4.3. Xây dựng tập các chu trình cơ bản của đồ thị 
4.4. Bài toán cây khung nhỏ nhất 
18 
BÀI TOÁN CÂY KHUNG NHỎ NHẤT 
Minimum Spanning Tree (MST) 
19 
Bài toán CKNN 
Bài toán: Cho đồ thị vô hướng liên thông G =( V,E ) với trọng số c ( e ), e E . Độ dài của cây khung là tổng trọng số trên các cạnh của nó. Cần tìm cây khung có độ dài nhỏ nhất. 
1 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
4 
1 
3 
4 
4 
5 
2 
Độ dài của cây khung là Tổng độ dài các cạnh: 14 
20 
Bài toán cây khung nhỏ nhất 
C ó thể ph á t biểu dưới dạng bài to á n tối ưu tổ hợp: 
 Tìm cực tiểu 
 c ( H ) =  c ( e ) min, 
 e T 
 với điều kiện H= ( V,T ) là c â y khung của G. 
Do số lượng c â y khung của G là rất lớn (xem định lý Cayley), n ê n kh ô ng thể giải nhờ duyệt toàn bộ 
21 
Ứng dụng thực tế: Mạng truyền thông  
C ô ng ty truyền th ô ng AT&T cần x â y dựng mạng truyền th ô ng kết nối n kh á ch hàng. Chi ph í thực hiện k ê nh nối i và j là c ij . Hỏi chi ph í nhỏ nhất để thực hiện việc kết nối tất cả c á c kh á ch hàng là bao nhi ê u? 
1 
6 
3 
7 
5 
8 
9 
4 
2 
10 
Giả thiết là: Chỉ có cách kết nối duy nhất là đặt kênh nối trực tiếp giữa hai nút. 
22 
Bµi to¸n x©y dùng hÖ thèng ®­êng s¾t 
Giả sử ta muốn xây dựng một hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi lại giữa hai thành phố bất kỳ đồng thời tổng chi phí xây dựng phải là nhỏ nhất. 
Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án xây dựng tối ưu phải là cây. 
Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các cạnh chính là chi phí xây dựng đường ray nối hai thành phố tương ứng 
Chó ý: Trong bµi to¸n nµy ta gi¶ thiÕt lµ kh«ng ®­îc x©y dùng tuyÕn ®­êng s¾t cã c¸c nhµ ga ph©n tuyÕn n»m ngoµi c¸c thµnh phè. 
23 
Sơ đồ chung của các giải thuật 
Generic-MST(G, c) 
 A = { } 
 // Bất biến: A là tập con các cạnh của CKNN nào đó 
 while A chưa là cây khung do 
 tìm cạnh ( u , v ) là an toàn đối với A 
 A = A  {( u , v )} 
 // A vẫn là tập con các cạnh của CKNN nào đó 
 return A 
Tìm cạnh an toàn bằng cách nào? 
Cạnh rẻ nhất 
để đảm bảo 
tính bất biến 
24 
Lát cắt 
Ta gọi lát cắt ( S, V S ) là một cách phân hoạch tập đỉnh V ra thành hai tập S và V S . Ta nói cạnh e là cạnh vượt lát cắt ( S, V S ) nếu một đầu mút của nó là thuộc S còn đầu mút còn lại thuộc V S . 
Giả sử A là một tập con các cạnh của đồ thị. Lát cắt ( S,V S ) được gọi là tương thích với A nếu như không có cạnh nào thuộc A là cạnh vượt lát cắt. 
25 
Lát cắt 
Lát cắt của G = ( V , E ) là phân hoạch V thành ( S , V – S ). 
Ví dụ. S = { a, b, c, f }, V – S = { e, d, g } 
Các cạnh ( b, d ), ( a, d ), ( b, e ), ( c, e ) là cạnh vượt lát cắt . 
Các cạnh còn lại không vượt lát cắt. 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
26 
Lát cắt tương thích với tập cạnh 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
Ví dụ. S = { a, b, c, f } 
A = { ( a , b ), ( d , g ), ( f , b ), ( a , f ) } 
A = A  { ( b , d ) } 
2 
1 
2 
1 
Lát cắt ( S , V – S ) là tương thích với A 1 không tương thích với A 2 
 (cạnh ( b , d ) vượt lát cắt). 
27 
Cạnh nhẹ 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
VD. S = { a, b, c, f } 
Cạnh ( b , e ) có trọng số 3, “nhẹ hơn” các cạnh 
vượt lát cắt còn lại ( a , d ), ( b , d ), và ( c , e ). 
cạnh nhẹ 
Cạnh nhẹ là cạnh có trọng số nhỏ nhất trong số các cạnh vượt lát cắt. 
2 
28 
Cạnh nhẹ là cạnh an toàn! 
Định lý. Giả sử ( S , V – S ) là lát cắt của G= ( V , E ) tương thích với 
 tập con A của E , và A là tập con của tập cạnh của CKNN của G . 
 Gọi ( u , v ) là cạnh nhẹ vượt lát cắt ( S , V – S ). Khi đó ( u , v ) là an 
 toàn đối với A ; nghĩa là, A  {( u , v )} cũng vẫn là tập con 
 của tập cạnh của CKNN. 
S 
V – S 
4 
2 
6 
u 
 v 
A gồm các cạnh đỏ . 
2 
29 
Tại sao cạnh nhẹ là an toàn ? 
S 
V – S 
4 
2 
6 
u 
 v 
2 
A 
y 
x 
A  { ( u , v ) }  T ' , tức là, ( u , v ) là an toàn đối với A . 
Chứng minh. Giả sử T là CKNN (gồm các cạnh đỏ) chứa A . 
Giả sử cạnh nhẹ ( u , v ) T . Ta có 
T  { ( u , v ) } chứa chu trình. 
Tìm được cạnh ( x , y ) T vượt lát cắt ( S , V – S ). 
Cây khung T ' = T – { ( x , y ) }  { ( u , v ) } có độ dài 
độ dài của cây khung T . Suy ra T ' cũng là CKNN. 
30 
Hệ quả Giả sử A là tập con của E và cũng là tập con của tập cạnh 
của CKNN nào đó của G , và C là một thành phần liên thông trong 
 rừng F = ( V , A ). Nếu ( u , v ) là cạnh nhẹ nối C với một thành phần 
liên thông khác trong F , thì ( u , v ) là an toàn đối với A . 
u 
v 
C 
7 
4 
w 
CM 
Cạnh ( u , v ) là cạnh nhẹ vượt lát cắt ( C , V – C ) tương thích với A . 
Theo định lý trên, cạnh ( u , v ) là an toàn đối với A . 
A gồm 5 cạnh đỏ . 
8 
Hệ quả 
31 
Tìm cạnh an toàn? 
Giả sử A là tập con của tập cạnh của một CKNN nào đó. 
A là rừng. 
Cạnh an toàn được bổ sung vào A có trọng số nhỏ nhất 
trong số các cạnh nối các cặp thành phần liên thông của nó. 
Thuật toán Kruskal 
Thuật toán Prim 
A là cây . 
Cạnh an toàn là cạnh nhẹ nối đỉnh trong A với một đỉnh 
không ở trong A . 
Thuật toán Kruskal 
Thuật toán Kruskal 
32 
Generic-MST(G, c) 
 A = { } 
 // Bất biến: A là tập con các cạnh của CKNN nào đó 
 while A chưa là cây khung do 
 tìm cạnh ( u , v ) là an toàn đối với A 
 A = A  {( u , v )} 
 // A vẫn là tập con các cạnh của CKNN nào đó 
 return A 
A là rừng. 
Cạnh an toàn được bổ sung vào A có trọng số nhỏ nhất 
trong số các cạnh nối các cặp thành phần liên thông của nó. 
33 
Thuật toán Kruskal – Ví dụ 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
Độ dài của CKNN: 14 
34 
Mô tả thuật toán Kruskal 
procedure Kruskal; 
begin 
 sắp xếp các cạnh e 1 , . . . , e m theo thứ tự không giảm của độ dài; 
 T =  ; (* T – tập cạnh của CKNN *) 
 for i = 1 to m do 
 if T  { e i } không chứa chu trình then T := T  { e i }; 
end 
35 
Thời gian tính 
Bước 1. Sắp xếp dãy độ dài cạnh. O ( m log n ) 
Bước lặp: Xác định xem T  { e i } có chứa chu trình hay không? 
Có thể sử dụng DFS để kiểm tra với thời gian O ( n ). 
Tổng cộng: O ( m log n + mn ) 
36 
Cách cài đặt hiệu quả 
Vấn đề đặt ra là: 
Khi cạnh e i =( j,k ) được xét, ta cần biết có phải j và k thuộc hai thành phần liên thông (tplt) khác nhau hay không. Nếu đúng, thì cạnh này được bổ sung vào cây khung và nó sẽ nối tplt chứa j và tplt chứa k . 
Thực hiện điều này như thế nào cho đạt hiệu quả? 
37 
Mỗi tplt C của rừng F được cất giữ như một tập. 
Ký hiệu First(C) đỉnh đầu tiên trong tplt C. 
Với mỗi đỉnh j trong tplt C , đặt First( j ) = First( C ) = đỉnh đầu tiên trong C . 
Chú ý: Thêm cạnh ( i,j ) vào rừng F tạo thành chu trình iff i và j thuộc cùng một tplt, tức là First( i ) = First( j ). 
Khi nối tplt C và D , sẽ nối tplt nhỏ hơn (ít đỉnh hơn) vào tplt lớn hơn (nhiều đỉnh hơn): 
 Nếu | C | > | D |, thì First( C  D ) := First( C ). 
Cách cài đặt hiệu quả 
38 
Phân tích thời gian tính 
Thời gian xác định First( i ) = First( j ) đối với i, j : O (1) cho mỗi cạnh. Tổng cộng là O ( m ). 
Thời gian nối 2 tplt S và Q , giả thiết | S | | Q |. 
O (1) với mỗi đỉnh của Q (là tplt nhỏ hơn) 
Mỗi đỉnh i ở tplt nhỏ hơn nhiều nhất là log n lần . (Bởi vì, số đỉnh của tplt chứa i tăng lên gấp đôi sau mỗi lần nối.) 
Tổng cộng thời gian nối là: O ( n log n ). 
Tổng thời gian thực hiện thuật toán là: 
 O ( m log n + n log n ). 
39 
Thuật toán Prim 
A là cây (Bắt đầu từ cây chỉ có 1 đỉnh) 
Cạnh an toàn là cạnh nhẹ nhất trong số các cạnh nối đỉnh trong A với một đỉnh không ở trong A . 
40 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
Thuật toán Prim – Ví dụ 
các cạnh để chọn 
chọn 
g 
41 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
42 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
43 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
44 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
45 
f 
d 
a 
b 
c 
e 
g 
2 
7 
5 
7 
1 
4 
1 
3 
4 
4 
5 
2 
Độ dài của CKNN: 14 
f 
46 
Mô tả thuật toán Prim 
procedure Prim( G , c ) 
begin 
 Chọn đỉnh tuỳ ý r V; 
 Khởi tạo cây T= ( V ( T ) , E ( T )) với V ( T )={ r }và E ( T )=; 
 while T có < n đỉnh do 
 begin 
 Gọi ( u , v ) là cạnh nhẹ nhất với u V ( T ) và v V ( G ) – V ( T ) 
 E ( T )  E ( T )  { ( u , v ) }; V ( T )  V ( T )  { v } 
 end 
end; 
Tính đúng đắn suy từ hệ quả đã chứng minh: 
Giả sử A là tập con của E và cũng là tập con của tập cạnh của CKNN của G , và C là một thành phần liên thông trong rừng F = ( V , A ). Nếu ( u , v ) là cạnh nhẹ nối C với một tplt khác trong F , thì ( u , v ) là an toàn đối với A . 
47 
Cài đặt thuật toán Prim đối với đồ thị dày 
Gi¶ sö ®å thÞ cho bëi ma trËn träng sè C ={ c [ i,j ], i, j = 1, 2,..., n }. 
Ở mçi b­íc ®Ó nhanh chãng chän ®Ønh vµ c¹nh cÇn bæ sung vµo c©y khung, c¸c ®Ønh cña ®å thÞ sÏ ®­îc g¸n cho c¸c nh·n. 
Nh·n cña mét ®Ønh v V-S cã d¹ng [ d [ v ], near [ v ]] : 
 d [ v ] dïng ®Ó ghi nhËn kho¶ng c¸ch tõ ®Ønh v ®Õn tËp ®Ønh S : 
	 d [ v ] := min{ c [ v, w ] : w S } ( = c [ v, z ]), 
near [ v ] := z ghi nhËn ®Ønh cña c©y khung gÇn v nhÊt 
48 
Thuật toán Prim 
procedure Prim; 
begin 
 (* B­íc khëi t¹o *) 
 S := { r }; T :=  ; d[r] := 0; near[r] := r. 
 for v V \ S do begin 
 d[v] := c[r,v]; near[v] := r; 
 end; 
 (* B­íc lÆp *) 
 for k:=2 to n do 
 begin 
 T×m u V\ S tho¶ m·n : d[u] = min { d[v] : v V\ S }; 
 S := S  { u }; T := T  { ( u, near[u] ) } ; 
 for v V\ S do 
 if d[v] > c[u,v] then begin 
 d[v] := c[u,v] ; near[v] := u; 
 end; 
 end; 
 H = ( S , T ) lµ c©y khung nhá nhÊt cña ®å thÞ ; 
end; 
Thời gian tính: O (| V | 2 ) 
49 
Thuật toán Prim – Ví dụ 
Ví dụ: Tìm CKNN cho đồ thị cho bởi ma trận trọng số 
 1 2 3 4 5 6 
 1 0 33 17 
 2 33 0 18 20 
 C = 3 17 18 0 16 4 
 4 20 16 0 9 8 
 5 4 9 0 14 
 6 8 14 0 
50 
Thuật toán Prim: Ví dụ 
Bước 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
1 
2 
3 
4 
5 
51 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
2 
3 
4 
5 
52 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
 - 
[18, 3] 
- 
[16, 3] 
[4, 3]* 
[ , 1] 
1, 3 
2 
3 
4 
5 
for v V\ S do 
 if d[v] > c[u,v] then 
 d[v] := c[u,v] ; 
 near[v] := u; 
53 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
 - 
[18, 3] 
- 
[16, 3] 
[4, 3]* 
[ , 1] 
1, 3 
2 
 - 
[18, 3] 
- 
[9,5]* 
- 
[14, 5] 
1, 3, 5 
3 
4 
5 
for v V\ S do 
 if d[v] > c[u,v] then 
 d[v] := c[u,v] ; 
 near[v] := u; 
54 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
 - 
[18, 3] 
- 
[16, 3] 
[4, 3]* 
[ , 1] 
1, 3 
2 
 - 
[18, 3] 
- 
[9,5]* 
- 
[14, 5] 
1, 3, 5 
3 
- 
[18,3] 
- 
- 
- 
[8,4]* 
1,3,5,4 
4 
5 
for v V\ S do 
 if d[v] > c[u,v] then 
 d[v] := c[u,v] ; 
 near[v] := u; 
55 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
 - 
[18, 3] 
- 
[16, 3] 
[4, 3]* 
[ , 1] 
1, 3 
2 
 - 
[18, 3] 
- 
[9,5]* 
- 
[14, 5] 
1, 3, 5 
3 
- 
[18,3] 
- 
- 
- 
[8,4]* 
1,3,5,4 
4 
- 
[18,3]* 
- 
- 
- 
- 
1,3,5,4,6 
5 
for v V\ S do 
 if d[v] > c[u,v] then 
 d[v] := c[u,v] ; 
 near[v] := u; 
56 
Thuật toán Prim: Ví dụ 
Đỉnh 1 
Đỉnh 2 
Đỉnh 3 
Đỉnh 4 
Đỉnh 5 
Đỉnh 6 
S 
Khởi tạo 
[0, 1] 
[33, 1] 
[17, 1]* 
[ , 1] 
[ , 1] 
[ , 1] 
1 
1 
 - 
[18, 3] 
- 
[16, 3] 
[4, 3]* 
[ , 1] 
1, 3 
2 
 - 
[18, 3] 
- 
[9,5]* 
- 
[14, 5] 
1, 3, 5 
3 
- 
[18,3] 
- 
- 
- 
[8,4]* 
1,3,5,4 
4 
- 
[18,3]* 
- 
- 
- 
- 
1,3,5,4,6 
5 
- 
- 
- 
- 
- 
- 
1,3,5,4,6,2 
Độ dài của CKNN : 18 + 17 + 9 + 4 + 8 = 56 
Tập cạnh của CKNN: {(2,3), (3,1), (4,5), (5,3), (6,4)} 
Người đề xuất bài toán MST 
57 
Otakar Borůvka 
Nhà khoa học Séc (Czech) 
Người đề xuất bài toán 
Đề xuất thuật toán thời gian O ( m log n ) 
Bài báo được xuất bản ở Séc từ năm 1926. 
Ứng dụng vào việc phát triển hệ thống mạng điện ở Bohemia. 
Tăng tốc 
O ( m log n ) 	 Borůvka, Prim, Dijkstra, Kruskal, 
O ( m log log n ) 	 Yao (1975), Cheriton-Tarjan (1976) 
O ( m  ( m , n )) 	 Fredman-Tarjan (1987) 
O ( m log  ( m , n )) Gabow-Galil-Spencer-Tarjan (1986) 
O ( m ( m , n )) 	 Chazelle ( JACM 2000) 
Optimal	 Pettie-Ramachandran ( JACM 2002) 
58 
59 
 Questions? 
60