Đồ thị và các thuật toán - Chương 4

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

86
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 4 Cây

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị và các thuật toán - Chương 4

Chu.o.ng 4 ˆ CAY Mo. d` u ˙ ¯ˆ ’a 4.1 Cˆy l` mˆt trong nh˜.ng kh´i niˆm quan trong nhˆ t cua l´ thuyˆt d` thi, v` thu.`.ng xuˆ t ´’ ´ˆ ´ a˙y aao u ae e ¯o . a o a . . . .ng l˜nh vu.c ´ c´ liˆn quan dˆn d` thi. ´ ¯ˆ . hiˆn trong nh˜ e u a . ıt o e ¯e o . Trong chu.o.ng n`y, tru.´.c hˆt s˜ nghiˆn c´.u cˆy Huﬀman v` nh˜.ng u.ng dung cua n´ ´ ˙o ’ a oee eua au´ . . liˆu. Kˆ tiˆp ch´ng ta x´t tr` b`y c´c thuˆt to´n t` cˆy bao tr`m, cˆy ´´ trong viˆc n´n d˜ e e e u. ee u e ınh a a a a ım a u a . . .o.ng nho nhˆ t khi c´c canh cua d` thi d u.o.c gˇn v´.i c´c chi ph´ (trong ´ ´ ˙ ’a ˙ ¯ˆ . ¯ . a o a ’o bao tr`m c´ trong lu . u o. a. ı . lu.o.ng). Cˆy bao tr`m nho nhˆ t cua d` thi c´ nhiˆu u.ng dung trong nh˜.ng tru.`.ng ho.p c´c ˙ a ˙ ¯ˆ . o ` ´ ´’o ’ a u e u o .a . . .`.ng dˆ n (ˆng dˆ n ga, dˆy dˆ n trong mang d iˆn, v.v) d u.o.c su. dung dˆ’ nˆi n d iˆ’m v´.i ˙o ˙ ˜o ˜ ˜ ´ ´ ˙. ’ du o ¯ a a aa ¯e ¯. ¯e ¯e o . . nhau theo c´ch tˆt nhˆ t: tˆ’ng khoang c´ch cua c´c d u.`.ng dˆ n l` nho nhˆ t. Nˆu n d iˆ’m ˙ ˙ ˜ ´ ´o ´ ´ ˙’ ˙ a ¯o ’ ˙ ’ a o a a aa a e ¯e d u.o.c nˆi v´.i nhau trˆn mˆt mˇt phˇng, ta c´ thˆ’ biˆ’u diˆn bo.i mˆt d` thi d` y d u trong d o ˙˙ ˙’ ˜ ´ ˙ ’ o ¯o . ¯ˆ ¯ ˙ ’ ¯. o o e oa a oee e .ˆ a ¯´ . . ˙ ng c´ch gi˜.a hai d iˆ’m tu.o.ng u.ng. Khi d ´ cˆy bao tr`m v´.i trong ˙ ’ c´c chi ph´ canh l` khoa a ı. a a u ¯e ´ ¯o a u o . lu.o.ng nho nhˆ t s˜ cho mang giao thˆng v´.i chi ph´ ´ nhˆ t. Nˆu c´ thˆ’ nˆi thˆm ngo`i n ˙´ e ´ ´ ´ ˙ ’ae o o ı ıt a e o eo a . . d iˆ’m cho ph´p, ta c´ thˆ’ thˆm ch´ xˆy du.ng d u.o.c mang v´.i ch´ ph´ re ho.n v` x´c d inh n´ ˙ ˙. ı ı˙ ’ ¯e e oea ıa ¯. o a a ¯. o . . ch´ l` giai quyˆt b`i to´n Steiner. B`i to´n sau n`y s˜ d u.o.c d` cˆp o. phˆn cuˆi chu.o.ng. ´ a e ¯ . ¯ˆ a ˙ ` ´ ınh a ˙ ’ e.’ eaa aa a o Dinh ngh˜ 4.1.1 C´c d inh ngh˜ sau cua cˆy (vˆ hu.´.ng) l` tu.o.ng d u.o.ng: -. ˙a ’ ıa a ¯. ıa oo a ¯ -ˆ . e 1. D` thi liˆn thˆng c´ n d ınh v` (n − 1) canh. o ¯˙ ’ o o a . -ˆ . e 2. D` thi liˆn thˆng khˆng c´ chu tr` o o o o ınh. 3. D` thi m` moi cˇp d ınh d u.o.c nˆi v´.i nhau bo.i mˆt v` chı mˆt dˆy chuyˆn so. cˆ p. - ˆ . a . a ¯˙ ¯ . o o ´ ` ´ ’ ˙ ’ oa˙oa ’. o e a . . 4. D` thi liˆn thˆng v` khi b´.t mˆt canh bˆ t k` th` mˆ t t´ liˆn thˆng. -ˆ . e ´ ´ o o a o o. a y ı a ınh e o . http://www.ebook.edu.vn 99
. a o ˙ ¯˙ ’ ’ H` 4.1 minh hoa cˆy c´ bay d ınh v` s´u canh. ınh aa . v2 • . . ... ... ... ... ... ... ... ... .. .. ... ... ... ... • v3 ... ... ... ... . ... ... ... . ... ... ... ... ... ... ... .. ... ... ... ... . . ... . ... ... ... ... ... ... ... ... ... ... ... v1 • v4 • .. .. .. .. .. .... ... .. . ..... .... . .. ..... . ..... .. ...... . .. .. ...... . . ..... .... . .. .. .... . .... ... . .. ... . .... .. .... ... . . ... .... .... .. . ... .. . .... .... ... .... . .. ... .... . .. . ... • v5 ..... • ... ..... .. .. .. . .. . .. .. v6 .. .. .. .. .. .. .. .. .. • v7 .. . . o ı.`a H` 4.1: Mˆt v´ du vˆ cˆy. ınh e . Kh´i niˆm vˆ cˆy nhu. mˆt thu.c thˆ’ cua to´n hoc d u.o.c d u.a ra lˆn d` u tiˆn bo.i ˙’ `a ` ¯ˆ e˙ ˙ ’ a e e o a . ¯. ¯ a a e . . . .i d inh ngh˜ c´c mach co. ban d u.o.c su. dung trong phˆn t´ c´c ˙ ¯. ˙ . ’ ’ Kirchhoﬀ [37] khi liˆn hˆ v´ ¯. e eo ıa a a ıch a . . ˙ ’ mang d iˆn. Khoang 10 nˇm sau d o, mˆt c´ch d oc lˆp, Cayley [11] d a ph´t hiˆn lai c´c cˆy ¯e a ¯´ o a ¯ˆ a ¯˜ a e.aa . . . .. . v` nh˜.ng t´ chˆ t cua n´ khi nghiˆn c´.u c´c t´ chˆ t ho´ hoc cua c´c chˆ t d` ng phˆn ´’o ´ ´ˆ ıch a ˙ ˙a ’ au e u a ınh a a. a ¯o a ˙ a hydrocarbon. ’ cu Cˆy c´ gˆc (c`n goi l` cˆy gia pha) d u.o.c d .nh ngh˜ tu.o.ng tu. nhu. sau: ´ o .aa ˙ ¯ . ¯i ’ a oo ıa . Dinh ngh˜ 4.1.2 Cˆy c´ gˆc T l` d` thi c´ hu.´.ng khˆng mach m` moi d ınh, ngoai tr`. -. ´ a . ¯˙ ’ ıa a oo a ¯o . o o ˆ o u . . ˙ ’ ` ´’ o ¯˙’ ˙ ¯˙ ’’ ao ˙ a mˆt d ınh (chˇng han v1 ), c´ bˆc trong bˇ ng mˆt: bˆc trong cua d ınh v1 (goi l` gˆc cua cˆy) a oa a o a . . . . . . bˇ ng khˆng; n´i c´ch kh´c, moi d ınh v ∈ T tˆn tai duy nhˆ t mˆt d u.`.ng d i t`. gˆc dˆn v. ` `. ´ o ¯o ´´ ¯˙ ’ a o oa a o a ¯ u o ¯e . . H` 4.2 minh hoa mˆt d` thi l` cˆy c´ gˆc v´.i d ınh v1 l` gˆc. T`. d .nh ngh˜ suy ra ´ ´ o ¯o . a a o o o ¯˙ ’ ınh .ˆ ao u ¯i ıa . .´.ng trˆn c´c ` rˇ ng cˆy c´ gˆc n d ınh c´ (n − 1) cung v` l` d` thi liˆn thˆng (khi bo qua hu o ´ ¯˙’ ˙ ’ a a oo o a a ¯ˆ . e o o ea cung). Cˆn ch´ y rˇ ng, c´ thˆ’ d .nh hu.´.ng trˆn mˆt cˆy (vˆ hu.´.ng) sao cho d` thi thu d u.o.c ˙ ` ` a u´ a o e ¯i o e oa oo ¯o . ˆ ¯. . .´.ng c´c ˙ ’ ´ ˙` ´ ’a o ¯˙ .’ l` cˆy c´ gˆc: Ta chı cˆn chon mˆt d ınh tu` y, chˇng han v1 , l`m gˆc v` d .nh hu o aa oo y´ a a o a ¯i a . . ` n t`. v1 dˆn c´c d ınh treo. Ngu.o.c lai, nˆu bo qua c´c hu.´.ng trˆn cˆy ´ a ¯˙ ´ ’ ˙ ’ cung theo dˆy chuyˆ u a e ¯e e a o ea .. c´ gˆc ta thu d u.o.c mˆt cˆy. ´ oo ¯. oa . Cˆy gia pha m` trong d o mˆ i ngu.`.i d an ˆng biˆ’u thi mˆt d ınh v` c´c cung d u.o.c v˜ ˙ ˜ ˙a ’ . o ¯˙ .’ a ¯´ o o ¯` o e aa ¯. e . c´c cha dˆn c´c con cua ho l` mˆt v´ du quen thuˆc cua cˆy c´ gˆc, gˆc cua cˆy l` ngu.`.i ´ ´o˙aa ´’ ˙ ’ .a o ı . o ˙ a oo ’ t` a u ¯e a o . . ˙ x´c d .nh d u.o.c. ’ a ¯i d` u tiˆn trong d`ng ho m` c´ thˆ ¯a ˆ e o . ao e ¯. http://www.ebook.edu.vn 100
v1 • .... .... ... ..... ... ..... ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... . . .... ... ... .... .... .. .... .... ... .. .. . ... ... ... ... . ... ... ... ... ... . ... ... ... ... ... . ... ... v2 v3 ... ... . ... ... ... ... . ... ... ... ... . • • ... ... ... ... . . ........ .. ... ..... ... ... ... ..... . ... ... ..... ... ... ... ... ... . . . .... .... .... .... ... ... ... . ... ..... .. . .... .. ... . .... .. ... ... ... ... ... ... ... . . ... ... v6 ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... . . ... ... • • • • ... ... ... ... ... ... . . ....... . ........ . ... ... v4 v5 v7 ... ... . .... .... ... . ... .. .. .... .... .... ... ... ... ... v8 ... ... ... ... ... ... ... .. ... • • ... ... ... . ....... . ........ .. ... ... v9 ... ... . .... .... .. ... .... .. .... .... ... .. ... ... ... .. v10 ... ... ... ... ... ... ... ... • • ... ... ... ... . ....... ...... . ... ... ... .... v11 . . ... .... ... ... .... .... . .... .... .. . ... . ... ... ... ... ... ... ... ... ... ... ... • • ... ... .. .. v12 v13 o ı.`a oo ´ H` 4.2: Mˆt v´ du vˆ cˆy c´ gˆc. ınh e . 4.2 Cˆy Huﬀman a ´ ` o˙ .’ Tiˆn tr` g´n d˜y c´c bit cho c´c k´ hiˆu goi l` m˜ ho´. Trong phˆn n`y ch´ng ta mˆt ta e ınh a a a a ye .aa a aa u . ´t quen thuˆc-thuˆt to´n m˜ ho´ Huﬀman. mˆt thuˆt to´n m˜ ho´ rˆ o a a a aa o a a aa . . . . ´ 4.2.1 C´c bˆ m˜ “tˆt” a oao . Khi ta n´i vˆ m˜ ho´ c´ ngh˜ l` g´n d˜y c´c bit cho c´c phˆn tu. cua mˆt bang ch˜. c´i. o` a ao ` a˙˙ ’’ o˙ ’ e ıa a a a a a ua . ˜i nhi phˆn goi l` bˆ m˜ v` c´c phˆn tu. cua ch´ng goi l` t`. m˜. Mˆt bang ` ˙˙ ’’ o˙ ’ Tˆp c´c chuˆ aa o .a .ao aaa a u . au a . . . . c´i l` mˆt tˆp ho.p c´c k´ hiˆu, goi l` c´c k´ tu.. Chˇng han, bang ch˜. c´i su. dung ˙ ’ ˙ ’ ua ˙ . ’ ch˜ a a o a u aye .aa y. a .. . . . . thu.`.ng, 26 k´ tu. hoa, v` c´c dˆ u ngˇt cˆu ´ ` eaa a´ ´ ` ´ trong hˆu hˆt c´c s´ch (tiˆng Anh) gˆm 26 k´ tu e o y. o y. aa a aa . dˆ u phˆ’y). M˜ ASCII (viˆt tˇt cua c´c ch˜. c´i d` u tiˆn cua chuˆi American Standard ˙ ´´ ’ ˜ ´ ea˙a u a ¯ˆ e ˙ ’ (nhu a a a a o . A l` 01000001, cua k´ tu. a l` 01100001 v` k´ ˙ y. ’ ˙ y. ’ Code for Information Interchange cua k´ tu a a ay . , l` 0011010. Ch´ y rˇ ng trong m˜ ASCII sˆ c´c bit su. dung dˆ’ biˆ’u diˆn c´c k´ tu. l` ˙e ˙ ` ˜ a y.a ´a ˙. ’ tu a u´ a a o ¯e e . bˇ ng nhau. M˜ nhu. vˆy goi l` m˜ c´ d ˆ d`i cˆ d. nh. Nˆu ta muˆn giam sˆ c´c bit d `i hoi ` ´ ´ ´ ´ ˙ ’ ¯o ˙ ’ a a a . a a o ¯o a o ¯i e o oa . . ˙ biˆ’u diˆn c´c thˆng b´o kh´c nhau, ta cˆn c´c chuˆi bit biˆ’u diˆn k´ tu. c´ d o d`i (n´i ’e ˙ ˙ ˜a ˜ ˜ y . o ¯ˆ a `a dˆ ¯e e o a a a o e e o . ` ng nhau. Nˆu biˆ’u diˆn c´c bit d`i ho.n cho c´c k´ tu. thu.`.ng xuyˆn xuˆ t ˙ ˜a ´ ´ chung) khˆng bˇo a e e e a a y. o e a hiˆn v` ngu.o.c lai, ch´ng ta c´ thˆ’, vˆ trung b` ˙e ınh, giam sˆ bit biˆ’u diˆn c´c k´ hiˆu. Chˇng ˙ ˜aye ˙ ’ oe` ´ ˙ ’ ea u o e e a . .. . han, m˜ Morse [31] su. dung c´c t`. m˜ ngˇn ho.n cho c´c k´ tu. xuˆ t hiˆn thu.`.ng xuyˆn: ´ ´e ˙. ’ a auaa a y. a o e . . a˙ ’˙ ’ ˙ ’ ˙ ’ m˜ cua cua a l` ·−, cua e l` ·, trong khi cua z l` − − · · · · , q l` − − ·−, j l` · − − − . a a a a a Tuy nhiˆn d o d`i trung b` cua m˜ khˆng phai l` tiˆu chuˆ’n quan trong khi thiˆt kˆ ˙ ´´ ınh ˙ ’ ˙ae ’ e ¯ˆ a ao a ee . . http://www.ebook.edu.vn 101
mˆt bˆ m˜ “tˆt”. X´t v´ du sau. Gia su. bang ch˜. c´i gˆm bˆn k´ tu. a1 , a2 , a3 , a4 v´.i c´c ´ ua` ´ ˙˙˙ ’’’ ooao eı. o o y. oa .. .o.ng u.ng l` P (a ) = 1 , P (a ) = 1 , P (a ) = 1 , P (a ) = 1 . Entropy cua ´ ´e ˙ ’ x´c suˆ t xuˆ t hiˆn tu a a a ´ a . 1 2 3 4 2 4 8 8 m˜ nguˆn n`y l` 1.75 bit/k´ hiˆu (xem [31] dˆ’ c´ kh´i niˆm vˆ entropy). X´t c´c bˆ m˜ ˙ ` ` a oaa ye ¯e o a e e eaoa . . . ` n n`y cho bo.i bang sau ˙˙ ’’ trong nguˆ a o C´c k´ tu. a y. M˜ C1 a M˜ C2 a M˜ C3 a M˜ C4 a a1 1 1 1 1 a2 1 0 01 10 a3 0 11 001 100 a4 01 00 000 1000 -o a Dˆ d`i trung b` ınh 1.125 1.125 1.75 1.875 . Dˆ d`i trung b` l cua mˆ i m˜ x´c d inh bo.i -o a ˜ ˙ ’ ˙ ’ ınh o a a ¯. . 4 l= P (ai )n(ai ) (bit/k´ hiˆu), ye . i=1 trong d o n(ai ) l` sˆ c´c bit cua t`. m˜ ai . ´ ˙ua ’ ¯´ aoa Du.a trˆn d o d`i trung b` ´ ´ a` ˙o ’ ˙ ’ e ¯ˆ a ınh, m˜ C1 l` tˆt nhˆ t. Tuy nhiˆn, c´c m˜ cˆn phai c´ kha a ao a e a a . . .`.i nhˆn c´ thˆ’ hiˆ’u d u.o.c r˜ r`ng. Hiˆ’n nhiˆn m˜ C ˙˙ ˙ ` nˇng truyˆn thˆng tin sao cho ngu o a e o a o e e ¯. oa e e a1 . .o.c g´n l` 1 nˆn khi nhˆn d u.o.c khˆng c´ t´ chˆ t n`y: V` ca hai k´ hiˆu a1 v` a2 d` u d u . a a ´ ı˙’ o o ınh a a ye a ¯ˆ ¯ e e a ¯. . . thˆng tin l` 1, ngu.`.i nhˆn khˆng thˆ’ phˆn biˆt d ´ l` k´ hiˆu a1 hay a2 . Ch´ng ta muˆn ˙a ´ o a o a o e e ¯o a y e u o . . . .o.c g´n duy nhˆ t mˆt t`. m˜. ˜ ´ oua mˆi k´ hiˆu d u . a oye¯ a . . M˜ C2 c´ c´c k´ tu. d u.o.c g´n c´c chuˆi bit kh´c nhau cho c´c k´ tu.. Tuy nhiˆn, gia ˜ ˙ ’ a oa y .¯. a a o a a y. e . m˜ ho´ d˜y a a a d u.o.c 011 v` gu.i d i chuˆi bit n`y. Ngu.`.i nhˆn chuˆ i 011 c´ mˆt sˆ ˜ ˜ .´ ˙ ’ a˙¯ ’ su a a a 2 1 1 ¯ . o a o a o ooo . - iˆu n`y c´ ngh˜ l` mˆt d˜y d u.o.c m˜ ho´ v´.i bˆ m˜ C2 c´ch giai m˜: a2 a1 a1 hoˇc a2 a3 . D ` ˙ ’a a a eao ıa a o a ¯ . a ao o a . . . th` d˜y n`y c´ thˆ’ d u.o.c giai m˜ khˆng tr`ng v´.i thˆng b´o ban d` u. N´i chung, d ˆy khˆng ˙ ˙ao ’ ı a a o e¯ . u o o a ¯a ˆ o ¯a o ˙ a ¯` ´ ´´ ´ ´ ’ ˙ ’ phai l` d iˆu ch´ng ta mong muˆn khi thiˆt kˆ c´c bˆ m˜. Ch´ng ta muˆn c´ t´ chˆ t giai e u o e ea o a u o o ınh a . ´t; t´.c l` moi d˜y c´c t`. m˜ chı c´ duy nhˆ t mˆt c´ch giai m˜. C´ thˆ’ ch´.ng ˙u ´oa ˙o ’ ˙ ’a m˜ duy nhˆ u a . a a u a a a a oe . ´ ˙ a ınh a a ’ minh c´c m˜ C3 v` C4 thoa m˜n t´ chˆ t n`y. a a a Mˇc d` viˆc kiˆ’m tra t´ duy nhˆ t khi giai m˜ l` kh´, ta c´ thˆ’ ch´.ng minh t´ ˙ ˙ ´ ˙’ aue e ınh a aa o oeu ınh . . .a trˆn thuˆc t´ cua bˆ m˜: khˆng c´ t`. m˜ n`o trong m˜ C ´t n`y cho bˆ m˜ C3 du ˙oa ’ chˆ a a oa e o ınh o ou aa a3 . . . . l` “tiˆn tˆ” cua t`. m˜ kh´c. Bˆ m˜ nhu. vˆy goi l` m˜ tiˆn tˆ. Mˆt c´ch d o.n gian dˆ’ kiˆ’m ˙˙ a`o˙uaa e´’ a .a a` o e´ ˙ ¯e e ’ oa oa¯ . . . tra mˆt bˆ m˜ c´ phai l` tiˆn tˆ hay khˆng ta v˜ cˆy nhi phˆn (mˆi d ınh c´ bˆc ≤ 2) tu.o.ng ˜’ ˙a` o e´ ’ o ¯˙ o o ao o ea .a oa .. . u.ng v´.i bˆ m˜. Cˆy d u.o.c v˜ xuˆ t ph´t t`. mˆt n´t d o.n (n´t gˆc) v` mˆ i n´t trong c´ bˆc ˜ ´ ´ ´ o o a a¯. e a a u o u¯ uo aou oa . . . .n hoˇc bˇ ng hai. Mˆt trong hai nh´nh con tu.o.ng u.ng bit 1 v` nh´nh c`n lai a` ˙ ’ ngo`i nho ho a a o a ´ aa o. . . http://www.ebook.edu.vn 102
tu.o.ng u.ng bit 0. Dˆ’ thuˆt tiˆn, ta quy u.´.c nh´nh con bˆn phai tu.o.ng u.ng 0 v` nh´nh con -e˙ ˙ ’ ´ ae o a e ´ aa . . .o.ng u.ng 1. Theo c´ch n`y, c´c cˆy nhi phˆn tu.o.ng u.ng c´c m˜ C , C v` C cho bˆn tr´i tu e a ´ a aaa a ´ a a2 3a4 . trong H` 4.3. (Dˆ’ d o.n gian, ta s˜ khˆng v˜ c´c m˜i tˆn trong c´c cˆy nhi phˆn). -e ¯ ˙ ˙ ’ ınh eo ea ue aa .a • ... ... ... ... 1.................... . . ... .. ... ... • •............... .. . .. . ...... . ... ..... ... ..... ... a1 ................0 1 0 ... ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... • • • • ... .. . .. . ... ... . ..... ...... ...... ... ... ... ... ... ..... ... ..... ... ..... ... ..... a1 a2 0... ... 1 0 1 ... 0 ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... . . . . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... ... ... • • • • • ... ... . ... ... .. .. ... ... ... ... .... ... .. ... ... . ... ... ... ... ..... ... .. ..... ... ... 1 a1 a2 0 a2 a3 0 ... ... . ... ... 1 0 ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... ... ... . . . ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... . ... . ... ... ... ... ... ... ... ... ... • • • • • ... ... ... ... ... ... ... ... .. .. a3 a4 a3 a4 a4 M˜ C2 a M˜ C3 a M˜ C4 a H` 4.3: ınh u´ ` ` ´ Ch´ y rˇ ng ngo`i n´t gˆc, cˆy nhi phˆn c´ hai loai n´t: c´c n´t l´ c´ bˆc ngo`i bˇ ng a auo a .ao .u a uaoa aa . . m˜ chı tu.o.ng o a` o a u e´ khˆng; v` c´c n´t trong c´ bˆc ngo`i kh´c khˆng. Trong bˆ m˜ tiˆn tˆ, c´c t` a ˙ ’ o aa u oa a a o . . .ng c´c n´t l´. M˜ C khˆng phai l` m˜ tiˆn tˆ do tˆn tai t`. m˜ tu.o.ng u.ng n´t trong. ˙a a` o ´ ` ’ u ´ a ua a4 o e o.ua ´ u Duyˆt cˆy t`. gˆc dˆn c´c n´t l´ cho ta biˆ’u diˆn chuˆi bit tu.o.ng u.ng k´ hiˆu. Mˆ i nh´nh ˙ ˜ ˜ ˜ ´´ e a u o ¯e a u a e e o ´ ye o a . . . m˜ cua n´: bit 1 cho nh´nh tr´i v` bit 0 cho nh´nh phai. d ong g´p mˆt bit v`o t` a ˙ o ’ ˙ ’ ¯´ o o au a aa a . M˜ tiˆn tˆ luˆn luˆn d u.o.c giai m˜ duy nhˆ t nhu.ng ngu.o.c lai khˆng d ung (chˇng han ˙ ’ a` o o e´ ´ ˙a ’ o¯. a o ¯´ a .. . .ng minh rˇ ng bˆ m˜ c´ thˆ’ giai m˜ duy nhˆ t tu.o.ng d u.o.ng m˜ C4 ). Tuy nhiˆn c´ thˆ’ ch´ ˙ ˙’ ` ´ o ao e ˙ a eoeu a a a ¯ . v´.i m˜ tiˆn tˆ theo ngh˜ sˆ trung b` c´c bit biˆ’u diˆn c´c k´ hiˆu bˇ ng nhau. ˙ ˜aye` o a` o e´ ´ ıa: o ınh a e e .a 4.2.2 M˜ Huﬀman a M˜ Huﬀman l` m˜ tiˆn tˆ v` tˆi u.u v´.i c´c x´c xuˆ t cho tru.´.c. Phu.o.ng ph´p xˆy du.ng a a` oaoe´ ´ ´ a oaa a o aa . m˜ Huﬀman du.a trˆn hai quan s´t sau: a e a . 1. Trong mˆt bˆ m˜ tˆt u.u, c´c k´ hiˆu xuˆ t hiˆn thu.`.ng xuyˆn (c´ x´c suˆ t hay tˆn sˆ ´ ´e ´ `o a´ o o ao aye a o e oa a .. . . ´t hiˆn l´.n) s˜ c´ c´c t`. m˜ ngˇn ho.n c´c k´ hiˆu ´ xuˆ t hiˆn. ´ ´e xuˆ a eo eoa u a a a y e ıt a . . . 2. Trong mˆt bˆ m˜ tˆt u.u, hai k´ hiˆu xuˆ t hiˆn ´ nhˆ t s˜ c´ c´c t`. m˜ c`ng d o d`i. ´ ´ e ıt a e o a u a u ¯ˆ a ´ o o ao ye a .. . . . Dˆ’ xˆy du.ng m˜ Huﬀman, ch´ng ta c´ thˆ’ biˆ’u diˆn qua cˆy nhi phˆn m` c´c n´t l´ -e a ˙ ˙˙ ˜ a u oee e a .a aa ua . .o.ng u.ng c´c k´ hiˆu. Duyˆt cˆy nhi phˆn s˜ cho ta c´c t`. m˜ cua bˆ m˜: xuˆ t ph´t t`. ´ aua˙ oa ’ tu ´ aye ea .ae a au . . . http://www.ebook.edu.vn 103
n´t gˆc v` d i dˆn c´c n´t l´, thˆm bit 1 v`o t`. m˜ mˆi lˆn qua nh´nh tr´i v` bit 0 mˆ i lˆn ˜a ˜a ´ ´ a u a o` o` u o a ¯ ¯e a u a e a aa .i cˆy trong H` 4.4, ta c´ biˆ’u diˆn c´c k´ tu. qua c´c t`. m˜ nhu. sau: ˙ ˜ a y. ˙ ’ qua nh´nh phai. V´ a a o ınh oe e aua K´ tu. y. M˜ ho´ aa A 1 O 00 R 010 S 0110 T 0111 • ..... ...... ... ..... ... ..... 1................... 0 ... ... ... ... ... ... . . . ... ... ... ... ... . ... ... ... • • ... .. .. . ..... ...... ... .... ... .... 1 0 ... ... A ... ... . ... ... ... ... . . ... ... ... ... ... ... ... ... ... . ... ... ... • • ... ... . .... ..... . .. . ... ... ... .... . 1 0 ... ... O ... ... .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... • • ... ... . .... ..... .. . . ... ... ... .... . ... 1 0 ... R ... ... .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... • • ... ... ... .. . T S H` 4.4: ınh Dˆ’ giai m˜ mˆt chuˆi bit, ch´ng ta bˇt d` u t`. gˆc v` di chuyˆ’n doc theo cˆy cho dˆn -e ˙ a o ˙’ ˙. ˜ ´ˆ ´ ´ o u a ¯a u o a e a ¯e . .: d i theo nh´nh tr´i nˆu d ´ l` bit 1, ngu.o.c lai d i theo nh´nh phai. Chˇng ˙ ’ ´ ˙ ’ khi gˇp k´ tu ¯ a y. a a e ¯o a . .¯ a a . ˜ han, chuˆi bit o . 01010111 .o.ng u.ng t`. RAT. V´.i mˆt cˆy x´c d inh m˜ Huﬀman nhu. H` 4.4, chuˆi bit bˆ t k` d u.o.c ˜ ´ tu ´ u o o a a ¯. a ınh o a y¯ . . . tu.o.ng u.ng v´.i nh˜.ng chuˆi bit c´ d ˆ d`i thay d o’i. ˙ ˜ ´ a ua y. ˙’a giai m˜ duy nhˆ t mˇc d` c´c k´ tu a ´ o u o o ¯o a ¯ˆ . . Huﬀman d a chı ra thuˆt to´n xˆy du.ng m˜ Huﬀman t`. bang c´c tˆn sˆ xuˆ t hiˆn cua a` o a a´´e˙ ¯˜ ˙ ’ u˙ ’ ’ a aa a . . . . nhu. sau: c´c k´ tu a y. Thuˆt to´n xˆy du.ng m˜ Huﬀman a a a a . . X´t chuˆ i cˆn m˜ ho´ s t`. n k´ tu. v´.i n ≥ 2. ˜a o` e aau y.o 1. Xˆy du.ng d˜y tˆn sˆ fi , i = 1, 2, . . . , n, xuˆ t hiˆn cua c´c k´ tu. trong chuˆi s. ˜ a`o a´ ´ e ˙ a y.’ a a o . . http://www.ebook.edu.vn 104
2. Nˆu n = 2 (gia su. f1 ≤ f2 ), xuˆ t cˆy nhu. trong H` 4.5 v` d`.ng. ´ ´ ˙˙ ’’ e aa ınh au • . .. ... ... ... ..... ... ..... ... ... ... ... ... ... ... ... ... 1 0 ... . . ... ... ... ... ... ... ... ... . ... ... ... ... . ... ... ... ... ... . ... ... ... ... ... . ... ... ... ... . • • ... ... .. .. f1 f2 H` 4.5: ınh 3. Gia su. f v` f l` hai tˆn sˆ nho nhˆ t v` f ≤ f . Tao mˆt danh s´ch tˆn sˆ m´.i bˇ ng `oo` `o a´˙aa ´ a´ ˙˙ ’’ ’ a a o a a . . .i f + f . Goi thuˆt to´n n`y su. dung danh s´ch tˆn sˆ m´.i dˆ’ tao ˙ ` o o ¯e . a´ ˙ ’ aa˙. ’ c´ch thay f v` f bo a a a a . . cˆy T . Thay d ınh d u.o.c g´n nh˜n f + f dˆ’ nhˆn d u.o.c cˆy T trong H` 4.6. Xuˆ t T. ˙. ´ ¯˙ ¯ . a ’ a a ¯e a ¯ . a ınh a • .. .. ... ..... ... ..... ... ... ... ... ... ... ... ... ... ... ... 1 0 ... . . ... ... ... ... ... ... ... ... . ... ... ... ... . ... ... ... ... ... . ... ... ... ... ... . ... ... ... ... • • . ... ... .. . f f H` 4.6: ınh `o a´ ˙ ’ V´ du 4.2.1 Cho bang tˆn sˆ ı. K´ tu. `o a´ y. tˆn sˆ A 2 B 3 C 7 D 8 E 12 Khi d o cˆy Huﬀman tu.o.ng u.ng cho trong H` 4.7. ¯´ a ´ ınh 4.3 Cˆy bao tr` m a u Ch´ng ta d a nghiˆn c´.u riˆng biˆt c´c t´ chˆ t cua mˆt cˆy, trong muc n`y ch´ng ta s˜ ´’ e a ınh a ˙ u ¯˜ eu e oa .a u e . . .u cˆy khi gˇn n´ nhu. mˆt d` thi con cua mˆt d` thi kh´c. Ch´ng ta biˆt rˇ ng ´ e` ´a ˙ ’ nghiˆn c´ a eu ao o ¯o . ˆ o ¯o . a ˆ u . . cho d` thi c´ m canh, c´ thˆ’ xˆy du.ng d u.o.c 2m d` thi con kh´c nhau; r˜ r`ng l` trong sˆ ˙ ´ ¯ˆ . o o o ea ¯. ¯o . ˆ a oa a o . . http://www.ebook.edu.vn 105
• .... .... .. .... .. .... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... . ... ... ... ... 1 0 . ... ... ... ... ... . ... ... ... ... ... . ... ... ... ... . ... ... ... ... . ... ... ... ... . ... ... ... ... ... . ... ... ... ... ... . ... ... • • .. .. . . ....... . ...... ...... ... ... . ... ... ... .... ... ..... ... ..... . 1 0 1 0 ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... . . . . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... • • • • ... .. .. . .. .. ..... . ...... . . . ... ... ... .... . 1 0 ... 7 8 12 ... ... ... . ... ... ... ... .. . ... ... ... ... ... ... ... ... ... C D E ... ... ... • • ... .. .. .. 2 3 A B H` 4.7: ınh d o c´ mˆt v`i d` thi con l` mˆt cˆy. Ch´ng ta quan tˆm dˆn mˆt loai cˆy d ac biˆt: “cˆy ´ ¯´ o o a ¯ˆ . o aoa u a ¯e o . a ¯ˇ e a . . . . . ` n d` u tiˆn d u.o.c su. dung v` ph´t triˆ’n l´ thuyˆt vˆ ˙y ´` e¯. ˙ . ’ bao tr`m”. Kh´i niˆm cˆy bao tr`m lˆ ¯a u ae a uaˆ aa e ee . cˆy bo.i nh` vˆt l´ ngu.`.i Du.c Kirchoﬀ nˇm 1847. Kirchoﬀ d a su. dung cˆy bao tr`m nhˇ m o -´ ` ˙ ’ ¯˜ ˙ . ’ a aay a a u a . .o.ng tr` tuyˆn t´ dˆ’ x´c d inh cu.`.ng d o d`ng d iˆn trong mˆ i nh´nh v` ˙ a ¯. ˜ ´ ˙ ea ’. giai hˆ c´c phu ınh e ınh ¯e o ¯ˆ o ¯ e o a a . . ˙ a mˆt mang d iˆn. ’ xung quanh mach cu o ¯e . . . . -ˆ . V´ du 4.3.1 D` thi trong H` 4.8(a) c´ cˆy bao tr`m trong H` 4.8(b). ı. o ınh oa u ınh e e b b • • • • ................................................ ............................................ . ... . ............................................... ............................................ ...... ... .. ... .... ... . ... .... ... . ... .. . ... ... . ... ... ... . ... . ... ... ... ... ... ... ... ... . ... ... . . ... ... ... ... ... ... ... . ... . . ... ... ... ... ... ... ... . ... . . ... ... ... ... ... ... ... ... . . . ... ... ... ... ... ... ... . ... . . ... ... ... . ... . ... ... ... ... .... . . ... .. ... ... . ... .. . . ... .. . ... a• •c a• •c .. ............................................... ... ................................................ . . ... .. . .. ............................................... ............................................... .. . . ... ... . ... .... . ... ... . ... ... . ... ... ... ... . ... ... ... ... . ... ... ... ... . ... ... ... . ... ... ... ... . ... ... ... . ... ... ... ... . ... ... ... ... . ... ... ... . ... ... ... ... . ... ... ... . ... ... ... . ... ... ... ... ... . ... ... ... ... . ... . ... ... ... ... ... ... . ... ... ... . ... ... . ... ... ... ... ... ... . ... ... ... ... . ... . ... ... .... ... ... ... . ... ... ... . ... . ... ... ... ... ... ... . ... ... ... • • • • ... ... .. .. .............................................. .. .............................................. . f f d d (a) (b) H` 4.8: ınh Dinh ngh˜ 4.3.2 Cˆy T d u.o.c goi l` cˆy bao tr`m cua d` thi liˆn thˆng G nˆu T l` d` -. ´ ˙ ¯o . e ’ˆ ıa a ¯. .aa u o e a ¯o ˆ .a tˆ t ca c´c d ınh cua G. u´’ thi con cua G v` T ch´ a ˙ a ¯˙ ˙ ’ ’ ˙ ’ a . -. -ˆ . Dinh l´ 4.3.3 D` thi G = (V, E ) c´ d` thi bˆ phˆn l` mˆt cˆy nˆu v` chı’ nˆu G liˆn ´ ´ o ¯ˆ . o a a o a e a ˙ e y o o e . . . .´.c mˆt d` thi liˆn thˆng v` c´ n d ı’nh, bao gi`. ta c˜ng c´ thˆ’ ˙ a o ¯˙ thˆng. N´i c´ch kh´c, cho tru o o oa a o ¯ˆ . e o o o u oe . ˙ d u.o.c mˆt cˆy ch´.a tˆ t ca c´c d ı’nh cu a G (cˆy c´ n d ı’nh). ’¯ . .´ ´’ ˙¯ o o . ’ ˙ ’ u a ˙ a ¯˙ ˙ ’ a o ¯˙ bo d i mˆt sˆ canh cu a G dˆ ¯e oa . http://www.ebook.edu.vn 106
Ch´.ng minh. Diˆu kiˆn cˆn. Nˆu G liˆn thˆng th` ta thu. t` xem c´ canh n`o m` khi x´a -` e` ´ ˙ ım ’ u e .a e e o ı o. a a o d i khˆng l`m cho d` thi mˆ t t´ liˆn thˆng khˆng. Nˆu khˆng c´ mˆt canh n`o nhu. vˆy ´ ´ ¯ o a ¯ˆ . a ınh e o o o e o oo. a a . . th` G l` mˆt cˆy; nˆu c´ mˆt canh nhu. vˆy th` x´a n´ d i, v` ta lai d i t` mˆt canh m´.i dˆ’ ˙ ´ ı aoa eoo. a ı o o¯ a ¯ ım o . o ¯e . . . . . .i khi khˆng thˆ’ x´a mˆt canh n`o d u.o.c n˜.a th` ta c´ mˆt cˆy m` tˆp ho.p c´c ˙o x´a... Cho t´ o o o e o. a¯. u ı ooa aa .a . . . ` ¯˙’ ˙ o ¯´ ’ d ınh cua n´ d ung bˇ ng V. a Diˆu kiˆn d u. Gia su. a, b l` hai d ınh trong G v` do d o thuˆc cˆy bao tr`m T cua G. Khi -` e ¯˙ ’ ˙˙ ’’ ¯˙’ ˙ ’ e a a ¯´ oa u . . d o tˆn tai dˆy chuyˆn µ trong T t`. a dˆn b. Suy ra µ c˜ng thuˆc G. Vˆy G liˆn thˆng. ¯´ ` . a ` ´ o e u ¯e u o a e o . . Ch´ng ta s˜ su. dung thuˆt to´n t` kiˆm theo chiˆu rˆng dˆ’ xˆy du.ng cˆy bao tr`m ˙ ´ ` o ¯e a e˙ . ’ u a a ım e e. a u . . cua d` thi liˆn thˆng. ˙ ¯ˆ . e ’o o ´ ` 4.3.1 Thuˆt to´n t` kiˆm theo chiˆu rˆng x´c d .nh cˆy bao tr` m a a ım e eo a ¯i a u . . Trong thuˆt to´n n`y, S k´ hiˆu l` mˆt d˜y. a aa yeaoa . . . Nhˆp: D` thi liˆn thˆng G := (V, E ) v´.i c´c d ınh d u.o.c d ´nh sˆ th´. tu. a -ˆ . e ´ o a ¯ ˙ ¯ . ¯a ’ o o o u. . v1 , v 2 , . . . , v n . ´ Xuˆ t: Cˆy bao tr`m T. a a u 1. [Kho.i tao] Dˇt S := [v1 ] v` T l` d` thi gˆm d ınh v1 v` khˆng c´ canh. K´ hiˆu v1 l` ˙ . -a a ¯ˆ . ` ¯˙ ’ ’ a o o ao o. ye a . . ´c. ¯˙’ d ınh gˆ o 2. [Thˆm canh] V´.i mˆ i x ∈ S, theo th´. tu., thˆm canh (x, y ) ∈ E v` d ınh y (theo th´. ˜ a ¯˙’ e o o u. e u . . .) v`o T nˆu T ∪ (x, y ) khˆng tao th`nh chu tr` ınh. Nˆu khˆng c´ canh nhu. vˆy, ´ ´ tu a e o a e o o. a . . . d`.ng. T l` cˆy bao tr`m. u aa u 3. [Cˆp nhˆt S ] Thay S bo.i con (trong T ) cua S theo th´. tu.. Chuyˆ’n sang Bu.´.c 2. ˙ ˙ ’ ˙ ’ a a u. e o . . - e ım a Dˆ’ t` cˆy bao tr`m cua d` thi liˆn thˆng ta c`n c´ thˆ’ d`ng thuˆt to´n t` kiˆm ˙ ˙ ´ ˙ ¯o . e ’ u ˆ o o o eu a a ım e . . sau: ` u sˆu (c`n goi l` quay lui) nhu theo chiˆ a e o .a ´ ` 4.3.2 Thuˆt to´n t` kiˆm theo chiˆu sˆu x´c d .nh cˆy bao tr` m a a ım e ea a ¯i a u . Nhˆp: D` thi liˆn thˆng G := (V, E ) v´.i c´c d ınh d u.o.c d ´nh sˆ th´. tu. a -ˆ . e ´ o a ¯ ˙ ¯ . ¯a ’ o o o u. . v1 , v 2 , . . . , v n . ´ Xuˆ t: Cˆy bao tr`m T. a a u http://www.ebook.edu.vn 107
1. [Kho.i tao] Dˇt w := v1 v` T l` d` thi gˆm d ınh v1 v` khˆng c´ canh. K´ hiˆu v1 l` ˙ . -a a ¯ˆ . ` ¯˙ ’ ’ a o o ao o. ye a . . ´ ¯˙’ d ınh gˆc. o 2. [Thˆm canh] Chon canh (w, vk ) v´.i chı sˆ k nho nhˆ t sao cho viˆc thˆm canh n`y v`o ’´ ´ ˙o ˙a ’ e o e e aa . . . . . ˙n sang Bu.´.c 3. Ngu.o.c lai, thˆm ’ ´ `. T khˆng tao ra chu tr` o ınh. Nˆu khˆng tˆn tai, chuyˆ e o o e o e . .. canh (w, vk ) v` d ınh vk v`o T ; d at w := vk v` chuyˆ’n sang Bu.´.c 2. ˙ a ¯˙’ a ¯ˇ a e o . . 3. [Kˆt th´c?] Nˆu w = v1 , thuˆt to´n d`.ng, T l` cˆy bao tr`m. ´ ´ e u e a au aa u . 4. [Quay lui] Dˇt x l` cha cua w (trong T ); g´n w := x v` chuyˆ’n sang Bu.´.c 2. -a ˙ ˙ ’ a a a e o . V´ du 4.3.4 D` thi trong H` 4.9(a) c´ c´c cˆy bao tr`m, H` 4.9(b) v` 4.9(c), d u.o.c -ˆ . ı. o ınh oa a u ınh a ¯. .ng theo c´c thuˆt to´n t` kiˆm theo chiˆu rˆng v` chiˆu sˆu tu.o.ng u.ng. ´ `o a`a xˆy du a a a a ım e e. e ´ . . a a a • • • .... ... .... ... .. . ... .... ... .... ... ... .... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. •c •c •c b• b• b• ............................... . .. . ... ................................ .................................... .. ... .. ..................................... .. ... .. ..... .. . .... .. .... . . . ..... .... .. .... . .... .. ... . . ... . ... ... . ... ... . .. . .. . .. . . . .. ... . ... ... . ..... ... . ... ... ... . .... ... . ..... ... . .... ... . . .. . .. . . . . ... ... . ... . ... . ... ... . ... . ... . ... . . .... ... ... ... ... ... ... ... ... ... ... ... . . . ... ... ... ... . ... ... . . . ... ... ... ... . ... . . . . ... ... ... ... ... . . . ... ... ... ... . ... ... ... ... ... ... . . . . ... . . . . ... ... ... ... ... ... . . . ... ... ... ... ... ... . . . . ... ... ... ... . . . . d• • •f d• • •f d• • •f ... . . . . ... ... ... .... .... .. .. .. ... . . . . .. .. .. . . . . . . ... .. ... .... . ... . . . . . .. . . ... ... ... ... ... . . . . ... ... ..... ... ... ... . . . . ... ... ... . . . . ... ... ... ... . . . ... e e e . ... ... ... ... . . . ... . ... ... ... ... . . . . ... ... ... ... ... . . . ... ... ... ... . ... . . . ... ... . ... ... . . . . ... ... . .... ... . .... ... ... . . . . ... . .... ... ... . ... ... . .... . . ... . . .. ... . . . .. ... ... . ... . .. ... . .. ... . ... ... ... . ... . . ... .... ... .... . . .. ....... . . ... . ... . . .. ... . ... . .. . . . ..................................... ..................................... . . • • • • • • ... ............................... ..... .. . . . ................................ . . .... . ... . . .. ... ... ... ... ... . ... .. ... ... . ... ... ... ... ... j j j ... i i i ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... .... ... ... ... • • • ... ... ... .. .... ... k k k (a) (b) (c) H` 4.9: (a) D` thi G. (b) Cˆy bao tr`m sinh bo.i thuˆt to´n t` kiˆm theo chiˆu rˆng. (c) -ˆ . ´ `o ˙ ’ ınh o a u a a ım e e. . .i thuˆt to´n t` kiˆm theo chiˆu sˆu. ´ `a ˙ ’ Cˆy bao tr`m sinh bo a u a a ım e e . T` cˆy bao tr` m du.a trˆn hai ma ng tuyˆn t´ ´ ˙ ’ 4.3.3 ım a u e e ınh . - e a ¯a a Dˆ’ c`i d ˇt c´c thuˆt to´n t` kiˆm theo chiˆu rˆng v` chiˆu sˆu trˆn d` thi liˆn thˆng G ˙ ´ `o a`a a a ım e e. e e ¯o . e ˆ o . . . liˆu ma trˆn kˆ hay cai biˆn, mang c´c danh t` cˆy bao tr`m T ta c´ thˆ’ d`ng cˆ u tr´c d˜ e ˙ ´ a` ˙e ’ ˙ ’ ım a u o eu a u u. .e a ` Vout []. Tuy nhiˆn, trong tru.`.ng ho.p d` thi d u.o.c biˆ’u diˆn bo.i hai mang tuyˆn t´ ˙ ˜ ´ ˙ ’ ˙ ’ s´ch kˆ a e e o . ¯o . ¯ . ˆ e e e ınh .n. Ngo`i ra, phu.o.ng ph´p sau n`y c˜ng cho ta ´. ˙ ’ α v` β th` c´ch tiˆp cˆn sau s˜ hiˆu qua ho a ıa ea ee a a au . .ng” (tˆp c´c cˆy bao tr`m) ch´.a (n − p) canh trong tru.`.ng ho.p d` thi c´ p > 1 mˆt “r` o u aaa u u o . ¯o . o ˆ . . . ` n liˆn thˆng. Hiˆ’n nhiˆn, v´.i nh˜.ng thuˆt to´n xˆy du.ng cˆy bao tr`m ta c´ thˆ’ ˙ ˙ th`nh phˆ e a a o e e o u a aa a u oe . . kiˆ’m tra d` thi c´ liˆn thˆng hay khˆng, v` nˆu n´ khˆng liˆn thˆng th` c´ thˆ’ x´c d .nh c´c ˙ ˙ ´ e ¯o . o e ˆ o o ae o o e o ı o e a ¯i a ` n liˆn thˆng. Nˆu mˇt kh´c, d` thi c´ trong sˆ th` ch´ng ta c´ thˆ’ t` cˆy bao ˙ ım a ´ ´ıu th`nh phˆ e a a o e a a ¯o . o . ˆ o oe . tr`m c´ tˆ’ng trong lu.o.ng nho nhˆ t (xem Phˆn 4.4). Ho.n n˜.a ch´ng ta c˜ng c´ thˆ’ xˆy ˙ ˙ ´ ` ˙ ’ u oo a a u u u o ea . . .ng hˆ c´c chu tr` d oc lˆp du.a trˆn cˆy bao tr`m cua d` thi nhu. trong Phˆn 4.3.4. ` ˙ ¯o . ’ˆ du ea ınh ¯ˆ a ea u a . . .. . http://www.ebook.edu.vn 108
X´t d` thi vˆ hu.´.ng G khˆng c´ khuyˆn n d ınh v` m canh. C´c d ınh d u.o.c g´n ¯˙ ’ a ¯˙ ’ e ¯ˆ . o o o o o e a ¯. a . nh˜n v1 , v2 , . . . , vn , v` d` thi x´c d .nh bo.i hai mang tuyˆn t´ α, β, trong d ´ αi v` βi , i = ´ ˙ ’ ˙ ’ a a ¯o . a ¯i ˆ e ınh ¯o a 1, 2, . . . , m, l` c´c d ınh d u.o.c liˆn thuˆc bo.i canh ei . a a ¯˙ ¯ . e ’ o˙. ’ . Mˆi bu.´.c lˇp cua thuˆt to´n, mˆt canh m´.i d u.o.c d u.a v`o kiˆ’m tra dˆ’ x´c d .nh c´c ˙ ˙ ˜ ˙ ’ o oa a a o. o¯. ¯ a e ¯e a ¯i a . . . .o.c thiˆt lˆp o. bu.´.c tru.´.c; bu.´.c ´ ´.’ ¯˙’ ˙ ’. ea˙ d ınh cua canh d o c´ xuˆ t hiˆn trong cˆy n`o d ´ (d ˜ d u . ¯´ o a e a a ¯o ¯a ¯ o o o . ˙. o d` u tiˆn ch´ng ta chu.a c´ cˆy bao tr`m n`o). O bu.´.c th´. i, 1 ≤ i ≤ m, khi kiˆ’m tra canh ’ ˙ ¯aˆ e u oa u a u e . .`.ng ho.p xay ra: ˙ ’ (αi , βi ) c´ nˇm tru o oa . 1. Nˆu ca hai d ınh khˆng nˇ m trong bˆ t c´. mˆt cˆy n`o d a d u.o.c xˆy du.ng o. (i − 1) ` ´˙ ´ ’ ¯˙ ’ ˙ ’ e o a a u o a a ¯˜ ¯ . a . . .´.c tru.´.c, khi d o c´c d ınh α , β d u.o.c g´n sˆ th`nh phˆn liˆn thˆng l` sˆ c, sau d o ´ ` ´ ¯´ a ¯˙ ’ bu o o ¯. a o a ae o ao ¯´ i i .n vi. tˇng c lˆn mˆt d o . a e o¯ . 2. Nˆu αi thuˆc cˆy Tj c`n βi thuˆc cˆy Tk (j, k = 1, . . . , c v` j < k ), canh th´. i d u.o.c ´ e oa o oa a u ¯. . . . . dung dˆ’ nˆi hai cˆy n`y; do d ´, moi d ınh trong cˆy T d u.o.c g´n l` sˆ th`nh phˆn ˙o ¯e ´ ´ ` ˙ ’ . ¯˙ ’ su . aa ¯o a k¯ . a a o a a ˙ a Tj . Gi´ tri c giam mˆt d o.n vi. ’ ˙ ’ liˆn thˆng cu e o a. o¯ . . 3. Nˆu ca hai d ınh c`ng nˇ m trong mˆt cˆy, th` canh (αi , βi ) c`ng v´.i mˆt sˆ canh kh´c ` ´’ .´ e˙ ¯˙ ’ u a oa ı. u o oo. a . . l´ tru.`.ng ho.p n`y. ˙ a e. ’ ˙ ’ cua cˆy s˜ tao th`nh mˆt chu tr` v` do d o khˆng xu y a o ınh a ¯´ o o a . . 4. Nˆu d ınh αi thuˆc cˆy Tj c`n βi khˆng thuˆc cˆy n`o, khi d ´ canh (αi , βi ) d u.o.c thˆm ´’ e ¯˙ oa o o oaa ¯o . ¯. e . . ` ´ ` ˙ ’ ¯˙ ’ v`o cˆy Tj bˇ ng c´ch g´n sˆ th`nh phˆn liˆn thˆng cua Tj cho d ınh βi . aa a a aoa ae o 5. Nˆu d ınh βi thuˆc cˆy Tk c`n αi khˆng thuˆc cˆy n`o, khi d o canh (αi , βi ) d u.o.c thˆm ´’ e ¯˙ oa o o oaa ¯´ . ¯. e . . ` ´ ` ˙ ’ ¯˙ ’ v`o cˆy Tk bˇ ng c´ch g´n sˆ th`nh phˆn liˆn thˆng cua Tk cho d ınh αi . aa a a aoa ae o Dˆ’ thu.c hiˆn viˆc kiˆ’m tra c´c d ınh cuˆi cua mˆt canh d u.o.c khao s´t c´ xuˆ t hiˆn -e˙. ˙ ´’ ´e a ¯˙ ’ o˙ ˙aoa ’ e e e o. ¯. . . . . .ng mˆt mang tuyˆn t´ n phˆn tu. Vertex[]. Khi mˆt ´ ınh `˙ ˙’ ’ trong cˆy n`o khˆng, ch´ng ta xˆy du aa o u a o e a o . . . canh (vi , vj ) nˇ m trong cˆy th´. c th` c´c phˆn tu. th´. i v` j cua mang n`y d u.o.c d at l` c. ` ` a˙u ’ ˙ ’ ˙ ’ a a u ıa a a ¯ . ¯ˇ a . . Trong c´c qu´ tr` xu. l´ kˆ sau, khi mˆt canh kh´c (αi , βi ) d u.o.c d u.a v`o kiˆ’m tra, ˙ ´ a ınh ˙ y e ’ a o. a ¯. ¯ a e . . th´. α v` β trong mang Vertex[] c´ kh´c 0 khˆng. ch´ng ta chı cˆn kiˆ’m tra c´c phˆn tu u i a i ˙ ˙` ` ’a a˙ ’ ˙ ’ u e a oa o . th´. q trong mang Vertex[] bˇ ng 0 chı ra rˇ ng d ınh th´. q n`y khˆng nˇ m trong bˆ t ` ` ¯˙ ` ` ´ a˙ ’ ˙ ’ ˙ ’ ’ Phˆn tu u a a u a o a a . cˆy n`o. Kˆt th´c chu.o.ng tr` ´ ´a ` ˙ ng Vertex[] cho ch´ng ta biˆt c´c th`nh phˆn liˆn ’ c´ a a u e u ınh, ma u e a ae thˆng cua d` thi G. ˙ ¯o . ’ˆ o Nhˆn x´t rˇ ng, cˆy khˆng chı d u.o.c mˆ ta bo.i tˆp c´c d ınh. Bo.i vˆy, ch´ng ta cˆn c´ ` `o ˙¯ . ’ o ˙ ˙ a a ¯˙ ’’. ’ ˙a ’. aea a o u a . ˙ ng c´c canh dˆ’ xuˆ t d˜. liˆu. Dˇt mang n`y l` Edge[]. Nˆu canh th´. i nˇ m trong ˙ a u e -a ` ´ ´. ’ ˙ ’ mˆt ma o a. ¯e aa e u a . . . cˆy th´. c, ta c´ Edge[k ] = c; ngu.o.c lai, n´ d u.o.c d ˇt bˇ ng 0. Tˆ t ca c´c phˆn tu. 0 trong o ¯ . ¯a ` ´’ ` a ˙a a˙ ’ a u o a .. . .o.ng u.ng v´.i c´c khuyˆn cˆ lˆp (t´.c l` c´c canh khˆng nˇ m trong bˆ t c´. cˆy ` ´ua ˙ ’ mang n`y tu a ´ oa e oa u aa . o a a . bao tr`m hay r`.ng n`o). Mang n`y c`ng v´.i c´c mang α v` β, x´c d .nh duy nhˆ t cˆy bao ´ ˙ ’ ˙ ’ u u a au oa a a ¯i aa tr`m (hoˇc r`.ng) d u.o.c sinh bo.i thuˆt to´n n`y. ˙ ’ u au ¯. a aa . . http://www.ebook.edu.vn 109
Trong thuˆt to´n n`y, v`ng lˇp ch´ thu.c hiˆn m lˆn. Th`.i gian d `i hoi dˆ’ kiˆ’m tra ’˙˙ ` ¯o ˙ ¯e e a aa o a ınh . e a o . . . ` ´e ´ a ¯˙ ’ c´c d ınh c´ xuˆ t hiˆn trong cˆy hay khˆng l` hˇ ng sˆ-khˆng phu thuˆc v`o n v` m. Do d o oa a o aa oo oa a ¯´ . . . .i gian thu.c hiˆn thuˆt to´n tı lˆ v´.i m1 . Trong tru.`.ng ho.p m n, ta c´ thˆ’ giam th`.i ˙’ a ˙e o ’. oe˙ th` o e a o o . . . . .c hiˆn bˇ ng c´ch lu.u tr˜. mˆt biˆn dˆm sˆ c´c canh d u.o.c d at v`o cˆy. Khi biˆn ` ´ ¯e ´ ´a . ´ gian thu ea a uo e o ¯ . ¯ˇ a a e . . . . n`y d at gi´ tri (n − 1) chu.o.ng tr` s˜ kˆt th´c (nˆu d` thi liˆn thˆng; tr´i lai ta cˆn kiˆ’m ˙ ´ ´o ` a ¯. a. ınh e e u e ¯ˆ . e o a. a e tra moi canh). .. Thu tuc sau minh hoa thuˆt to´n t` cˆy bao tr`m du.a trˆn hai mang tuyˆn t´ α[] ´ ˙. ’ ˙ ’ a a ım a u e e ınh . . . v` β [] : a void SpaningTree() { byte i, j, Tempt, Count = 0; byte Vertex[MaxVertices], Edge[MaxEdges]; for (j = 1; j
Edge[i] = Vertex[alpha[i]]; Vertex[beta[i]] = Vertex[alpha[i]]; } else if (Vertex[alpha[i]] != Vertex[beta[i]]) { Edge[i] = Vertex[alpha[i]]; Tempt = Vertex[beta[i]]; for (j = 1; j
´’ a ım a ˙ a a 4.3.4 Thuˆt to´n t` tˆ t ca c´c cˆy bao tr` m a u . Viˆc phˆn t´ c´c mach d iˆn vˆ co. ban c´ thˆ’ d u.a vˆ b`i to´n t` tˆ t ca c´c cˆy bao tr`m ˙ . ¯e ` ` a a ım a ˙ a a ´’ ˙ o e¯ ’ e a ıch a .e e u . cua d` thi (xem [19]). Do tˆm quan trong cua n´, c´ nhiˆu thuˆt to´n kh´c nhau giai quyˆt ` ˙ oo ` ´ ˙ ¯o . ’ˆ ’ ˙ ’ a e a a a e . . .ng phu.o.ng ph´p l` ho´n d o’i c´c chu tr` nhu. sau: Xuˆ t ph´t ˙a ´ b`i to´n n`y. Mˆt trong nh˜ aaa o u a a a ¯ˆ ınh a a . t`. mˆt cˆy bao tr`m T n`o d ´. V´.i mˆ i canh khˆng nˇ m trˆn cˆy T, khi thˆm v`o cˆy n`y ˜ ` uoa u a ¯o o o . o a ea e aaa . ´o ´ ˙o. ’. s˜ tao ra duy nhˆ t mˆt chu tr` e. a ınh. X´a bo mˆt canh bˆ t k` trong chu tr` n`y s˜ cho ta o ay ınh a e . mˆt cˆy bao tr`m m´.i. oa u o . Do sˆ c´c cˆy bao tr`m l` rˆ t l´.n thˆm ch´ ca v´.i nh˜.ng d` thi nho, t´ hiˆu qua ´ ´ ı˙o’ ˙ ınh e ’ ˙ ’ oa a u aa o a u ¯o . ˆ . . ˙ a nh˜.ng thuˆt to´n giai quyˆt b`i to´n rˆ t quan trong (xem [14]). Mˆt tˆ’ng quan cua c´c ˙ ´aaa ´ ’ ˙ ’ ˙a ’ cu u a a e oo . . . phu.o.ng ph´p n`y l` mˆt luˆn ´n tiˆn s˜ cua Chase [12]. Chase d ˜ chı ra rˇ ng thuˆt to´n ` ´ e ı˙ ’ ¯a ˙ ’ aaao aa a a a . . . .a ra bo.i Minty c´ hiˆu qua nhˆ t: liˆn tiˆp thu gon d` thi bˇ ng c´c ph´p to´n xo´ mˆt ` ´ ´ ˙’ ˙ ’ du ¯ oe a e e . ¯ˆ . a o a e a ao . . canh v` ho.p nhˆ t c´c d ınh d` u cuˆi cua n´. T`. c´c cˆy bao tr`m cua c´c d` thi thu gon ´ ´’ a a ¯˙ ’ ¯a o ˙ o ua a ˙ a ¯o . ’ a. ˆ u ˆ . . (m` nho ho.n rˆ t nhiˆu) ta c´ thˆ’ du.ng d u.o.c tˆ t ca c´c cˆy bao tr`m cua d` thi ban d` u. ˙ ´ ` ´’ ˙ ’ ¯. a ˙a a ˙ ¯ˆ . ’o a a e oe. u ¯ˆ a Dˆ’ bao d am thuˆt to´n kˆt th´c, c´c d` thi c´ k´ thu.´.c du.´.i mˆt ngu.˜.ng cho tru.´.c s˜ - e ˙ ¯˙ ˙’ ´ ’ a ae u a ¯o . o ıch ˆ o o o o oe . . .o.c thu gon thˆm; thay v`o d ´ l` c´c cˆy bao tr`m cua ch´ng d u.o.c suy ra. ˙ ’ khˆng d u . o¯ e a ¯o a a a u u ¯. . Hˆ co. so. cua c´c chu tr` d oc lˆp ˙˙ ’’a 4.3.5 e ınh ¯ˆ a . .. Nhˇc lai rˇ ng chu sˆ cua d` thi vˆ hu.´.ng G c´ n d ınh, m canh, p th`nh phˆn liˆn thˆng ´ ` ´’ ˆ ` o ˙ ¯o . o o o ¯˙ ’ a.a a ae o . ` ng c(G) = m − n + p−ch´ l` sˆ cu.c d ai c´c chu tr` d oc lˆp. Phˆn du.´.i d ˆy ta xˆy ´ . ¯. a ` bˇ a ınh a o ınh ¯ˆ a a o ¯a a .. du.ng thuˆt to´n t` hˆ co. so. cua c´c chu tr` d oc lˆp du.a trˆn cˆy bao tr`m cua d` thi. ˙˙a ’’ ˙ ¯ˆ . ’o a a ım e ınh ¯ˆ a ea u . . . .. . Khˆng giam tˆ’ng qu´t, c´ thˆ’ gia thiˆt d` thi G liˆn thˆng, v` trong tru.`.ng ho.p tr´i lai, ˙ ˙’ ´ˆ ˙ ’ aoe˙ o o e ¯o . e o ı o a. . .ng th`nh phˆn liˆn thˆng. Y tu.o.ng o. d ˆy l` ´ ` ˙ ’ ˙ ¯a a ’ th` ta x´t t` ı eu a ae o 1. Xˆy du.ng cˆy bao tr`m T := (V, ET ). a a u . 2. Gia su. e1 , e2 , . . . , em−n+1 l` c´c canh cua E m` khˆng thuˆc cˆy T. Khi thˆm mˆt canh ˙˙ ’’ ˙ ’ aa . ao oa e o. . . bˆ t k` trong c´c canh n`y, chˇng han canh ek , v`o cˆy T ta d u.o.c mˆt v` chı mˆt chu ˙ ’ ´ oa˙o ’. ay a. a a aa ¯. . . . tr` µk . C´c chu tr` µ1 , µ2 , . . . , µm−n+1 l` d ˆc lˆp v` mˆ i chu tr` ch´.a mˆt canh ˜ ınh a ınh a ¯o a ı o ınh u o. .. . khˆng thuˆc c´c chu tr` kia; mˇt kh´c ta c´ (m − n + 1) = c(G) chu tr` nhu. vˆy, o oa ınh a a o ınh a . . . .o.c hˆ co. so. cua c´c chu tr` d ˆc lˆp. ˙˙a ’’ nˆn ta d ˜ x´c d .nh d u . e e ¯a a ¯i ¯ ınh ¯o a . .. Nhu. vˆy b`i to´n d u.a vˆ t` c´c chu tr` µk khi thˆm canh ek v`o cˆy T. Trong khi ` ım a a a a¯ e ınh e aa . . kiˆ’m tra canh ek = (αk , βk ) trong thuˆt to´n 4.3.3, nˆu d iˆu kiˆn 3 d ung (t´.c l` ca hai d ınh ˙ e ¯` ´ ua˙ ’ ¯˙’ e a a e e ¯´ . . . ´t hiˆn trong c`ng cˆy Ti ) th` thay cho viˆc loai bo canh n`y ch´ng ta cˆn t`` ım . ˙.’ αk v` βk xuˆ a a e u a ı e a u a . . c´c canh trong Ti m` tao th`nh dˆy chuyˆn gi˜.a hai d ınh αk v` βk . Dˆy chuyˆn n`y c`ng ` ` ¯˙’ a. a. a a e u a a eau v´.i canh (αk , βk ) tao th`nh mˆt chu tr` co. ban. Vˆ n d` ch´ o. d ay l` t` dˆy chuyˆn ´e ` ˙ ’ a ¯ˆ ınh ˙ ¯ˆ a ım a ’ o. a o ınh e . . http://www.ebook.edu.vn 112
n`y. C´ nhiˆu phu.o.ng ph´p hiˆu qua giai quyˆt b`i to´n, trong sˆ d ´ thuˆt to´n cua Paton o` ´ ´ ˙˙ ’’ a˙ ’ a e a e eaa o ¯o a . . ´ ˙ ’a [50] l` hiˆu qua nhˆ t. ae . Thuˆt to´n Paton t` hˆ co. so. cua c´c chu tr` d oc lˆp ˙˙ ’’a a a ım e ınh ¯ˆ a . . .. Ch´ng ta c˜ng s˜ kiˆ’m tra mˆ i canh c´ tao th`nh chu tr` v´.i nh˜.ng canh trong cˆy d u.o.c ˙ ˜ u u ee o. o. a ınh o u a¯. . .ng trong qu´ tr` thu.c hiˆn thuˆt to´n, nhu.ng thay viˆc lˆ y c´c canh theo th´. tu. ´ xˆy du a a ınh . e a a eaa. u. . . . . . trong Thuˆt to´n 4.3.3), ta chon mˆt d ınh z v` kiˆ’m tra c´c canh liˆn thuˆc v´.i ˙ o ¯˙ .’ tu` y (nhu y´ a a ae a. e oo . . . - ınh z l` d ınh v`.a d u.o.c thˆm v`o cˆy). Dˆ’ d o.n gian, ta s˜ su. dung ma trˆn kˆ A biˆ’u -e¯˙ ˙ ` ˙’ ˙ ’ ˙ ’ ˙. ’ n´. (D o a¯ u¯. e aa e ae e . .o.c xˆy du.ng o. bu.´.c n`o d o ˜ ¯o . y e diˆn d` thi. K´ hiˆu T l` tˆp hiˆn h`nh c´c d ınh trong cˆy d u . a a ¯˙’ ˙ ’ eˆ aa ea a¯ o a ¯´ . . . . .a d u.o.c kiˆ’m tra (t´.c l` nh˜.ng d ınh thuˆc T hoˇc khˆng nhu.ng ˙ a a a ¯˙ ’ ¯˙ ’ v` W l` tˆp c´c d ınh chu ¯ . a e uau o a o . . . c´ ´ nhˆ t mˆt canh liˆn thuˆc v´.i n´ chu.a d u.o.c kiˆ’m tra). ˙ ´o. o ıt a e ooo ¯. e . . Ch´ng ta kho.i d` u thuˆt to´n bˇ ng c´ch d at T = {v1 } v` W = V. Dınh v1 s˜ l` gˆc -˙ a` ´ ˙ ¯a ’ˆ ’ u a a a ¯ˇ a ea o . . ˙ a cˆy. Sau qu´ tr` kho.i tao, thu.c hiˆn c´c bu.´.c sau: ’a ˙. ’ cu a ınh ea o . . 1. Nˆu T ∩ W = ∅ thuˆt to´n d`.ng. ´ e a au . ´ . ¯˙ ’ 2. Nˆu T ∩ W = ∅ chon d ınh z ∈ T ∩ W. e 3. Kiˆ’m tra z bˇ ng c´ch x´t mˆ i canh liˆn thuˆc v´.i n´. Nˆu khˆng c´ canh n`o, khu. z ˙ ` ˜ ´ ˙’ e a a e o. e oooe o o. a . . W v` chuyˆ’n sang Bu.´.c 1. ˙ t` u a e o 4. Nˆu tˆn tai canh (z, p) ∈ E kiˆ’m tra z c´ thuˆc T khˆng. ˙ e`.. ´o e o o o . 5. Nˆu p ∈ T t` chu tr` co. ban gˆm canh (z, p) v` mˆt dˆy chuyˆn (duy nhˆ t) t`. ´ ˙` ` ´u ’o e ım ınh aoa e a . . z dˆn p trong cˆy d ang d u.o.c xˆy du.ng. Xo´ canh (z, p) khoi d` thi v` chuyˆ’n sang ˙ ´ ˙ ¯o . a ’ˆ ¯e a¯ ¯. a a. e . Bu.´.c 3. o 6. Nˆu p ∈ T thˆm canh (z, p) v`o cˆy v` d ınh p v`o T. Xo´ canh (z, p) khoi d` thi v` ´ a a a ¯˙ ’ ˙ ¯o . a ’ˆ e / e a a. . ˙n sang Bu.´.c 3. ’ chuyˆ e o Nhu. d a d` cˆp, vˆ n d` co. ban l` Bu.´.c 5. Ch´ng ta phai t` dˆy chuyˆn t`. z dˆn p ´e ` u ¯e ´ ˙a ’ ˙ ım a ’ ¯˜ ¯ˆ a e. a ¯ˆ o u e . thˆ n`o? Thu tuc sau s˜ tra l`.i cˆu hoi n`y. ´ ˙. ’ e ˙o a ’ ˙a ’ nhu e a Ch´ng ta su. dung mˆt ngˆn xˆp (stack) T W = T ∩ W dˆ’ lu.u tr˜. c´c d ınh trong cˆy ˙ ´ ˙. ’ u a ¯˙’ u o ae ¯e a . .ng chu.a d u.o.c kiˆ’m tra. Dınh d u.o.c thˆm gˆn d ay nhˆ t v`o cˆy s˜ d u.o.c ch`n v`o d` u -˙ ˙ ` ¯ˆ ´ a a e¯ . ’ ¯. nhu ¯. e e a a e a ¯a ˆ ngˆn xˆp. Mˆ i lˆn mˆt d ınh d u.o.c kiˆ’m tra d u.o.c lˆ y ra khoi t`. d ınh cua ngˆn xˆp. Ta su. ˙ ˜a ´ o` ´ ´ o ¯˙ ’ ¯. ˙ u ¯˙ ’ ’ ˙ ’ ˙ ’ ae e ¯. a ae . ´n t´ d ˆ d`i n : mang l[j ] l` khoang c´ch t`. gˆc v1 dˆn d ınh vj ´ ´ ¯˙ ˙’ ˙ ’ ˙ ’ ’ dung thˆm hai mang tuyˆ ınh ¯o a e e a a uo ¯e . . trong cˆy bao tr`m; v` Pred[j ] l` d ınh vi sao cho canh (vi , vj ) l` mˆt canh trong cˆy v´.i a ¯˙’ a u a ao. ao . . vi gˆn gˆc ho.n vj . N´i c´ch kh´c, Pred[j ] l` d ınh liˆn tru.´.c d ınh vj trong dˆy chuyˆn t`. ` ´ ` `u a ¯˙’ o ¯˙ ’ ao oa a e a e http://www.ebook.edu.vn 113
v1 dˆn vJ . Nh˜n l[J ] = −1 nˆu v` chı nˆu d ınh vj khˆng thuˆc tˆp T. Kho.i tao l[1] = 0 v` ´ ´ ’´ ’ e a ˙ e ¯˙ ˙. ’ ¯e a o oa a .. .i moi j = 2, 3, . . . , n. l[j ] = −1 v´ o . Trong Bu.´.c 5, khi x´t d ınh z v` canh (z, p) d u.o.c t` thˆ y v´.i p ∈ T. Dˆ’ x´c d .nh chu - e a ¯i ˙ ´ e ¯˙’ o a. ¯ . ım a o tr` co. ban sinh bo.i canh (z, p) ch´ng ta lˆn theo dˆy chuyˆn t`. z dˆn p trong cˆy bˇ ng a` ` ` u ¯e ´ ˙ ’ ˙. ’ ınh u a a e a ´. ´ ` ´ ´ c´ch t` liˆn tiˆp c´c “tiˆn bˆi” Pred[z ], Pred[Prede[z ]], . . . cho dˆn khi ch´ng ta bˇt gˇp a ım e ea eo ¯e u aa Pred[p]-tiˆn bˆi cua p. N´i c´ch kh´c, nhu. chı ra trong H` ??, chu tr` co. ban d u.o.c tao ` ´’ eo˙ ˙ ’ ˙ ¯. . ’ oa a ınh ınh ra l` a z, Pred[z ], Pred[Pred[z ]], . . . , Pred[p], p, z. Cˆn ch´ y rˇ ng tiˆn bˆi Pred[k ] cua moi d ınh k ∈ T l` mˆt d ınh m` hoˇc d ˜ d u.o.c ` ` ` ´ ˙ ’ . ¯˙’ a o ¯˙ ’ a u´ a eo a a ¯a ¯ . . . ˙m tra hoˇc d ang d u.o.c kiˆ’m tra. T´.c l`, nˆu k ∈ T ∩ W th` ’ ˙ ´ kiˆ e a¯ ¯. e uae ı . nhu.ng Pred[k ] ∈ T. Pred[k ] ∈ W / Thu tuc FundamentalCircuits() minh hoa c´c bu.´.c d a tr` b`y o. trˆn. ˙. ’ o ¯˜ ınh a ˙ e ’ .a Th`.i gian thu.c hiˆn cua thuˆt to´n bi chˇn trˆn bo.i nν trong d ´ gi´ tri thu.c ν ∈ [2, 3] e˙ ’ ˙ ’ o a a.a e ¯o a . . . . . . ´u tr´c cua d` thi c˜ng nhu. c´ch d anh nh˜n c´c d ınh [50]. ˙ ¯ˆ . u ’o ˙ ’ phu thuˆc v`o cˆ oaa u a ¯´ a a¯ . . Mˇc d` dˆ’ d o.n gian ch´ng ta d a gia su. G liˆn thˆng, tuy nhiˆn thuˆt to´n c´ thˆ’ ˙ ˙ ˙ ’ ¯˜ ˙ ˙ ’’ a u ¯e ¯ u e o e a aoe . . ˜ d`ng cai biˆn cho tru.`.ng ho.p tˆ’ng qu´t. D` u tiˆn, thuˆt to´n s˜ tao ra tˆ t ca c´c chu -ˆ ˙ ´’ ˙ ’e a ˙a dˆ a e o .o a a e a a e. . tr` co. ban trong th`nh phˆn liˆn thˆng ch´.a d ınh xuˆ t ph´t v1 . Sau d ´ ta chon d ınh y ` ´ ˙ ’ u ¯˙ ’ . ¯˙’ ınh a ae o a a ¯o .i y l` gˆc cua cˆy bao tr`m th´. hai. Thuˆt to´n lˇp lai cho dˆn ´ˆ m` l[y ] = −1 v` bˇt d` u v´ ´’ ´ ao ˙ a a a a ¯a o u u a aa. ¯e . . ´t ca c´c d ınh d u.o.c g´n nh˜n l kh´c −1. ˙ a ¯˙ ¯ . a ’ ’ khi tˆa a a Cˆy bao tr` m tˆi thiˆ’u ˙ ´ 4.4 a u o e Dinh ngh˜ 4.4.1 Gia su. G l` d` thi c´ trong sˆ. Cˆy bao tr`m tˆi thiˆ’u cua G l` mˆt -. ˙˙ ´a ´ ˙˙ ’’ ’ ıa a ¯o . o . ˆ o u o e ao . .i trong lu.o.ng nho nhˆ t. ´ ˙ ’ ˙ ’a cˆy bao tr`m cua G v´ a u o . . ˙ ’ ´ B`i to´n n`y rˆ t hay gˇp trong thˆng tin liˆn lac v` trong c´c ng`nh kh´c. Chˇng han aaaa a o e.a a a a a . . . sau: d ˆ d`i dˆy d iˆn ngˇn nhˆ t cˆn thiˆt dˆ’ nˆi n th`nh phˆ d a d inh ˙o ´ a` ´a e ¯e ´ ´ ´ ˙ ’ ta d at cˆu hoi nhu ¯ˇ a ¯o a a ¯ e a a o ¯˜ ¯. . . . l` bao nhiˆu? Khi d ´ coi c´c th`nh phˆ l` c´c d ınh cua d` thi v` w(a, b) l` khoang c´ch ´ o a a ¯˙ ’ ˙ ¯ˆ . a ’ ˙’ a e ¯o a a o a a .a c´c th`nh phˆ a v` b. Mang dˆy d iˆn cˆn phai liˆn thˆng, v` v` d o d`i ` ´ a ¯e ` ˙e ’ t´ bˇ ng km gi˜ a ınh a u a o a a o a ı ¯ˆ a . . . ’. ¯´ a o a ˙ ¯a ´ a ¯e ` ´ ` dˆy d iˆn cˆn ngˇn nhˆ t nˆn n´ khˆng c´ chu tr` a a aeoo o ınh: vˆy mang d o l` mˆt cˆy. O d ˆy ta cˆn a a . . . . ´i thiˆ’u” c´ thˆ’ d u.o.c v` l` mˆt d` thi bˆ phˆn cua d` thi d` y d u c´ n d ınh. ˙ ˙ ¯ . a a o ¯o . o a ˙ ¯ˆ . ¯a ¯ ˙ o ¯˙ ’o ’ ’ t` mˆt cˆy “tˆ ım o a o e oe .ˆ ˆ . . . Mˆt u.ng dung gi´n tiˆp: b`i to´n t` cˆy bao tr`m tˆi thiˆ’u l` bu.´.c trung gian trong viˆc ˙ ´ ´ o´ a e a a ım a u o eao e . . . .i giai cua b`i to´n ngu.`.i du lich-mˆt b`i to´n thu.`.ng xuˆ t hiˆn trong thu.c tˆ. ´e ´ ˙˙aa ’’ t` l` ım o o oaa o a e . . . . http://www.ebook.edu.vn 114
Cˆn ch´ y rˇ ng, cˆy bao tr`m tˆi thiˆ’u cua d` thi khˆng liˆn quan dˆn cˆy sinh bo.i ˙ ˙ ¯o . o ` ` ´ ´ ’ˆ ˙ ’ a u´ a a u o e e ¯e a . mˆt d ınh cho tru.´.c. Do d ´, d` thi trong H` 4.10(a), ´ ´’ ` ´ tˆ t ca c´c dˆy chuyˆn ngˇn nhˆ t t` o ¯˙ a ˙a a au.’ e a o ¯o ¯ˆ .o ınh v´.i c´c sˆ trˆn c´c canh tu.o.ng u.ng c´c trong lu.o.ng canh, cˆy sinh ra bo.i d u.`.ng d i ngˇn ´ ´ ˙ ¯o ’ oaoea. ´ a a ¯ a . . . ´t t`. d ınh cho tru.´.c, chˇng han v1 , trong H` 4.10(b); ngu.o.c lai, cˆy bao tr`m tˆi thiˆ’u ˙ ˙ ’ ´ ˙ ’ nhˆ u ¯ a o a ınh ..a uo e . cho trong H` 4.10(c). ınh v1 v1 v1 ..•.. ..•.. •. .... .. .... .. . ........ ........ . . . . . ... . ... ... . ... . . ... . ... ... . ... . . . . ... . .... .. ... ... . ... .. ... . . . ... . ... . . .. ... . ... ... .. ... . . . 5................... 5 ... . . . ... ... . . . ... ... ... . . . ... . ... . . ... ... ... . . . ... . ... . ... . . ... . ... ... . ... . . 3 . .. . . .. . ... . . ... ... . .. . ... . .. ... ... . . . . ... . ... . ... ... . ... ... . ... . . ... . . . ... . ... ... . ... . ... . ... ... . ... . . ... . . . ... ... . ... . ... ... . . ... ... . . . ... ... ... . . . ... . ... . ... ... . ... . . ... . . ... ... 3 3 ... . . ... . . ... ... . . ... . ... . ... ... . . ... .. . . .. . v4 • • v2 v4 • • v2 v4 • • v2 ... . • • • ................................................................... ... . . ... ... . . ... . . ................................................................... .. . ................................................................... .... .. . . .................................................................. .. . . . ... ... ... ... . ... v5 v5 v5 ... ... ... . ... ... . ... ... ... . ... ... ... . . . ... ... . ... ... ... ... ... ... . . . . ... ... ... . ... ... ... ... ... . . .. .. .. ... .. .. .. ... . . ... ... ... ... ... ... . ... ... . ... ... ... . ... ... ... ... . ... 5 . ... ... ... ... ... ... . ... ... . ... ... ... . ... ... ... ... . ... . ... ... ... ... ... ... . ... 5 3 ... . .. .. .. . .. .. .. ... . ... ... ... ... . ... ... ... . ... ... . ... . ..... ... ... ... . ..... ... ... ... ... . ... ... ... . ... ... . ... .. .. . . . • • • ... ... . ..... ... ... .... . v3 v3 v3 (a) (b) (c) H` 4.10: (a) D` thi G. (b) Cˆy sinh bo.i d u.`.ng d i ngˇn nhˆ t xuˆ t ph´t t`. v1 . (c) Cˆy bao -ˆ . ´ ´ ´ ˙ ¯o ¯ ’ ınh o a a a a au a ´ ˙ ’a tr`m nho nhˆ t. u T` cˆy bao tr`m tˆi thiˆ’u l` mˆt trong nh˜.ng b`i to´n cua l´ thuyˆt d` thi c´ thˆ’ ˙ ˙ ´ ´ˆ ˙y ’ ım a u o eao u aa e ¯o . o e . .o.c tao ra trong qu´ tr` xˆy du.ng giai quyˆt triˆt dˆ’. Do d o, d at Ti v` Tj l` hai cˆy con d u . . ˙ ´ ˙ ’ e e ¯e ¯´ ¯ˇ a a a ¯ a ınh a . . . .o.c su. dung dˆ’ biˆ’u diˆn tˆp c´c d ınh cua cˆy con th` ∆ cˆy bao tr`m tˆi thiˆ’u. Nˆu Ti d u . ˙ . ˙ ˙˙ ˜ a a ¯˙ ´ ´ ’ ’ ˙a ’ a uo e e ¯ ¯e e e. ı ij c´ thˆ’ d .nh ngh˜ l` khoang c´ch ngˇn nhˆ t t`. mˆt d ınh trong Ti dˆn mˆt d ınh trong Tj ; ˙ ´ ´ ´ ˙ ’ a u o ¯˙ .’ o ¯˙ .’ o e ¯i ıa a a a ¯e .c l` t´ a u ∆ij := min [ min {w(vi , vj )}], i = j. (4.1) vi ∈Ti vj ∈Tj Khi d o, dˆ d`ng ch´.ng minh rˇ ng lˇp lai ph´p to´n sau s˜ cho ta cˆy bao tr`m tˆi ¯´ ˜ a ` ´ e u a a. e a e a u o . thiˆ’u: ˙ e Ph´p to´n I. V´.i cˆy con Ts n`o d o, t` cˆy con Tj ∗ sao cho ∆sj ∗ = minTj [∆sj ], v` d at e a oa a ¯´ ım a a ¯ˇ . .o.ng u.ng gi´ tri ∆ ∗ trong (4.1) d at d u.o.c. Khi d ´ (v , v ∗ ) thuˆc (vs , vj ∗ ) l` canh tu a. ´ a . sj ¯. ¯ . ¯o s j o . cˆy bao tr`m tˆi thiˆ’u v` c´ thˆ’ d u.o.c thˆm v`o v´.i c´c canh kh´c trong qu´ tr` ˙ ˙ ´ a u o e a o e¯ . e aoa. a a ınh lˇp dˆ’ tao ra cˆy bao tr`m tˆi thiˆ’u. ˙ ˙ ´ a ¯e . a u o e . Thˆt vˆy, gia su. c´c canh trong c´c cˆy con o. bu.´.c k n`o d o thuˆc cˆy bao tr`m tˆi ´ ˙˙a . ’’ ˙ ’ aa aa o a ¯´ oa u o .. . ˙u Tm o. bu.´.c cuˆi c`ng. Gia su. canh (vs , vj ∗ ) d u.o.c chon nhu. trˆn khˆng thuˆc cˆy bao ’ ´ ˙ ’ ˙˙. ’’ thiˆ e o ou ¯. e o oa . . http://www.ebook.edu.vn 115
tr`m tˆi thiˆ’u Tm . Theo d inh ngh˜ cˆy con Ts o. bu.´.c cuˆi c`ng d u.o.c nˆi v´.i cˆy con kh´c ˙ ´ ´ ´ ˙ ’ uo e ¯. ıa, a o o u ¯. o o a a n`o d o bˇ ng canh (vi , vj ) trong d ´ vi ∈ Ts v` vj ∈ Ts v` ngo`i ra Ts phai ch´.a trong cˆy ` ˙ ’ a ¯´ a ¯o a / a a u a . bao tr`m tˆi thiˆ’u Tm . Xo´ canh (vi , vj ) khoi cˆy Tm s˜ cho ta hai th`nh phˆn liˆn thˆng ˙ ´ ` ˙a ’ u o e a. e a ae o ˙.i canh (vs , vj ∗ ) s˜ tao mˆt cˆy m´.i c´ trong lu.o.ng nho ho.n trong lu.o.ng cˆy ’. ˙ ’ v` thay n´ bo a o e. oa oo. a . . . . Tm , mˆu thuˆn. Vˆy, v´.i nh˜.ng gia thiˆt trˆn, ta c´ thˆ’ thˆm canh (vs , vj ∗ ) dˆ’ tao th`nh ˙ ˙ ˜ ´e ˙ ’ a a a o u e oee ¯e . a . . cˆy (ch´.a trong cˆy bao tr`m tˆi thiˆ’u) o. bu.´.c k v` tiˆp tuc v´.i bu.´.c (k + 1). C˜ng cˆn ˙’ ´ ´ ` e˙ a u a u o o ae . o o u a ch´ y rˇ ng, phu.o.ng ph´p trˆn khˆng phu thuˆc v`o cˆy Ts d u.o.c chon. Ho.n n˜.a, do bu.´.c u´ ` a a e o oaa ¯. u o . . . .i tao (t´.c l` tru.´.c khi bˆ t c´. canh n`o d u.o.c chon) gia thiˆt l` khˆng tˆn tai (v` do d ´ ´ ´ `. ˙ ’ ˙ ’ kho . ua o au. a¯. ea o o a ¯o . ´i c`ng s˜ tao ra cˆy bao tr`m tˆi thiˆ’u. ˙ ´ d ung) nˆn lˇp lai thuˆt to´n trˆn cuˆ u ¯´ ea. a a e o e. a u o e . . Hˆu hˆt c´c phu.o.ng ph´p t` cˆy bao tr`m tˆi thiˆ’u d` u du.a trˆn nh˜.ng tru.`.ng ho.p ˙e ` ea a´ ´ a ım a uo e ¯ˆ e u o . . - ` u tiˆn, trong sˆ d o l` phu.o.ng ph´p cua Kruskal [39] nhu. sau. ´ e˙ .’ ˙. ’ a˙ ’ d ac biˆt cua thu tuc trˆn. Dˆ ¯ˇ e a e o ¯´ a . 4.4.1 Thuˆt to´n Kruskal a a . Y tu.o.ng cua thuˆt to´n Kruskal t` cˆy bao tr`m trong d` thi liˆn thˆng c´ trong sˆ G ´ ´ ˙ ’ ˙ ’ a a ım a u ¯o . e ˆ o o. o . . sau: Kho.i tao v´.i d` thi T gˆm tˆ t ca c´c d ınh cua G v` khˆng c´ canh. Tai mˆ i bu.´.c ˜ ` ´’ ˙ . o ¯o . ’ o a ˙ a ¯˙ ’ ˙ ’ nhu ˆ ao o. .o o .o.ng nho nhˆ t lˆn cˆy T m` khˆng tao th`nh chu ´ ˙ ’ lˇp ch´ng ta thˆm mˆt canh c´ trong lu . a u e o. o. aea ao a . . . .ng khi T c´ (n − 1) canh. tr` trong T. Thuˆt to´n d` ınh a au o . . 1. [Kho.i tao] Gia su. T l` d` thi gˆm n d ınh v` khˆng c´ canh. a ¯o . ` ˙. ’ ˙˙ ’’ ¯˙’ ˆ o ao o. 2. [Sˇp xˆp] Sˇp xˆp th´. tu. c´c canh cua d` thi G theo th´. tu. trong lu.o.ng tˇng dˆn. ´´ ´´ ` ˙ ¯o . ’ˆ ae ae u.a . u. . a a . 3. [Thˆm canh] Thˆm canh (bˇt d` u t`. canh d` u tiˆn) trong danh s´ch c´c canh d u.o.c ´ˆ e e a ¯a u . ¯ˆa e a a. ¯. . . sˇp xˆp v`o cˆy T sao cho khˆng tao th`nh chu tr` trong T khi thˆm. (Canh d u.o.c ´´ aeaa o a ınh e ¯. . . .o.c). ´ thˆm v`o goi l` chˆ p nhˆn d u . e a .a a a¯ . 4. [Kˆt th´c] Nˆu T c´ (n − 1) canh th` thuˆt to´n d`.ng; T l` cˆy bao tr`m tˆi thiˆ’u. ˙ ´ ´ ´ e u e o ı a au aa u o e . . Thuˆt to´n n`y thˆm v`o cˆy T nh˜.ng canh c´ trong lu.o.ng nho nhˆ t chˆ p nhˆn d u.o.c ´ ´ ˙a ’ a aa e aa u o. a a¯. . . . . .n l` thˆm canh gi˜.a mˆt cˆy con cua T, chˇng han T , v` mˆt cˆy con n`o kh´c (nhu. ˙ ’ ˙ ’ ho a e u oa a aoa a a . . . . s chı ra trong Ph´p to´n I). Hiˆ’n nhiˆn canh d u.o.c chon c´ trong lu.o.ng nho nhˆ t gi˜.a mˆt ˙ ´u ˙’ ˙ ’ e a e e. ¯. .o. a o . . ´ ´ ˙ ’ cˆy con n`o d ´ v` bˆ t k` cˆy con kh´c, nˆn nguyˆn tˇc chon cua thuˆt to´n Kruskal l` mˆt a a ¯o a a y a a e ea a a ao . . . tru.`.ng ho.p d ac biˆt cua Ph´p to´n I. Tuy nhiˆn c´ thˆ’ xay ra tru.`.ng ho.p canh e d u.o.c ˙’ e˙ ’ eoe˙ o ¯ˇ e a o ¯. . . . . . kiˆ’m tra dˆ’ thˆm v`o liˆn thuˆc gi˜.a hai d ınh cua c`ng mˆt cˆy con v` do d o n´ s˜ tao ra ˙ ˙ ¯˙ ’ ˙u ’ e ¯e e ae o u oa a ¯´ o e . . . mˆt chu tr` nˆu thˆm v`o; t´.c l` canh e l` khˆng chˆ p nhˆn d u.o.c. V` vˆy, trong Bu.´.c 3, ´ ´ o ınh e e a ua. ao a a¯. ıa o . . . ` n d u.o.c kiˆ’m tra t´ chˆ p nhˆn cua n´ tru.´.c khi thˆm v`o T. Tiˆn tr` kiˆ’m ˙ ˙ ´ ´ a˙o ’ c´c canh cˆ ¯ . a. a e ınh a o e a e ınh e . .c hiˆn hiˆu qua bˇ ng c´ch su. dung thuˆt to´n xˆy du.ng cˆy bao tr`m tra n`y c´ thˆ’ thu ˙. ˙` ’a ˙. ’ aoe e e a a aa a u . . . . .a trˆn hai mang tuyˆn t´ nhu. d a tr` b`y trong Phˆn 4.3.3. ´ ` ˙ ’ du e e ınh ¯˜ ınh a a . http://www.ebook.edu.vn 116
V´ du 4.4.2 X´t d` thi trong H` 4.11(a). Sˇp xˆp c´c canh theo trong lu.o.ng tˇng dˆn ´´ ` ı. e ¯ˆ . o ınh aea. a a . . . dung hai mang tuyˆn t´ α v` β ) ta d u.o.c ´ ˙ ’ ˙ ’ (su . e ınh a ¯. k 1 2 3 4 5 6 7 8 9 α c a e a c a b c d β d c f e f b d e f Trong lu.o.ng 1 2 2 3 3 4 5 6 6 . . ınh) d u.o.c thˆm v`o cˆy T theo th´. tu. l` C´c canh (khˆng tao th`nh chu tr` a. o a ¯. e aa u.a . (c, d), (a, c), (e, f ), (a, e), (a, b). T l` cˆy bao tr`m nho nhˆ t c´ trong lu.o.ng 12 (H` 4.11(b)). ´ ˙ ’ao. aa u ınh . a a 4 4 b b • • • • .................................................................. .................................................................. .................................................................. .................................................................. . . . ... . ... . . ... . ... . . . . . ... . ... . ... . ... . . . . . ... . ... . ... ... . . . . . . . . . ... ... . . ... ... . . . 2 5 2 . . . . . . . . ... ... . ... ... . . . . . . . . ... ... . . . 3 1 3 1 ... ... . . . . . . . . . ... ... . . ... ... . . . . . . . . . ... ... . . . ... ... . • • • • . . ................................................................. .. . ................................................................. . . ... ... .. . ............................................................... ... ... ......... ........................................................... ......... .... . .. . . . . ... ... .... ... ... ... .... .... .... . c c .. . . . . ... .... ... ... .... .... ... ... ... .... d d .... . .... .. .. . . .. .... .. ... .... ... ... ... .... .... ... ... .... .... .. 3 .. .... 6 .... ... ... 6 ... ... ... .... .... ... .... .... ... ... ..... ... ... ..... ... ... .... .... ... .......... ... .......... ... ... .... .... . . . .. ... .... ... ... .. ... .... .... ... .. ... ..... • . • • • .. . .......................................................................................... ...................................................................................... ......................................................................................... ....................................................................................... . ... .. . .. . e e f f 2 2 (a) (b) H` 4.11: ınh Bˆ’ d` 4.4.3 Nˆu Kn = (V, E ) l` d` thi d` y d u , v` nˆu tˆ t ca c c´c trong lu.o.ng cu a c´c ˙e ´ ´´’ a ¯ˆ . ¯ˆ ¯ ˙ a e a ˙ a ’ ˙a ’ o ¯ˆ e o a . . ˙u T = (V, ET ). ’ ı` . ´oa ´ canh kh´c nhau th` tˆn tai duy nhˆ t mˆt cˆy bao tr`m tˆi thiˆ a o a uo e . . Ch´.ng minh. K´ hiˆu Ek := {e1 , e2 , . . . , ek } l` tˆp c´c canh d u.o.c thˆm v`o cˆy T trong u ye aa a . ¯. e aa . . . bu.´.c lˇp th´. k, 1 ≤ k ≤ n − 1. Hiˆ’n nhiˆn theo c´ch xˆy du.ng, T l` d` ˙ ˙ ’ Thuˆt to´n 4.4.1 o a a oa u e e a a a ¯o ˆ . . . ˙ a Kn . ’ thi c´ (n − 1) canh v` khˆng c´ chu tr` nˆn T l` cˆy bao tr`m cu .o ao o ınh e aa u . Gia su. T = (V, ET ) l` cˆy bao tr`m tˆi thiˆ’u, ta ch´.ng minh ET = En−1 . Thˆt vˆy, ˙ ´ ˙˙ ’’ aa u o e u aa .. . ngu.o.c lai tˆn tai chı sˆ k nho nhˆ t sao cho canh e khˆng thuˆc E . Khi d ´ theo `. ´ ´ ˙˙ ’’ ˙o ’ ˙ ’ gia su ..o a o o ¯o . . k T ınh a ˙ a ` . ` . o a ˙ o ´’ ’. t´ chˆ t cua cˆy, tˆn tai tˆn tai mˆt v` chı mˆt chu tr` µ trong T ∪ {ek }. Trˆn chu tr` o o ınh e ınh . .o.c lai tˆn tai mˆt chu tr` n`y c´ mˆt canh e0 m` e0 ∈ En−1 , v` nˆu ngu . . ` . ´ aoo. a / ıe o o ınh, l` µ, trong cˆy a a . . http://www.ebook.edu.vn 117
˜ T −mˆu thuˆn. Nˆu d at ET := (ET ∪ {ek }) \ {e0 }) th` d` thi T := (V, ET ) khˆng c´ chu ´. a a e ¯ˇ ı ¯ˆ . o o o tr` v` c´ (n − 1) canh nˆn n´ l` mˆt cˆy. ınh a o e oa o a . . Mˇt kh´c Ek−1 ∪ {e0 } ⊂ ET nˆn Ek−1 ∪ {e0 } khˆng ch´.a chu tr` a a e o u ınh. Suy ra . w(e0 ) > w(ek ). Nhu.ng cˆy T nhˆn d u.o.c t`. cˆy T b` ng c´ch thay canh e0 th`nh canh ek nˆn W (T ) < a a ¯. ua ˇ a a a e . . . ˙u. ’ ˜ ´ W (T ). Mˆu thuˆn v` T l` cˆy bao tr`m tˆi thiˆ a aı aa u o e Dinh l´ 4.4.4 Thuˆt to´n Kruskal l` d ung; t´.c l`, kˆt th´c thuˆt to´n T l` cˆy bao tr`m -. ´u y aa a ¯´ uae aa aa u . . tˆi thiˆ’u. ˙ ´ o e Ch´.ng minh. Thˆt vˆy tru.´.c hˆt ta thu xˆp dˆ’ moi canh d` u c´ d ˆ d`i kh´c nhau; chˇng ˙ ˙ ’ ´ ´ u aa oe e ¯e . . ¯ˆ o ¯o a e a a .. . ´u w(e1 ) = w(e2 ) = · · · = w(es ) th` thu.c hiˆn ph´p biˆn d o’i: ˙ ´ ¯ˆ han nˆ e ı. e e e . . w(e1 ) = w(e1 ) + , w(e2 ) = w(e2 ) + 2 , . . . w(es ) = w(es ) + s , trong d o l` sˆ du.o.ng d u b´ sao cho khˆng l`m d ao lˆn th´. tu. vˆ quan hˆ gi˜.a trong lu.o.ng ´ u.` ¯˙ e ’ a ¯˙ o ’. ¯´ a o o e eu . . . ˙a. ’ cua c´c canh. C˜ng thˆ, ta c˜ng c´ thˆ’ thˆm c´c canh f v´.i trong lu.o.ng d u l´.n w(f ) > ˙ ´ ¯˙ o ’ u e u oee a. o w(e) . . e∈E .o.c K = (V, E ) l` d` y d u. v` kh´c nhau sao cho d` thi nhˆn d u . a ¯ˆ ¯ ˙ ’ aa ¯ˆ . a ¯ o a . n Theo Bˆ’ d` 4.4.3 tˆn tai duy nhˆ t mˆt cˆy bao tr`m tˆi thiˆ’u T trong d` thi Kn . Mˇt ˙e ˙ `. ´oa ´ o ¯ˆ o a uo e ¯o . ˆ a . . .o.ng khˆng vu.o.t qu´ kh´c, moi cˆy bao tr`m cua d` thi G c´ trong lu . ˙ ¯o . ’ˆ a a u o. o a e∈E w(e) v` moi cˆy a.a . . bao tr`m cua G c˜ng l` cˆy bao tr`m cua Kn . Suy ra T l` cˆy bao tr`m tˆi thiˆ’u cua G. ˙˙ ´ ˙ ’ ˙ ’ ’ u u aa u aa u o e Nhˆn x´t rˇ ng, c´ thˆ’ d`ng phu.o.ng ph´p d oi ngˆ u: loai dˆn c´c canh c´ trong lu.o.ng ˙ ae` ˜ ´ .`a. a o eu a ¯ˆ a a o. . . .n nhˆ t cua d` thi m` khˆng l`m mˆ t t´ liˆn thˆng cua n´ cho dˆn khi khˆng thˆ’ loai ˙ ´’ˆ ´ ´ a ˙ ¯o . a o ˙o ’ l´ o a a ınh e o ¯e o e. canh d u.o.c n˜.a. ¯. u . Dˆ ph´.c tap t´ to´n cua thuˆt to´n Kruskal phu thuˆc v`o Bu.´.c 2: d` thi c´ m - o u . ınh a ˙ ’ a a oa o ¯o . o ˆ . . . . ˙ thu.c hiˆn sˇp xˆp mang theo trong lu.o.ng tˇng dˆn. Tuy ’. .´´ ` ` ˙ ’ canh cˆn m log2 m ph´p to´n dˆ a e a ¯e eae a a . . . ` n duyˆt to`n bˆ mang v` cˆy bao tr`m tˆi thiˆ’u gˆm (n − 1) ˙` ´ ˙’ nhiˆn, n´i chung ta khˆng cˆ e o o a e ao ıa u o eo . . canh chˆ p nhˆn d u.o.c nˆn chı cˆn kiˆ’m tra r < m phˆn tu. d` u tiˆn cua mang. Do d o ta c´ ˙ ´ ˙` ` ’a a ˙ ¯a ’ˆ e˙ ’ ˙ ’ a a¯. e e ¯´ o . . ˙ cai tiˆn thuˆt to´n n`y dˆ’ tˇng tˆc d o thu.c hiˆn (xem [14], [36]). ’˙ e ˙a ´ ´ ¯ˆ . thˆ ’ e a a a ¯e o. e . . Mˇc d` c´ nh˜.ng cai tiˆn, nhu.ng thuˆt to´n Kruskal chı th´ ho.p v´.i nh˜.ng d` thi ’´ ˙e ˙ ıch . ’ a uo u a a o u ¯ˆ . o . . .o.ng d ˆi thu.a. V´.i nh˜.ng d` thi kh´c, chˇng han d` thi d` y d u c´ sˆ canh m = n(n − 1)/2, ˙ ’ ´ ´ . ¯o . ¯ˆ ¯ ˙ o o . ’ tu ¯o o u ¯ˆ . a o a ˆ a http://www.ebook.edu.vn 118