Chương 4 Bài toán cây khung nhỏ nhất
The Minimum Spanning Tree Problem
Nội dung
ấ ơ ả ủ ấ ơ ả ủ 4.1. Cây và các tính ch t c b n c a cây 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
2
Cây và rừng (Tree and Forest)
(cid:0)
(cid:0) Nh vËy, rõ ng lµ ®å thÞ mµ mç i thµnh phÇn liªn
§Þnh ng hÜa 1. Ta g äi c ©y lµ ®å thÞ v « híng liª n th«ng kh«ng c ã c hu tr×nh. §å thÞ kh«ng c ã c hu tr×nh ®îc g äi lµ rõ ng .
T1
T2
T3
th«ng c ña nã lµ mé t c ©y.
Rừng F gồm 3 cây T1, T2,, T3
3
VÍ DỤ
G1, G2 là cây
G3, G4 không là cây
4
Các tính chất cơ bản của cây
(cid:0) Đ nh lý 1.
ị Gi
s T= ề ồ ị ươ ướ ươ ả ử ệ Khi đó các m nh đ sau đây là t ỉ ng n đ nh. ng:
(V,E) là đ th vô h ng đ ứ
ạ
ầ
ề ượ ố ớ ấ ỳ ủ c n i v i nhau b i (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ó n1 c nh; (3) T liên thông và có n1 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 đ
ơ ỉ ộ ườ đúng m t đ
(6) T không ch a chu trình nh ng h c thêm vào ộ ạ ượ ng đi đ n; ứ nó m t c nh ta thu đ ễ ứ ư ộ c đúng m t chu trình.
5
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.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
6
Cây khung của đồ thị
(cid:0) Đ nh nghĩa 2.
ị ả ử Gi (V,E) là đ th v
ượ ọ ồ ị ô h c g i là c ướ ên ng li ây khung E đ
s G= thông. Cây T=(V,F) v i Fớ (cid:0) ủ ồ ị c a đ th G.
b c b c b c
a d a d a d
T2
G
T1
e e e
Đồ thị G và 2 cây khung T1 và T2 của nó
7
Số lượng cây khung của đồ thị
(cid:0) Đ nh lý sau đây cho bi khung c a đ th đ y đ
ị ế ố ượ t s l ng cây
ủ ồ ị ầ ủ Kn:
(cid:0) Đ nh lý 2 (Cayley).
ị ủ ồ ị ố S cây khung c a đ th
Arthur Cayley (1821 – 1895)
Kn là nn2 .
b a b c
b c a
a c c a b
K3 Ba cây khung c a Kủ 3
8
Bài toán trong hoá học hữu cơ
ử
ên tử
(cid:0) Bi u di n c u trúc phân t ễ ấ ể (cid:0) M i đ nh t ỗ ỉ (cid:0) C nh – th hi n liên k t gi a các nguyên t ạ
ớ ng ng v i m t nguy ế ươ ứ ể ệ : ộ ữ ử
ứ ân c a cacbua hydro no ch a
(cid:0) Bài toán: Đ m s đ ng ph ế ên t m t s nguy
ộ ố ố ồ cử ácbon cho tr ủ cướ
9
methane
ethane
H H
H C H H C H
propane
H H H C H
H
H C H
H
C H H
H C H
butane
H C H H C H
H C H H H C
saturated hydrocarbons CnH2n+2
H H
10
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.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
11
Tập các chu trình cơ bản
(cid:0) 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.
(cid:0)
§Þnh nghÜa 3. NÕu thªm m é t c¹nh ngoµi e (cid:0) 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µ Ce . TËp c¸c chu tr×nh (cid:0) E \ T } = { Ce : e (cid:0)
®îc gäi lµ tËp c¸c chu tr×nh c¬ b¶n cña ®å thÞ G.
12
Tính chất
(cid:0) Gi¶ sö A vµ B lµ hai tËp hîp, ta ®a vµo phÐp to¸n
sau
B = (A (cid:0)
B) \ (A (cid:0)
B).
A (cid:0) TËp A(cid:0) B ®îc gäi lµ hiÖu ®è i xø ng cña hai tËp A
vµ B.
(cid:0) Tªn gäi c hu tr×nh c ¬ b ¶n g¾n liÒn víi sù kiÖn chØ
ra trong ®Þnh lý sau ®©y:
(cid:0) §Þ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µ 13 hiÖu ®è i xø ng cña m é t s è c¸c chu tr×nh c¬ b¶n.
Ý nghĩa ứng dụng
ệ
ơ ả
(cid:0) Vi c tìm t p các chu trình c b n gi
ề ả
ậ ọ ỗ
ạ
ế ọ
ệ
ằ
ữ ộ m t vai ệ ạ ấ i tích m ng đi n: trò quan tr ng trong v n đ gi Theo m i chu trình c b n c a đ th t ơ ả ồ ị ươ ủ ng ế ẽ ầ ệ ứ t ng v i m ng đi n c n phân tích ta s thi ế ươ ộ ậ ng trình tuy n tính theo c m t ph l p đ ệ ổ ị đ 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 ệ ố
ế
ạ ườ
ượ c ọ ệ cho phép tính toán hi u đi n th trên m i ủ ướ đo n đ
ế ng trình tuy n tính thu đ ệ ệ i đi n.
ng dây c a l
14
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 ¸c h kÒ Ke (v ), v (cid:0) V.
ậ
ầ
ứ ỉ
ơ ả ủ
pro c e dure Cyc le (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 b iÕn d , num , S TACK, Ind e x lµ to µn c ô c *) be g in d:=d+1; S TACK[d] := v; num := num+1; Inde x[v] := num; fo r u (cid:0) Ke (v) do if Inde x[u]=0 the n Cyc le (u) e ls e if (u (cid:0)
S TACK[d1]) and (Inde x[v] > Inde x[u]) the n
< Ghi nhËn c hu tr×nh v íi c ¸c ®Ønh: S TACK[d ], S TACK[d 1], ... , S TACK[c ], v íi S TACK[c ]=u >; d := d1; e nd;
15
Thuật toán xây dựng tập chu trình cơ bản
V do Inde x[v] := 0;
V do
(* Main Pro g ram *) BEGIN fo r v (cid:0) num := 0; d := 0; S TACK[0] := 0; fo r v (cid:0) if Inde x[v] = 0 the n Cyc le (v); END.
(cid:0) Đ ph c t p:
ộ ứ ạ O(|V|+|E|)
16
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 4.4. Bài toán cây khung nh nh t
17
BÀI TOÁN CÂY KHUNG NHỎ NHẤT
Minimum Spanning Tree (MST)
18
Bài toán CKNN
ướ
ồ ị ộ ọ
ầ ỏ ớ ọ G=(V,E) v i tr ng ng liên thông Bài toán: Cho đ th vô h s ố c(e), e (cid:0) ố ổ ủ 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.
a
7
d
2
2 5
f
5 4
b
g
1
ủ
1 4 3 7
c
e
ạ
ộ
4
19
ộ Đ dài c a cây khung là ổ T ng đ dài các c nh: 14
Bài toán cây khung nhỏ nhất
ố ư ổ ợ
ể ướ ạ
i d ng bài to
án t
i u t
h p:
át bi u d
ự ể
c(e) (cid:0)
min,
ớ
(cid:0) Có th phể Tìm c c ti u c(H) = (cid:0) e(cid:0) T ề v i đi u ki n
ệ H=(V,T) là cây khung c aủ G.
ố ượ
ị
ể ả
ờ
ộ
Do s l ng c Cayley), nên không th gi
ây khung c a ủ G là r t l n (xem đ nh lý ấ ớ ệ i nh duy t toàn b
20
Ứng dụng thực tế: Mạng truyền thông
ự
ạ
(cid:0) Công ty truy n thề
ông AT&T c n xầ
ế ông k t n i
ỏ
ênh n i ố i và j là cij. H i chi ph ệ
ây d ng m ng ố n khách hàng. Chi phí th c ự ấ ể í nh nh t đ ế ố ấ ả ác khách hàng là bao
ỏ t c c
ề truy n th hi n kệ ệ ự th c hi n vi c k t n i t nhiêu?
4 10
3
8 2 5 7
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. 9 1
6
21
Bµi to ¸n x©y d ùng hÖ thè ng ®ê ng s ¾t
(cid:0) Gi
ố ả ử
ườ ự s ta mu n xây d ng m t h th ng đ ữ
ắ ố ng s t n i n ố i gi a hai thành ph ả ờ ổ ấ ỏ
ồ ị
ố ươ ươ ứ ớ ộ ệ ố ạ ể ố thành ph sao cho hành khách có th đi l ự ấ ỳ ồ b t k đ ng th i t ng chi phí xây d ng ph i là nh nh t. (cid:0) Rõ ràng là đ th mà đ nh là các thành ph còn các c nh là các ng án ố ạ ng ng v i ph
ỉ ng s t n i các thành ph t ố ư
ườ ế tuy n đ ự xây d ng t ậ ắ ố ả i u ph i là cây. ẫ ặ ề
ấ ồ ị ầ ỗ ỉ ươ ủ ứ ớ ỉ
ự
(cid:0) Vì v y, bài toán đ t ra d n v bài toán tìm cây khung nh ỏ ộ ng ng v i m t nh t trên đ th đ y đ n đ nh, m i đ nh t ạ thành ph , v i đ dài trên các c nh chính là chi phí xây d ng ố ươ ứ ườ ng ng đ
(cid:0) 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è .
ố ớ ộ ố ng ray n i hai thành ph t
22
Sơ đồ chung của các giải thuật
ậ ủ
ạ ố ớ A ạ ế A là t p con các c nh c a CKNN nào đó do u, v) là an toàn đ i v i
ủ ẫ ạ ậ
ấ ẻ ạ C nh r nh t ể ả ả đ đ m b o ế ấ tính b t bi n
ằ
ạ
Tìm c nh an toàn b ng cách nào?
GenericMST(G, c) A = { } ấ //B t bi n: ư while A ch a là cây khung tìm c nh ( A = A (cid:0) {(u, v)} // A v n là t p con các c nh c a CKNN nào đó return A
23
Lát cắt Lát cắt
ạ
(cid:0) Ta g i ọ lát c t ắ (S, V(cid:0) S) là m t cách phân ho ch ộ V ra thành hai t p ậ S và V(cid:0) S. Ta nói c nh ạ ắ (S, V(cid:0) S) n u m t đ u mút ế ượ v ộ V(cid:0)
t lát c t ầ ộ S còn đ u mút còn l
ộ ầ ạ i thu c
ủ ồ ị
ỉ ậ t p đ nh e là c nh ạ ủ c a nó là thu c S. (cid:0) Gi
ọ c g i là
ả ử A là m t t p con các c nh c a đ th . Lát v i ớ A n u ế t ượ t lát
ạ ng thích ạ ộ A là c nh v
ộ ậ s c t (ắ S,V(cid:0) S) đ ươ ượ ạ ư nh không có c nh nào thu c c t. ắ
24
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}
a
7
d
2 2 5
b
f
4 5
g
1
1 4 3
c
e
4 7
ạ ượ ắ . t lát c t
25
b, d), (a, d), (b, e), (c, e) là c nh v ượ ạ ắ ạ Các c nh ( ạ Các c nh còn l i không v t lát c t.
Lát cắt tương thích với tập cạnh
{ (b, d) } Ví d .ụ S = {a, b, c, f} A = { (a, b), (d, g), (f, b), (a, f) } 1 A = A (cid:0) 2 1
a
7
d
2 2 5
b
f
4 5
g
1
4 1 3
c
e
4 7
ươ ng thích v i ớ A2 ớ A1 không t
26
ượ Lát c t (ắ S, V – S) là t (c nh ạ (b, d) v ươ ng thích v i ắ t lát c t).
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.
VD. S = {a, b, c, f}
a
d
7
2 2 5
b
f
4 5
g
1 3
1 4 ẹ ạ c nh nh
c
e
4 7
ẹ ơ ạ ố b, e) có tr ng s 3, “nh h n” các c nh
27
ạ C nh ( ượ v ọ ạ a, d), (b, d), và (c, e). ắ t lát c t còn l i (
Cạnh nhẹ là cạnh an toàn!
ị s ( ả ử S, V – S) là lát c t c a Gi
ạ t lát c t ( ớ ắ ủ G=(V, E) t ươ ng thích v i ủ G. A c a ủ E, và A là t p con c a t p c nh c a CKNN c a ủ ủ ậ ạ ắ S, V – S). Khi đó (u, v) là an
ậ ẫ {(u, v)} cũng v n là t p con
Đ nh lý. ậ ậ t p con G i (ọ u, v) là c nh nh v ẹ ượ ố ớ A; nghĩa là, A (cid:0) toàn đ i v i ủ ủ ậ ạ c a t p c nh c a CKNN.
4 v
2
S
2
V – S
6 u
28
ạ ồ A g m các c nh đỏ.
Tại sao cạnh nhẹ là an toàn?
ứ
ạ
ỏ
s
ứ A.
Ch ng minh.
Gi
ả ử T là CKNN (g m các c nh đ ) ch a ồ T. Ta có
ẹ u, v) (cid:0)
Gi ả ử ạ s c nh nh ( T (cid:0)
ượ ạ
c c nh (
ứ { (u, v) } ch a chu trình. x, y) (cid:0)
T v
t lát c t (
ắ S, V – S).
ộ
{ (u, v) } có đ dài T. Suy ra T ' cũng là CKNN.
ượ Tìm đ Cây khung T ' = T – { (x, y) } (cid:0) ộ đ dài c a cây khung A (cid:0)
ủ { (u, v) } (cid:0)
ứ T ', t c là, (
u, v) là an toàn đ i v i
ố ớ A.
(cid:0)
A
4 v
2
S y x
2
V – S
6 u
29
ả
H quệ
ậ s ả Gi ậ ả ử A là t p con c a ủ E và cũng là t p con c a t p c nh
ầ ộ
ủ ậ ạ ủ G, và C là m t thành ph n liên thông trong ầ ạ ộ ẹ ố C v i m t thành ph n
H quệ ủ c a CKNN nào đó c a ớ r ng ừ F = (V, A). N u (ế u, v) là c nh nh n i ố ớ A. liên thông khác trong F, thì (u, v) là an toàn đ i v i
ẹ ượ ươ ớ ạ u, v) là c nh nh v t lát c t ( ắ C, V – C) t ng thích v i
8
ạ ị CM ạ C nh ( A. Theo đ nh lý trên, c nh ( u, v) là an toàn đ i v i ố ớ A. v
4 w
7
ạ
ồ
A g m 5 c nh
đỏ.
u
C
30
Tìm cạnh an toàn?
ủ ậ ạ ủ ậ ộ Gi ả ử A là t p con c a t p c nh c a m t CKNN nào đó. s
ậ Thu t toán Kruskal
ượ ổ ạ ỏ c b sung vào
ấ ố A có tr ng s nh nh t ủ ọ ầ ặ ố A là r ng.ừ C nh an toàn đ ạ ố 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 Prim
ẹ ố ỉ ộ ỉ ớ A v i m t đ nh
ở A là cây. ạ C nh an toàn là c nh nh n i đ nh trong không trong ạ A.
31
Thuật toán Kruskal
ậ ủ
ạ ố ớ A ạ ế A là t p con các c nh c a CKNN nào đó do u, v) là an toàn đ i v i
ủ ạ ậ ẫ
GenericMST(G, c) A = { } ấ //B t bi n: ư while A ch a là cây khung tìm c nh ( A = A (cid:0) {(u, v)} // A v n là t p con các c nh c a CKNN nào đó return A
Thuật toán Kruskal
ượ ổ ạ ỏ c b sung vào
ấ ố A có tr ng s nh nh t ủ ọ ầ ặ ố A là r ng.ừ C nh an toàn đ ạ ố trong s các c nh n i các c p thành ph n liên thông c a nó.
32
Thuật toán Kruskal – Ví dụ
a
d
7
2 2 5
b
f
4 5
g
1
4 3 1
c
e
7
4
ủ ộ Đ dài c a CKNN: 14
33
Mô tả thuật toán Kruskal
procedure Kruskal; begin
ạ ủ ộ ả không gi m c a đ dài;
e1, . . . , em theo th t ủ ậ ạ ứ ự ế ; (* T – t p c nh c a CKNN *)
ắ s p x p các c nh T = (cid:0) for i = 1 to m do
ứ then T := T (cid:0) if T (cid:0) {ei} không ch a chu trình {ei};
end
34
Thời gian tính
ế
ạ
ộ
S p x p dãy đ dài c nh.
B
c 1.
ắ ướ O(m log n)
ứ
T (cid:0)
B
c l p:
{ ei } có ch a chu
ướ ặ Xác đ nh xem ị 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)
35
Cách cài đặt hiệu quả
ấ
ề ặ V n đ đ t ra là:
ầ
ế
Khi c nh ạ
t có ph i
ei=(j,k) đ
ượ c xét, ta c n bi ầ
thành ph n liên thông (tplt) ượ
ế
ạ
ẽ ố
ả j và khác nhau ổ c b sung ứ j và tplt ch a ứ
ộ k thu c hai hay không. N u đúng, thì c nh này đ vào cây khung và nó s n i tplt ch a k.
ự
ệ
ề
ệ
ạ
Th c hi n đi u này nh th nào cho đ t hi u qu ? ả ư ế
36
Cách cài đặt hiệu quả
ượ ấ ữ ư ộ ậ c c t gi C c a r ng ủ ừ F đ nh m t t p.
ầ
(cid:0) M i tplt ỗ (cid:0) Ký hi u First(C) đ nh đ u tiên trong tplt C. ỉ ệ (cid:0) V i m i đ nh ỗ ỉ tiên trong C.
(cid:0) Chú ý: Thêm c nh (
ặ ớ ầ ỉ j trong tplt C, đ t First( j) = First(C) = đ nh đ u
ạ 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).
ỉ ơ nh h n ỏ ơ (ít đ nh h n) vào tplt
ỉ
ộ (cid:0) Khi n i tplt ố ẽ ố C và D, s n i tplt ơ ề ơ (nhi u đ nh h n): ớ l n h n N u |ế C| > |D|, thì First(C(cid:0) D) := First(C).
37
Phân tích thời gian tính
ờ ị i) = First(j) đ i v i ố ớ i, j: O(1) cho m i ỗ
(cid:0) Th i gian xác đ nh First( ạ O(m). c nh. T ng c ng là
ộ ổ
(cid:0) Th i gian n i
ờ ả ố 2 tplt S và Q, gi thi ế S| (cid:0) t | |Q|.
ỗ ỉ ở tplt nh h n
ủ Q (là tplt nh h n) ề ỏ ơ nhi u nh t là log ấ n l nầ . (B i vì, ố ỗ ầ
O(1) v i m i đ nh c a ỏ ơ ớ M i đ nh ở ấ ỗ ỉ i ứ i tăng lên g p đôi sau m i l n n i.) ủ ố ỉ s đ nh c a tplt ch a (cid:0) T ng c ng th i gian n i là: ố ờ ộ
ổ O(n log n).
(cid:0) T ng th i gian th c hi n thu t toán là: ậ ự O( m log n + n log n).
ổ ệ ờ
38
Thuật toán Prim
ắ ầ ừ
(cid:0) A là cây (B t đ u t
ỉ cây ch có 1
ấ ớ
ở
(cid:0) C nh an toàn là c nh nh nh t trong ạ ố ỉ ộ A v i m t trong
ạ không
ỉ đ nh) ẹ ạ ố s các c nh n i đ nh trong ỉ đ nh
A.
39
Thuật toán Prim – Ví dụ
a
d
7
ch nọ
2 2 5
b
f
4 5
g g
1
4 3 1
c
e
7
ạ
ể ọ các c nh đ ch n
4
40
a
d
7
2 2 5
b
f
4 5
g
1
4 3 1
c
e
7
4
41
a
d
7
2 2 5
b
f
4 5
g
1
4 3 1
c
e
7
4
42
a
d
7
2 2 5
b
f
4 5
g
1
4 3 1
c
e
7
4
43
a
d
7
2 2 5
b
f
4 5
g
1
4 3 1
c
e
7
4
44
ủ ộ Đ dài c a CKNN: 14
a
d
7
2 2 5
b
f f
4 5
g
1
4 3 1
c
e
7
4
45
Mô tả thuật toán Prim
ỳ r (cid:0) V; T=(V(T), E(T)) v i ớ V(T)={ r }và E(T)=(cid:0)
;
ỉ
do
ẹ
ạ
ấ ớ u (cid:0)
V(T) và v(cid:0) V(G) – V(T)
V(T) (cid:0)
{ v }
procedure Prim(G, c) begin ỉ ọ Ch n đ nh tu ý ở ạ Kh i t o cây while T có < n đ nh begin G i (ọ u, v) là c nh nh nh t v i E(T) (cid:0) { (u, v) }; V(T) (cid:0) E(T) (cid:0) end end;
ậ
ủ ậ ạ
ủ
s
ủ ủ E và cũng là t p con c a t p c nh c a CKNN c a
ớ
ậ ả ử A là t p con c a Gi ầ ộ G, và C là m t thành ph n liên thông trong r ng ộ ẹ ố C v i m t tplt khác trong ạ c nh nh n i
ừ F = (V, A). N u (ế u, v) là ố ớ A.
F, thì (u, v) là an toàn đ i v i
ắ ừ ệ ứ ả Tính đúng đ n suy t h qu đã ch ng minh:
46
Cài đặt thuật toán Prim đối với đồ thị dày
(cid:0) Gi¶ sö ®å thÞ cho bëi ma trËn träng sè C={c[i,j], i, j = 1,
(cid:0) Ở 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.
(cid:0) Nh·n cña mét ®Ønh v (cid:0)
2,..., n}.
d[v] dïng ®Ó ghi nhËn kho¶ng c¸ch tõ ®Ønh v ®Õn
VS cã d¹ng [d[v], ne ar[v]] :
ne ar[v] := z ghi nhËn ®Ønh cña c©y khung gÇn v nhÊt
tËp ®Ønh S : d[v] := min{ c[v, w] : w (cid:0) S } ( = c[v, z ]),
47
Thuật toán Prim
; d[r] := 0; ne ar[r] := r.
V \ S do begin
V\ S };
V\ S tho ¶ m ∙n: d[u] = min { d[v] : v (cid:0) { u }; T := T (cid:0)
{ ( u, ne ar[u] ) } ;
V\ S do
procedure Prim; begin (* Bíc khë i t¹o *) S := { r }; T := (cid:0) for v (cid:0) d[v] := c [r,v]; ne ar[v] := r; end; (* Bíc lÆp *) for k:=2 to n do begin T×m u (cid:0) S := S (cid:0) for v(cid:0) if d[v] > c [u,v] then begin d[v] := c [u,v] ; ne ar[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)
48
Thuật toán Prim – Ví dụ
(cid:0)
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 (cid:0) (cid:0) (cid:0) (cid:0) 2 33 0 18 20 (cid:0) C = 3 17 18 0 16 4 (cid:0) 4 (cid:0) 5 (cid:0) 6 (cid:0)
20 16 0 9 8 (cid:0) 4 9 0 14 (cid:0) (cid:0) 8 14 0
49
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
50
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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
[(cid:0)
, 1]
1
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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
, 1]
1
[(cid:0)
-
[18, 3]
-
[16, 3]
[4, 3]*
, 1]
1, 3
[(cid:0)
1
2
3
4
5
V\ S do
52
for v(cid:0) if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;
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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
, 1]
1
[(cid:0)
-
[18, 3]
-
[16, 3]
[4, 3]*
, 1]
1, 3
[(cid:0)
1
-
[18, 3]
-
[9,5]*
-
[14, 5]
1, 3, 5
2
3
4
5
V\ S do
53
for v(cid:0) if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;
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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
, 1]
1
[(cid:0)
[(cid:0)
-
[18, 3]
-
[16, 3]
[4, 3]*
, 1]
1, 3
1
-
[18, 3]
-
[9,5]*
-
[14, 5]
1, 3, 5
2
-
[18,3]
-
-
-
[8,4]*
1,3,5,4
3
4
5
V\ S do
for v(cid:0) 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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
, 1]
1
[(cid:0)
[18, 3]
-
[16, 3]
[4, 3]*
, 1]
1, 3
[(cid:0)
-
1
[18, 3]
-
[9,5]*
[14, 5]
1, 3, 5
-
-
2
[18,3]
-
-
-
[8,4]*
1,3,5,4
-
3
[18,3]*
-
-
-
1,3,5,4,6
-
-
4
5
V\ S do
55
for v(cid:0) if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;
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]*
[(cid:0)
, 1]
[(cid:0)
, 1]
, 1]
1
[(cid:0)
1
-
[18, 3]
-
[16, 3]
[4, 3]*
, 1]
1, 3
[(cid:0)
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)}
56
Người đề xuất bài toán MST
Otakar Borůvka
ấ ả ở ượ ừ O(m log n) năm Séc t
ụ ể ệ ố
ng d ng vào vi c phát tri n h th ng ạ ệ ở ọ Nhà khoa h c Séc (Czech) ấ ườ ề i đ xu t bài toán Ng ờ ậ ấ ề Đ xu t thu t toán th i gian Bài báo đ c xu t b n 1926. Ứ m ng đi n ệ Bohemia.
57
Tăng tốc
FredmanTarjan (1987)
Chazelle (JACM 2000)
O(m log n) Borůvka, Prim, Dijkstra, Kruskal,… O(m log log n) Yao (1975), CheritonTarjan (1976) O(m (cid:0) (m, n)) O(m log (cid:0) (m, n)) GabowGalilSpencerTarjan (1986) O(m (cid:0) (m, n)) Optimal 2002)
PettieRamachandran (JACM
