CH NG VIƯƠ
CÂY
M t đ th liên thông và không có chu trình đ c g i là cây. Cây đã đ c dùngộ ồ ị ượ ọ ượ
t năm 1857, khi nhà toán h c Anh tên là Arthur Cayley dùng cây đ xác đ nh nh ngừ ọ ể ị ữ
d ng khác nhau c a h p ch t hoá h c. T đó cây đã đ c dùng đ gi i nhi u bài toánạ ủ ợ ấ ọ ừ ượ ể ả ề
trong nhi u lĩnh v c khác nhau. Cây r t hay đ c s d ng trong tin h c. Ch ng h n,ề ự ấ ượ ử ụ ọ ẳ ạ
ng i ta dùng cây đ xây d ng các thu t toán r t có hi u qu đ đ nh v các ph n tườ ể ự ậ ấ ệ ả ể ị ị ầ ử
trong m t danh sách. Cây cũng dùng đ xây d ng các m ng máy tính v i chi phí rộ ể ự ạ ớ ẻ
nh t cho các đ ng đi n tho i n i các máy phân tán. Cây cũng đ c dùng đ t o raấ ườ ệ ạ ố ượ ể ạ
các mã có hi u qu đ l u tr và truy n d li u. Dùng cây có th mô hình các th t cệ ả ể ư ữ ề ữ ệ ể ủ ụ
mà đ thi hành nó c n dùng m t dãy các quy t đ nh. Vì v y cây đ c bi t có giá tr khiể ầ ộ ế ị ậ ặ ệ ị
nghiên c u các thu t toán s p x p.ứ ậ ắ ế
6.1. Đ NH NGHĨA VÀ CÁC TÍNH CH T C B N.Ị Ấ Ơ Ả
6.1.1. Đ nh nghĩa:ị Cây là m t đ th vô h ng liên thông, không ch a chu trình và cóộ ồ ị ướ ứ
ít nh t hai đ nh.ấ ỉ
M t đ th vô h ng không ch a chu trình và có ít nh t hai đ nh g i là m tộ ồ ị ướ ứ ấ ỉ ọ ộ
r ng. Trong m t r ng, m i thành ph n liên thông là m t cây.ừ ộ ừ ỗ ầ ộ
Thí d 1:ụ R ng sau có 3 cây:ừ
6.1.2. M nh đ :ệ ề N u T là m t cây có n đ nh thì T có ít nh t hai đ nh treo.ế ộ ỉ ấ ỉ
Ch ng minh:ứ L y m t c nh (a,b) tuỳ ý c a cây T. Trong t p h p các đ ng đi s c pấ ộ ạ ủ ậ ợ ườ ơ ấ
ch a c nh (a,b), ta l y đ ng đi t u đ n v dài nh t. Vì T là m t cây nên u ứ ạ ấ ườ ừ ế ấ ộ ≠ v. M tặ
khác, u và v ph i là hai đ nh treo, vì n u m t đ nh, u ch ng h n, không ph i là đ nh treoả ỉ ế ộ ỉ ẳ ạ ả ỉ
thì u ph i là đ u mút c a m t c nh (u,x), v i x là đ nh không thu c đ ng đi t u đ nả ầ ủ ộ ạ ớ ỉ ộ ườ ừ ế
v. Do đó, đ ng đi s c p t x đ n v, ch a c nh (a,b), dài h n đ ng đi t u đ n v,ườ ơ ấ ừ ế ứ ạ ơ ườ ừ ế
trái v i tính ch t đ ng đi t u đ n v đã ch n.ớ ấ ườ ừ ế ọ
6.1.3. Đ nh lý:ị Cho T là m t đ th có n ộ ồ ị ≥ 2 đ nh. Các đi u sau là t ng đ ng:ỉ ề ươ ươ
1) T là m t cây.ộ
2) T liên thông và có n−1 c nh.ạ
3) T không ch a chu trình và có nứ−1 c nh.ạ
4) T liên thông và m i c nh là c u.ỗ ạ ầ
5) Gi a hai đ nh phân bi t b t kỳ c a T luôn có duy nh t m t đ ng đi s c p.ữ ỉ ệ ấ ủ ấ ộ ườ ơ ấ
87
a
b
c f
d
e
g h j
i
k
l
m
n
6) T không ch a chu trình nh ng khi thêm m t c nh m i thì có đ c m t chu trình duyứ ư ộ ạ ớ ượ ộ
nh t.ấ
Ch ng minh:ứ 1)⇒2) Ch c n ch ng minh r ng m t cây có n đ nh thì có nỉ ầ ứ ằ ộ ỉ −1 c nh. Taạ
ch ng minh b ng quy n p. Đi u này hi n nhiên khi n=2. Gi s cây có k đ nh thì cóứ ằ ạ ề ể ả ử ỉ
k−1 c nh, ta ch ng minh r ng cây T có k+1 đ nh thì có k c nh. Th t v y, trong T n u taạ ứ ằ ỉ ạ ậ ậ ế
xoá m t đ nh treo và c nh treo t ng ng thì đ th nh n đ c là m t cây k đ nh, câyộ ỉ ạ ươ ứ ồ ị ậ ượ ộ ỉ
này có k−1 c nh, theo gi thi t quy n p. V y cây T có k c nh.ạ ả ế ạ ậ ạ
2)⇒3) N u T có chu trình thì b đi m t c nh trong chu trình này thì T v n liên thông.ế ỏ ộ ạ ẫ
Làm l i nh th cho đ n khi trong T không còn chu trình nào mà v n liên thông, lúc đóạ ư ế ế ẫ
ta đ c m t cây có n đ nh nh ng có ít h n nượ ộ ỉ ư ơ −1 c nh, trái v i 2).ạ ớ
3)⇒4) N u T có k thành ph n liên thông Tế ầ 1, ..., Tk l n l t có s đ nh là nầ ượ ố ỉ 1, ..., nk (v iớ
n1+n2+ … +nk=n) thì m i Tỗi là m t cây nên nó có s c nh là nộ ố ạ i−1. V y ta cóậ
n−1=(n1−1)+(n2−1)+ ... +(nk−1)=(n1+n2+ … +nk)−k=n−k.
Do đó k=1 hay T liên thông. H n n a, khi b đi m t c nh thì T h t liên thông, vì n uơ ữ ỏ ộ ạ ế ế
còn liên thông thì T là m t cây n đ nh v i nộ ỉ ớ −2 c nh, trái v i đi u đã ch ng minh trên.ạ ớ ề ứ ở
4)⇒5) Vì T liên thông nên gi a hai đ nh phân bi t b t kỳ c a T luôn có m t đ ng điữ ỉ ệ ấ ủ ộ ườ
s c p, nh ng không th đ c n i b i hai đ ng đi s c p vì n u th , hai đ ng đóơ ấ ư ể ượ ố ở ườ ơ ấ ế ế ườ
s t o ra m t chu trình và khi b m t c nh thu c chu trình này, T v n liên thông, tráiẽ ạ ộ ỏ ộ ạ ộ ẫ
v i gi thi t.ớ ả ế
5)⇒6) N u T ch a m t chu trình thì hai đ nh b t kỳ trên chu trình này s đ c n i b iế ứ ộ ỉ ấ ẽ ượ ố ở
hai đ ng đi s c p. Ngoài ra, khi thêm m t c nh m i (u,v), c nh này s t o nên v iườ ơ ấ ộ ạ ớ ạ ẽ ạ ớ
đ ng đi s c p duy nh t n i u và v m t chu trình duy nh t.ườ ơ ấ ấ ố ộ ấ
6)⇒1) N u T không liên thông thì thêm m t c nh n i hai đ nh hai thành ph n liênế ộ ạ ố ỉ ở ầ
thông khác nhau ta không nh n đ c m t chu trình nào. V y T liên thông, do đó nó làậ ượ ộ ậ
m t cây.ộ
6.2. CÂY KHUNG VÀ BÀI TOÁN TÌM CÂY KHUNG NH NH T.Ỏ Ấ
6.2.1. Đ nh nghĩa:ị Trong đ th liên thông G, n u ta lo i b c nh n m trên chu trìnhồ ị ế ạ ỏ ạ ằ
nào đó thì ta s đ c đ th v n là liên thông. N u c lo i b các c nh các chu trìnhẽ ượ ồ ị ẫ ế ứ ạ ỏ ạ ở
khác cho đ n khi nào đ th không còn chu trình (v n liên thông) thì ta thu đ c m tế ồ ị ẫ ượ ộ
cây n i các đ nh c a G. Cây đó g i là cây khung hay cây bao trùm c a đ th G.ố ỉ ủ ọ ủ ồ ị
T ng quát, n u G là đ th có n đ nh, m c nh và k thành ph n liên thông thì ápổ ế ồ ị ỉ ạ ầ
d ng th t c v a mô t đ i v i m i thành ph n liên thông c a G, ta thu đ c đ thụ ủ ụ ừ ả ố ớ ỗ ầ ủ ượ ồ ị
g i là r ng khung c a G. S c nh b lo i b trong th t c này b ng mọ ừ ủ ố ạ ị ạ ỏ ủ ụ ằ −n+k, s này kýố
hi u là ệν(G) và g i là chu s c a đ th G.ọ ố ủ ồ ị
6.2.2. Bài toán tìm cây khung nh nh t:ỏ ấ Bài toán tìm cây khung nh nh t c a đỏ ấ ủ ồ
th là m t trong s nh ng bài toán t i u trên đ th tìm đ c ng d ng trong nhi uị ộ ố ữ ố ư ồ ị ượ ứ ụ ề
88
lĩnh v c khác nhau c a đ i s ng. Trong ph n này ta s có hai thu t toán c b n đự ủ ờ ố ầ ẽ ậ ơ ả ể
gi i bài toán này. Tr c h t, n i dung c a bài toán đ c phát bi u nh sau.ả ướ ế ộ ủ ượ ể ư
Cho G=(V,E) là đ th vô h ng liên thông có tr ng s , m i c nh eồ ị ướ ọ ố ỗ ạ ∈E có tr ngọ
s m(e)ố≥0. Gi s T=(Vả ử T,ET) là cây khung c a đ th G (Vủ ồ ị T=V). Ta g i đ dài m(T)ọ ộ
c a cây khung T là t ng tr ng s c a các c nh c a nó:ủ ổ ọ ố ủ ạ ủ
m(T)=
∑
∈T
E
)(
e
em
.
Bài toán đ t ra là trong s t t c các cây khung c a đ th G, hãy tìm 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 và bàiỏ ấ ư ậ ượ ọ ỏ ấ ủ ồ ị
toán đ t ra đ c g i là bài toán tìm cây khung nh nh t.ặ ượ ọ ỏ ấ
Đ minh ho cho nh ng ng d ng c a bài toán cây khung nh nh t, d i đây làể ạ ữ ứ ụ ủ ỏ ấ ướ
hai mô hình th c t tiêu bi u cho nó.ự ế ể
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 t b t c m t thành ph nàoườ ắ ố ố ể ừ ấ ứ ộ ố
đ n b t kỳ m t trong s các thành ph còn l i. M t khác, trên quan đi m kinh t đòiế ấ ộ ố ố ạ ặ ể ế
h i là chi phí v xây d ng h th ng đ 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 h th ng đ ng s t n i hai thành ph .ộ ạ ự ệ ố ườ ắ ố ố
Bài toán n i m ng máy tính:ố ạ C n n i m ng m t h th ng g m n máy tính đánh s t 1ầ ố ạ ộ ệ ố ồ ố ừ
đ n n. Bi t chi phí n i máy i v i máy j là m(i,j) (thông th ng chi phí này ph thu cế ế ố ớ ườ ụ ộ
vào đ dài cáp n i c n s d ng). Hãy tìm cách n i m ng sao cho t ng chi phí là nhộ ố ầ ử ụ ố ạ ổ ỏ
nh t. Bài toán này cũng d n v bài toán tìm cây khung nh nh t.ấ ẫ ề ỏ ấ
Bài toán tìm cây khung nh nh t đã có nh ng thu t toán r t hi u qu đ gi iỏ ấ ữ ậ ấ ệ ả ể ả
chúng. Ta s xét hai trong s nh ng thu t toán nh v y: thu t toán Kruskal và thu tẽ ố ữ ậ ư ậ ậ ậ
toán Prim.
6.2.3. Thu t toán Kruskal:ậThu t toán s xây d ng t p c nh Eậ ẽ ự ậ ạ T c a cây khung nhủ ỏ
nh t T=(VấT, ET) theo t ng b c. 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 Eả ủ ọ ố ắ ầ ừ T=∅, 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 Eạ ệ ổ ậ T 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 Eẽ ế ượ ậ T g m nồ−1 c nh. C th có th mô t nh sau:ạ ụ ể ể ả ư
1. B t đ u t đ th r ng T có n đ nh.ắ ầ ừ ồ ị ỗ ỉ
2. S p x p các c nh c a G theo th t không gi m c a tr ng s .ắ ế ạ ủ ứ ự ả ủ ọ ố
3. B t đ u t c nh đ u tiên c a dãy này, ta c thêm d n các c nh c a dãy đã đ cắ ầ ừ ạ ầ ủ ứ ầ ạ ủ ượ
x p vào T theo nguyên t c c nh thêm vào không đ c t o thành chu trình trong T.ế ắ ạ ượ ạ
89
4. L p l i B c 3 cho đ n khi nào s c nh trong T b ng nặ ạ ướ ế ố ạ ằ −1, ta thu đ c cây khungượ
nh nh t c n tìm.ỏ ấ ầ
Thí d 2:ụ Tìm cây khung nh nh t c a đ th cho trong hình d i đây:ỏ ấ ủ ồ ị ướ
B t đ u t đ th r ng T có 6 đ nh.ắ ầ ừ ồ ị ỗ ỉ
S p x p các c nh c a đ th theo th t không gi m c a tr ng s :ắ ế ạ ủ ồ ị ứ ự ả ủ ọ ố
{(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}.
Thêm vào đ th T c nh (vồ ị ạ 3, v5).
Do s c nh c a T là 1<6ố ạ ủ −1 nên ti p t c thêm c nh (vế ụ ạ 4, v6) vào T. Bây gi sờ ố
c nh c a T đã là 2 v n còn nh h n 6, ta ti p t c thêm c nh ti p theo trong dãy đã s pạ ủ ẫ ỏ ơ ế ụ ạ ế ắ
x p vào T. Sau khi thêm c nh (vế ạ 4, v5) vào T, n u thêm c nh (vế ạ 5, v6) thì nó s t o thànhẽ ạ
v i 2 c nh (vớ ạ 4, v5), (v4, v6) đã có trong T m t chu trình. Tình hu ng t ng t cũng xãyộ ố ươ ự
ra đ i v i c nh (vố ớ ạ 3, v4) là c nh ti p theo trong dãy. Ti p theo ta b sung c nh (vạ ế ế ổ ạ 1, v3),
(v2, v3) vào T và thu d c t p Eượ ậ T g m 5 c nh:ồ ạ
{(v3, v5), (v4, v6), (v4, v5), (v1, v3), (v2, v3)}.
Tính đúng đ n c a thu t toán:ắ ủ ậ Rõ ràng đ th thu đ c theo thu t toán có nồ ị ượ ậ −1 c nhạ
và không có chu trình. Vì v y theo Đ nh lý 6.1.3, nó là cây khung c a đ th G. Nh v yậ ị ủ ồ ị ư ậ
ch còn ph i ch ra r ng T có đ dài nh nh t. Gi s t n t i cây khung S c a đ thỉ ả ỉ ằ ộ ỏ ấ ả ử ồ ạ ủ ồ ị
mà m(S)<m(T). Ký hi u eệk là c nh đ u tiên trong dãy các c nh c a T xây d ng theoạ ầ ạ ủ ự
thu t toán v a mô t không thu c S. Khi đó đ th con c a G sinh b i cây S đ c bậ ừ ả ộ ồ ị ủ ở ượ ổ
sung c nh eạk s ch a m t chu trình duy nh t C đi qua eẽ ứ ộ ấ k. Do chu trình C ph i ch aả ứ
c nh e thu c S nh ng không thu c T nên đ th con thu đ c t S b ng cách thay c nhạ ộ ư ộ ồ ị ượ ừ ằ ạ
e c a nó b i eủ ở k, ký hi u đ th này là S’, s là cây khung. Theo cách xây d ng,ệ ồ ị ẽ ự
m(ek)≤m(e), do đó m(S’)≤m(S), đ ng th i s c nh chung c a S’ và T đã tăng thêm m tồ ờ ố ạ ủ ộ
so v i s c nh chung c a S và T. L p l i quá trình trên t ng b c m t, ta có th bi nớ ố ạ ủ ặ ạ ừ ướ ộ ể ế
đ i S thành T và trong m i b c t ng đ dài không tăng, t c là m(T)ổ ỗ ướ ổ ộ ứ ≤m(S). Mâu thu nẩ
này ch ng t T là cây khung nh nh t c a G.ứ ỏ ỏ ấ ủ
Đ ph c t p c a thu t toán Kruskal đ c đánh giá nh sau. Tr c tiên, ta s pộ ứ ạ ủ ậ ượ ư ướ ắ
x p các c nh c a G theo th t có chi u dài tăng d n; vi c s p x p này có đ ph cế ạ ủ ứ ự ề ầ ệ ắ ế ộ ứ
t p O(pạ2), v i p là s c nh c a G. Ng i ta ch ng minh đ c r ng vi c ch n eớ ố ạ ủ ườ ứ ượ ằ ệ ọ i+1
không t o nên chu trình v i i c nh đã ch n tr c đó có đ ph c t p là O(nạ ớ ạ ọ ướ ộ ứ ạ 2). Do
p≤n(n−1)/2, thu t toánậ
90
v2
v3
v1
v4
v5
v6
v1
v2
v3
v4
v5
v6
33
17
18 16
4
9
8
14
20
Kruskal có đ ph c t p là O(pộ ứ ạ 2).
6.2.4. 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.ệ ả ơ ậ ượ ọ ươ ậ ầ ấ
1. VT:={v*}, trong đó v* là đ nh tuỳ ý c a đ th G.ỉ ủ ồ ị
ET:=∅.
2. V i m i đ nh vớ ỗ ỉ j∉VT, tìm đ nh wỉj∈VT sao cho
m(wj,vj) = min m(xi, vj)=:βj
xi∈VT
và gán cho đ nh vỉj nhãn [wj, βj]. N u không tìm đu c wế ợ j nh v y (t c là khi vư ậ ứ j không kề
v i b t c đ nh nào trong Vớ ấ ứ ỉ T) thì gán cho vj nhãn [0, ∞].
3. Ch n đ nh vọ ỉ j* sao cho
βj* = min βj
vj∉VT
VT := VT ∪ {vj*},
ET := ET ∪ {(wj*, vj*)}.
N u |VếT| = n thì thu t toán d ng và (Vậ ừ T, ET) là cây khung nh nh t.ỏ ấ
N u |VếT| < n thì chuy n sang B c 4.ể ướ
4. Đ i v i t t c các đ nh vố ớ ấ ả ỉ j∉VT mà k v i về ớ j*, ta thay đ i nhãn c a chúng nh sau:ổ ủ ư
N u ếβj > m(vj*, vj) thì đ t ặβj:=m(vj*, vj) và nhãn c a vủj là [vj*, βj]. Ng c l i, taượ ạ
gi nguyên nhãn c a vữ ủ j. Sau đó quay l i B c 3.ạ ướ
Thí d 3:ụ 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.ượ ở ậ ọ ố
∞
∞
∞
∞
∞
∞
∞
∞
14182111191218
14172321202032
18173430211920
21233422293423
11213022131319
19202129133316
12201934133315
18322023191615
.
Yêu c u vi t các k t qu trung gian trong t ng b c l p, k t qu cu i cùng c n đ aầ ế ế ả ừ ướ ặ ế ả ố ầ ư
ra t p c nh và đ dài c a cây khung nh nh t.ậ ạ ộ ủ ỏ ấ
91
ABCDEF H
A
I
B
C
D
E
F
H
I