Lí thuyết đồ thị part 5

Chia sẻ: ágffq ằefgsd | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

75
lượt xem 11
download

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

Một trong những kết quả đầu tiên trong lí thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Königsberg, xuất bản năm 1736. Bài báo này cũng được xem như một trong những kết quả topo đầu tiên trong hình học, tức là, nó không hề phụ thuộc vào bất cứ độ đo nào. Nó diễn tả mối liên hệ sâu sắc giữa lí thuyết đồ thị và tôpô học.

Chủ đề:

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

Lưu

Nội dung Text: Lí thuyết đồ thị part 5

v5 • .. .. .... ....... .... ....... .... .... .... .... .... .... .... .... .... .... .... 25 30 .... ... ... .... .... .... .... .... .... .... .... .... .. .... . .... .... .... .... .. . .... .... .... .... v4 .. .... . .... .... .... 50 .... .... .. . .... .... .... .... .. . .... .... .... v7 • • v3 .... • ......................................................... ......................................................... .... .... . ..... . .. .... .... .... ... . . .. . . .... .... . ..... . .... . ..... . .... . . .... .... . . . .... .... . . . 20 20 . . . ... .... ... .. . .... . . . .... .... . . . .... ... . ... .... . . .. . . . . .... .... .... . . . ... .... . ... . . . .. .... . .... . . . .... .... ... ... . . . .... . . . .... .. . . . . ... .... .... ... .... . . . .... . . . .. . . ... .... ... . . .... .... . .... v6 . . . . . .... . ... .. . ... .... .... . . . .... . . . .... ... . . . .... ... .. . . . . .... .... .... . . . .... ... . ... . . .... ...... .... .... . • . . . ... 25 30 25 . . ... . ... . . . . .. . . . ... ... . . . . . . . . . ... . . 40 . ... . . . . . . . . ... . ... . . . . . . . . . . ... . ... . . . . . . . . . ... . . . ... . . . . . . . . . ... ... . 20 . . . . . . . ... . . . . ... . . . . . . . . ... . ... . . . . . . . . ... . . . . ... . . . ... . . . . ... . . . . . . . . ... . . ... . . . . . . . . . . .... . .... . . • • • • . . . . ................................................................................................................................................................. . . . . ................................................................................................................................................................ . v8 v9 v1 v2 20 40 30 H` 3.2: ınh     012 034 ˙ng ma trˆn A ⊕ B nˆu A =  2 0 3  v` B =  5 0 4  . ’ ´ V´ du 3.3.2 T` tˆ ı. ım o a e a    . 560 310 Ta c´ o       012 034 012      A ⊕ B = 2 0 3 + 5 0 4 = 2 0 3. 560 310 310 Chˇng han, phˆn tu. c23 x´c d .nh bo.i ˙ ’ ` a˙ ’ ˙ ’ a a ¯i . c23 = min{2 + 4, 0 + 4, 3 + 0} = 3.     01∞ 10∞ V´ du 3.3.3 T` tˆ’ng ma trˆn A ⊕ B nˆu A =  1 0 4  v` B =  1 0 4  . ˙ ´ ı. ım o a e a     . ∞40 ∞40 Ta c´ o       01∞ 10∞ 105      A ⊕ B =  1 0 4  +  1 0 4  = 1 0 4. ∞40 ∞40 540 Chˇng han, phˆn tu. c13 x´c d .nh bo.i ˙ ’ ` a˙ ’ ˙ ’ a a ¯i . c23 = min{0 + ∞, 1 + 4, ∞ + 0} = 5. Bˆy gi`. ´p dung tˆ’ng ma trˆn Hedetniemi v`o viˆc t` d u.`.ng d i ngˇn nhˆ t. X´t v´ ˙ ´ ´ a oa o a a e ım ¯ o ¯ a a eı . . . 89
du trong H` 3.2. K´ hiˆu W 2 := W ⊕ W, W k := W k−1 ⊕ W, k ≥ 2. Khi d o ınh ye ¯´ . .   0 30 55 30 60 50 ∞ 60 40  30 70  0 25 40 70 60 ∞ ∞      55 25 0 50 80 70 ∞ ∞ ∞    30 40  40 50 0 30 20 40 ∞   W =  60 ∞. 2 70 80 30 0 ∞ 25 ∞     ∞ 20  ∞ ∞ 20 ∞ 0 20 ∞   ∞ ∞ ∞ ∞ ∞ 25 20 0 25     ∞ ∞ ∞ ∞ ∞ ∞ 25 0 20  40 ∞ ∞ ∞ ∞ 20 ∞ 20 0 Ch´ng ta h˜y x´t c´ch x´c d inh mˆt phˆn tu. cua ma trˆn W 2 = [aij ] : (2) ` a˙˙ ’’ u aea a ¯. o a . . (2) a13 = min{0 + ∞, 30 + 25, ∞ + 0, 30 + 50, ∞ + ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞, 40 + ∞} = 55. Ch´ y rˇ ng gi´ tri 55 l` tˆ’ng cua 30, d o d`i cua d u.`.ng d i ngˇn nhˆ t v´.i sˆ cung mˆt t`. ˙ u´ ` ´ ´ ´ ˙ ’ ¯ˆ a ˙ ¯ o ’ a a. ao ¯ a aoo ou . . (2) ´’ ´’ ¯˙’ ¯e ¯˙ a˙ ’ ¯ˆ a ˙ ’ o ¯˙ a ¯˙’ d ınh v1 dˆn d ınh v2 , v` cua 25, d o d`i cua cung nˆi d ınh v2 v` d ınh v3 . Do d o a13 l` d o d`i ¯´ a ¯ˆ a . . cua d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v2 v´.i sˆ cung nhiˆu nhˆ t hai. Suy ra W 2 cho ta thˆng ´ ´ ´ ´ ` ´ ˙ ¯o ’ ¯ a au ¯e oo e a o .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh c´ sˆ cung nhiˆu nhˆ t hai. ´ ’´’ ´u ´ ` ´ ˙ a ˙ a ¯ˆ a ¯ ¯˙’ tin cua tˆ t ca c´c d o d`i d u o ¯ a a oo e a . Tu.o.ng tu., W 3 cho ta thˆng tin cua tˆ t ca c´c d o d`i d u.`.ng d i ngˇn nhˆ t gi˜.a hai ´ ’´’ ´u ˙ a ˙ a ¯ˆ a ¯ o o ¯ a a . . d ınh c´ sˆ cung nhiˆu nhˆ t ba, v` vˆn vˆn. Do d` thi c´ n d ınh nˆn c´ nhiˆu nhˆ t (n − 1) ´ ` ´ ` ´ ¯˙’ ¯ˆ . o ¯˙ ’ oo e a aa a o eo e a .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh. Vˆy ´ ´u ¯˙ ’ cung trˆn d u o e¯ ¯ a a a . Dinh l´ 3.3.4 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, phˆn tu. h`ng i cˆt j cu a ma -. ´ ` ¯˙ a ˙a ’ ˙ ’ y ¯ˆ . o . o ooa o . .`.ng d i ngˇn nhˆ t gi˜.a d ı’nh v v` v . ´ ´ n−1 a ¯o a ˙ ¯ ’ a u ¯˙ trˆn Hedetniemi W a l` d ˆ d`i cu a d u o ¯ a iaj . . V´.i d` thi trong H` 3.2 c´ ch´ d ınh, ta c´ o ın ¯˙ ’ o ¯ˆ . o ınh o   0 30 55 30 60 50 70 60 40  30 80 90 70  0 25 40 70 60      55 25 0 50 80 70 90 110 90     30 40 60 40  40 50 0 30 20     8 W =  60 70 80 30 0 45 25 50 65  .    50 20 40 20  60 70 20 45 0    0 25 40   70 80 90 40 25 20     60 90 110 60 50 40 25 0 20  40 70 90 40 65 20 40 20 0 Do d o, d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 c´ d o d`i 70. ´ ´ ´ ¯´ ¯ o ¯ a au ¯e o ¯ˆ a . 90
Diˆu l´ th´ nhˆ t trong v´ du n`y l` W 4 = W 8 . Thˆt vˆy, d ang th´.c suy tru.c tiˆp t`. -` y u a ˙ ’ ´ ´ e ı.aa a a ¯ˇ u eu .. . .`.ng d i ngˇn nhˆ t d i qua nhiˆu nhˆ t bˆn cung. Bo.i vˆy d o d`i ´ d` thi trong H` 3.2: moi d u o ¯ ´ ` ´´ ˙ a ¯ˆ a ’. ¯o . ˆ ınh .¯ a a¯ e ao . .`.ng d i ngˇn nhˆ t d u.o.c x´c d inh bo.i ma trˆn W 4 thay v` phai t´ dˆn W 8 . Tˆ’ng ˙ ´ ´ ´ ˙¯ ’ ˙’ ˙ ınh ¯e ’ cua d u o ¯ a a ¯ . a ¯. a ı o . qu´t ta c´ a o -. Dinh l´ 3.3.5 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, nˆu ma trˆn Hedetniemi W k = ´ ´ ¯˙ y ¯ˆ . o . o ooa e a. ˙u thi tˆp c´c d ˆ d`i cu a c´c d u.`.ng d i ngˇn nhˆ t, v` sˆ ’ ´ ´ ´ k−1 k k+1 k . a a ¯o a ˙ a ¯ o ¯ ’ W , c`n W = W , th` W biˆ o ı e a a ao . . .`.ng d i ngˇn nhˆ t khˆng vu.o.t qu´ k. ˜ ´ ´ cung trˆn mˆ i d u o e o¯ ¯ a a o a . Do d ´, thuˆt to´n n`y c´ thˆ’ d`.ng o. bu.´.c lˇp th´. k < (n − 1). Du.´.i d ay l` d oan ˙ ˙ ’ ¯o a a a o eu oa u o ¯ˆ a ¯ . . . .o.ng tr` minh hoa t´ ma trˆn lu˜ th`.a cua ma trˆn trong lu.o.ng W. yu˙ ’ chu ınh . ınh a a . . . . void Hetdetniemi() { int i, j, k, t; int Old[MAXVERTICES][MAXVERTICES], New[MAXVERTICES][MAXVERTICES]; Boolean Flag; for (i = 1; i
if (Flag == TRUE) break; } } X´c d .nh d .`.ng d ngˇn nhˆ t ´ ´ a ¯i ¯u o ¯i a a Bˆy gi`. ta t` d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 (d o d`i 70). Ta c´ ´ ´ ´ a o ım ¯ o ¯ a au ¯e ¯ˆ a o . (4) (3) w14 = w1k ⊕ wk7 v´.i k n`o d o. Nhu.ng c´c phˆn tu. w1k tao th`nh vector h`ng ’ (3) . ` a˙ o a ¯´ a a a (0, 30, 55, 30, 60, 50, 70, 60, 40) v` c´c phˆn tu. wk7 tao th`nh vector cˆt ` a˙ ’ aa a o . . (∞, ∞, ∞, ∞, 25, 20, 0, 25, ∞). V` gi´ tri nho nhˆ t d at d u.o.c tai k = 6 u.ng v´.i 70 = 50 + 20 (v` k = 7) nˆn d u.`.ng d i ngˇn ´ ´ ˙ a ¯. ¯ . . ’ ıa. ´ o a e ¯o ¯ a . v dˆn v s˜ d i qua nhiˆu nhˆ t ba cung t`. v dˆn v v` kˆt th´c v´.i cung d o d`i 20 ´ ´ ` ´ ´ ´ nhˆ t t` 1 ¯e 7 e ¯ au e a u 1 ¯e 6 a e uo ¯ˆ a . . v dˆn v . (Thˆt ra, do gi´ tri nho nhˆ t c˜ng d at d u.o.c tai k = 7 (´.ng v´.i 70 + 0) nˆn ´ ´ ˙ ’ a u ¯. ¯ . . t` 6 ¯e 7 u a a. u o e . ` n tai d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 v´.i tˆ’ng sˆ cung d i qua khˆng vu.o.t qu´ ba). ˙ ´ ´u ´ ´ tˆ . ¯ o o ¯ a a ¯e oo o ¯ o a . Tiˆp dˆn ta t` cung tru.´.c khi dˆn d ınh v6 . Ch´ y rˇ ng w16 = 70 − 20 = 50. C´c (4) u´ ` ´´ ´’ ¯e ¯ ˙ e ¯e ım o a a phˆn tu. wk6 tao th`nh vector cˆt ` a˙ ’ a o . . (∞, ∞, ∞, 20, ∞, 0, 20, ∞, 20). Lˆn n`y gi´ tri nho nhˆ t d at tai k = 4 (´.ng v´.i 50 = 30 + 20) nˆn d u.`.ng d i ngˇn nhˆ t d ˆ ´ ` ´ ´. ˙ ’ a ¯. . aa a. u o e ¯o ¯ a a ¯o . v dˆn v kˆt th´c v´.i cung (v , v ) d ˆ d`i 20. Cuˆi c`ng, c´c phˆn tu. w tao ´ ´ ´ ` a ˙ k4 . ’ d`i 50 t` 1 ¯e 6 e a u uo ¯o a ou a . 46 th`nh vector cˆt a o . (30, 40, 50, 0, 30, 20, ∞, ∞, ∞), v` gi´ tri nho nhˆ t d at tai k = 1 hoˇc k = 4 (´.ng v´.i 30 + 0 hoˇc 0 + 30) nˆn tˆn tai cung ´ e`. ˙ ’ a ¯. . aa. a u o a o . . . v dˆn v . Vˆy d u.`.ng d i ngˇn nhˆ t t`. v dˆn v l` v , v , v , v (c´c cung c´ ´ ´ ´ ´ d o d`i 30 t` 1 ¯e 4 a ¯ o ¯ˆ a u ¯ a a u 1 ¯e 7 a 1 4 6 7 a o . . d o d`i 30, 20, 20). ¯ˆ a . Do d ´ thuˆt to´n Hedetniemi cho mˆt minh hoa h` hoc trong mˆ i bu.´.c lˇp, v` su. ˜ a˙ ’ ¯o a a o . ınh . o oa . . . ˙ phuc hˆi d u.o.c d u.`.ng d i ngˇn nhˆ t. Nhu. vˆy, ch´ng ta cˆn thˆm ’ . `¯. ¯o ´ ´ ` dung c´c ma trˆn c´ thˆ a aoe o ¯ a a a u a e . . . mˆt ma trˆn P lu.u tr˜. thˆng tin cua c´c d u.`.ng d i ngˇn nhˆ t. Ma trˆn n`y s˜ d u.o.c cˆp ´ ´ ˙ a ¯o ’ o a uo ¯ a a a a e¯ . a . . . . nhˆt trong mˆ i bu.´.c lˇp khi t´ W k t`. W k−1 . ˜ a o oa ınh u . . 92
Thuˆt to´n Floyd (tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y) 3.3.2 a a o a y´ . . . . . Thuˆt to´n du.´.i d ay d u.o.c d u.a ra lˆn d` u tiˆn bo.i Floyd [25] v` d u.o.c l`m min ho.n bo.i ` ¯ˆ ˙ ’ ˙ ’ a a o ¯ˆ ¯ . ¯ a a e a¯ . a . . Murchland [46]. Thuˆt to´n Floyd a a . 1. [Kho.i tao] Dˇt k := 0. ˙ . -a ’ . 2. k := k + 1. 3. [Bu.´.c lˇp] V´.i moi i = k sao cho wik = ∞ v` v´.i moi j = k sao cho wkj = ∞, thu.c oa o ao . . . . hiˆn ph´p g´n e ea . wij := min{wij , (wik + wkj )}. (3.3) 4. [Diˆu kiˆn kˆt th´c] (a) Nˆu tˆn tai chı sˆ i sao cho wii < 0 th` tˆn tai mach v´.i d ˆ -` ´ e`. ´o ’´ ı` . ˙o e ee u o o ¯o . . . .a d ınh v . B`i to´n vˆ nghiˆm; thuˆt to´n d`.ng. d`i ˆm ch´ ¯˙ ’ aa u aao e a au . . i (b) Nˆu wii ≥ 0 v´.i moi i = 1, 2, . . . , n, v` k = n, b`i to´n c´ l`.i giai: ma trˆn wij cho ´ ˙ ’ e o a a a oo a . . .`.ng d i ngˇn nhˆ t t`. v dˆn v . Thuˆt to´n d`.ng. ´ ´ ´ d ˆ d`i d u o ¯o a ¯ ¯ a a u i ¯e j a au . . ´u wii ≥ 0 v´.i moi i = 1, 2, . . . , n, nhu.ng k < n, chuyˆ’n sang Bu.´.c 2. ˙ (c) Nˆe o e o . Ch´.ng minh t´ d ung d ˇn cua thuˆt to´n Floyd l` ho`n to`n d o.n gian [35], [25] v` ´ ˙ ’ ˙ ’ u ınh ¯´ ¯a a a aa a¯ a . .`.i d oc. Ph´p to´n co. ban cua Phu.o.ng tr` 3.3 trong thuˆt to´n n`y goi l` ˙ ’ ˙ ’ d`nh cho ngu o ¯ . a e a ınh a a a .a . ph´p to´n bˆ ba v` c´ nhiˆu u.ng dung trong nh˜.ng b`i to´n tu.o.ng tu. b`i to´n t` d u.`.ng `´ e ao ao e u aa a a ım ¯ o . . . ´ ´ d i ngˇn nhˆ t (xem [14], [30]). ¯ a a C´c d u.`.ng d i ngˇn nhˆ t c´ thˆ’ nhˆn d u.o.c d` ng th`.i c`ng v´.i c´c d o d`i d u.`.ng d i ˙ ´ ´ a ¯o ¯ a a o e a ¯ . ¯ˆ o ou o a ¯ˆ a ¯ o ¯ . . . dung quan hˆ dˆ qui tu.o.ng tu. Phu.o.ng tr` 3.2. Bˇ ng c´ch ´p ´ a` ` ´a ˙ ’ ngˇn nhˆ t bˇ ng c´ch su . a a e ¯e ınh a aa .. . . chˆ cua Hu [35] dˆ’ lu.u gi˜. thˆng tin c´c d u.`.ng d i ngˇn nhˆ t c`ng v´.i d o d`i cua ˙ ´ ´˙ ´u ’ o ¯ˆ a ˙ ’ dung co e ¯e uo a ¯o ¯ a a . . .a v`o ma trˆn vuˆng cˆ p n : P := [θ ]; v` biˆn d ˆ’i n´ d` ng th`.i v´.i viˆc n´. Cu thˆ’ l` d u a ˙ ˙ ´ ´ o . e a¯ a o a a e ¯o o ¯o ˆ ooe . . ij ˙i ma trˆn W. Phˆn tu. θij cua ma trˆn P s˜ chı ra d ınh d i tru.´.c vj trong d u.`.ng d i ’ ´ ` a˙ ’ ˙’ e˙ ’ ¯˙ ’¯ biˆn d ˆ e ¯o a a o ¯o ¯ . . ngˇn nhˆ t t`. vi dˆn vj ; o. bu.´.c d` u tiˆn ta g´n cho ma trˆn P c´c gi´ tri d` u l` θij := vi ´ ´ ´ ˙ ’ a au ¯e o ¯ˆ a e a a a a . ¯a a ˆ . v´.i moi d ınh vi v` vj . ¯˙ ’ o a . C`ng v´.i viˆc biˆn d o’i ma trˆn W theo Phu.o.ng tr` 3.3 trong Bu.´.c 3, ta biˆn d o’i ˙ ˙ ´ ´ u oe e ¯ˆ a ınh o e ¯ˆ . . ´ P theo quy tˇc a ´ θkj nˆu (wik + wkj ) < wij , e θij := nˆu ngu.o.c lai. ´ θij e .. .o.c s˜ gi´p cho ta viˆc t` c´c d u.`.ng d i ngˇn nhˆ t. ´ ´ ´ Kˆt th´c thuˆt to´n, ma trˆn P thu d u . e u e u a a a ¯ e ım a ¯ o ¯ a a . . . ˙ ng han d u.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh vi v` vj l` ’ ´ ´u ¯˙ ’ Chˇa . ¯o ¯ a a a a vi , v ν , . . . , v γ , v β , v α , v j 93
´ trong d o vα = θij , vβ = θiα , vγ = θiβ , ..., cho dˆn khi vi = θiν . ¯´ ¯e Cˆn ch´ y o. d ˆy l` nˆu tˆ t ca c´c gi´ tri wii d u.o.c kho.i tao bˇ ng ∞ (thay cho bˇ ng ˙.` ` ` ´´’ u ´ ˙ ¯a a e a ˙ a ’ ’ a a. ¯. a a ´ ´ ´ ´ ˙ ’ a ¯o a ˙ ’ 0) l´c xuˆ t ph´t thuˆt to´n, th` c´c gi´ tri cuˆi c`ng cua wii l` d ˆ d`i cua mach ngˇn nhˆ t u a a a a ıa a.ou a a . . . ´t ph´t t`. d ınh vi . Ngo`i ra c˜ng c´ thˆ’ dˆ d`ng x´c d inh mach c´ d o d`i ˆm khi wii < 0 ˙˜a ˙ ’ xuˆ a a u¯ a u o ee a ¯. o ¯ˆ a a . . du.a v`o ma trˆn d u.`.ng d i P. a a ¯o ¯ . . ˙. ’ Thu tuc Floyd() sau minh hoa thuˆt to´n d a tr` b`y. a a ¯˜ ınh a . . void Floyd() { byte i, j, k; AdjPointer Tempt; byte Pred[MAXVERTICES][MAXVERTICES]; int Weight[MAXVERTICES][MAXVERTICES], NewLabel; byte Start, Terminal; for (i = 1; i Length; Tempt = Tempt->Next; } } for (k = 1; k
for (j = 1; j NewLabel) { Weight[i][j] = NewLabel; Pred[i][j] = Pred[k][j]; } } if (Weight[i][i] < 0) { printf("Ton tai mach do dai am qua dinh %d", i); printf(" %6d ", Weight[i][i]); return; } } } // Vi du minh hoa Start = 1; Terminal = 3; if (Weight[Start][Terminal] < +INFTY) { printf("Ton tai duong di tu %d", Start); printf(" den %d", Terminal); printf("\nDuong di qua cac dinh:"); i = Terminal; while (i != Start) { printf("%3d ", i); i = Pred[Start][i]; } printf("%3d ", Start); printf("\nTrong luong la %3d ", Weight[Start][Terminal]); } else printf("\n Khong ton tai duong di tu %d den %d", Start, Terminal); } 95
3.4 Ph´t hiˆn mach c´ d o d`i ˆm a e o ¯ˆ a a . . . Vˆ n d` ph´t hiˆn c´c mach c´ d o d`i ˆm trong mˆt d` thi tˆ’ng qu´t l` quan trong khˆng ˙ ´e a ¯ˆ a ea o ¯ˆ a a o ¯o . o .ˆ aa o . . . . .ng trong ch´ b`i to´n t` d u.`.ng d i ngˇn nhˆ t m` c`n l` mˆt bu.´.c co. ban trong ´ ´ ˙ ’ nh˜ u ınh a a ım ¯ o ¯ a a ao a o o . nh˜.ng thuˆt to´n kh´c (xem Phˆn 3.4.1 v` [14]). ` u a a a a a . Ta biˆt rˇ ng Thuˆt to´n Floyd t` d u.`.ng d i ngˇn nhˆ t gi˜.a c´c cˇp d ınh c´ thˆ’ ph´t ˙ ´` ´ ´ a u a a ¯˙ ’ ea a a ım ¯ o ¯ a oea . . ` thi. Ho.n n˜.a, nˆu d` thi ch´.a mˆt d ınh s m` c´ thˆ’ dˆn ˙´ ´ ¯o . u ˙ ’ hiˆn c´c mach d o d`i ˆm trong d o . ea . ¯ˆ a a ¯ˆ u eˆ o¯ a o e ¯e . . . . d o, th` c´ thˆ’ ´p dung Thuˆt to´n Ford-Moore-Bellman (t` tˆ t ca ˙ ´’ ´’ a ˙ a ¯˙ ’ ım a ˙ tˆ t ca c´c d ınh kh´c t` ¯´au ı o ea a a . . .`.ng d i ngˇn nhˆ t xuˆ t ph´t t`. d ınh s) dˆ’ ph´t hiˆn c´c mach c´ d o d`i ˆm nhu. d ˜ ˙a ´ ´ ´ a u ¯˙ ’ c´c d u o a¯ ¯ a a a ¯e ea o ¯ˆ a a ¯a . . . thu.c hiˆn trong Bu.´.c 3 cua phˆn n`y. Nˆu tˆn tai d ınh khˆng thˆ’ dˆn d u.o.c t`. s (chˇng˙´ ˙ ’ ` e ` . ¯˙ ´o ˙ ’ ’ e o aa o e ¯e ¯ . u a . . han, khi G l` d` thi vˆ hu.´.ng khˆng liˆn thˆng) th` Thuˆt to´n Ford-Moore-Bellman s˜ kˆt ´ a ¯o . o o ˆ o e o ı a a ee . . ˙ c´c d ınh c´ thˆ’ dˆn d u.o.c t`. s c´ nh˜n h˜.u han, c´c d ınh kh´c khˆng dˆn d u.o.c ˙ ¯e ¯ . u ´ ´¯. ’ a ¯˙ ’ ˙ ’ th´c v` chı ua oe oau a¯ a o ¯e . t`. s c´ nh˜n bˇ ng ∞. Trong tru.`.ng ho.p n`y c´ thˆ’ tˆn tai c´c mach c´ d o d`i ˆm trong ˙o ` a o e` . a u oaa o o ¯ˆ a a . . . th`nh phˆn liˆn thˆng khˆng ch´.a s v` khˆng d u.o.c ph´t hiˆn. Tuy nhiˆn, nhiˆu u.ng dung ` `´ a ae o o u a o ¯. a e e e . . ` n kiˆ’m tra c´ mach d ˆ d`i ˆm hay khˆng, d` thi d u.o.c x´t c´ d ınh s dˆn d u.o.c tˆ t ca c´c ˙ ´¯. a ˙a ´’ ˙ ’ cˆ a e o . ¯o a a o ¯o . ¯ . e o ¯ ˆ ¯e . d ınh kh´c, v` do d o v´.i nh˜.ng tru.`.ng ho.p nhu. vˆy, dˆ’ x´c d .nh su. tˆn tai cua mach d o ˙ .` . ˙ ¯˙’ ’ a a ¯´ o u o a ¯e a ¯i o ¯ˆ . . . . .n Thuˆt to´n ˙’ d`i ˆm, Thuˆt to´n Ford-Moore-Bellman s˜ cho ph´p t´ to´n hiˆu qua ho aa a a e e ınh a e a a . . . Floyd. C´c nguyˆn tˇc kˆt th´c cua Thuˆt to´n Ford-Moore-Bellman d u.o.c tr` b`y dˆ’ t´ ˙ ´´ u˙ ’ a eae a a ¯. ınh a ¯e ınh . ´t c´c d u.`.ng d i ngˇn nhˆ t t`. s khi khˆng c´ mach d o d`i ˆm. C´c nguyˆn tˇc ´ ´ ´u to´n ´ nhˆ a ¯ o a ıt a ¯ a a o o. ¯ˆ a a a ea . .m ho.n nhu. sau. n`y c´ thˆ’ cai biˆn dˆ’ ph´t hiˆn mach d ˆ d`i ˆm s´ ˙ ’ e ¯e a ˙ a o e˙ e . ¯o a a o . . Sau khi g´n lai nh˜n cua d ınh vi t`. mˆt d ınh vj ∗ theo Phu.o.ng tr` 3.2 ta kiˆ’m tra ˙ ˙ ¯˙ ’ ’ u o ¯˙.’ a. a ınh e .`.ng d i ngˇn nhˆ t hiˆn h`nh (m` c´ thˆ’ suy t`. c´c nh˜n hiˆn h`nh θ) ˙ ´ ´ea ¯˙’ d ınh vi c´ thuˆc d u o o o¯ ¯ a a ao e ua a ea . . . . s dˆn v ∗ hay khˆng. Nˆu d ung, th` d ınh v ∗ d ˜ d u.o.c g´n nh˜n thˆng qua v v` d iˆu ´ ´ i a ¯` ı ¯˙’ t` ¯e j u o e ¯´ j ¯a ¯ . a a o e ˜n dˆn Lk (vj ∗ ) + w(vj ∗ , vi ) < Lk (vi ); do d ´ mˆt phˆn cua d u.`.ng d i ngˇn nhˆ t hiˆn ´ ´ ` ´e ˙ ¯o ’ n`y dˆ ¯e aa ¯o o a ¯ a a . . h`nh t`. vi dˆn vj ∗ cˆng thˆm cung (vj ∗ , vi ) s˜ tao th`nh mach c´ d o d`i ˆm v` thuˆt to´n ´ a u ¯e o e e. a o ¯ˆ a a a a a . . . . kˆt th´c. Nˆu mˇt kh´c, nh˜n cua d ınh vi hoˇc khˆng thay d o’i bo.i Phu.o.ng tr` 3.2, hoˇc ˙’ ´ ´ a ˙ ¯˙ ’’ ¯ˆ ˙ e u e a a a o ınh a . . . nhˆn nh˜n m´.i t`. mˆt d ınh vj ∗ nhu.ng vi khˆng thuˆc d u.`.ng d i ngˇn nhˆ t t`. s dˆn vj ∗ , th` ´ ´ ´ o u o ¯˙ ’ a a o o ¯o ¯ a a u ¯e ı . . . .´.c 3 nhu. tru.´.c. Cˆn ch´ y rˇ ng, cai tiˆn trˆn ch´ l` giam nh˜.ng u´ ` ´ ` ’´ ˙e ınh a ˙ ’ thuˆt to´n tiˆp tuc Bu o a a e. o a a e u . . th`.a khˆng cˆn thiˆt trong Thuˆt to´n Ford-Moore-Bellman, do mˆt mach c´ d o d`i ˆm ` ´ du u o a e a a o o ¯ˆ a a . . . . d u.o.c x´c d .nh ngay khi n´ d u.o.c tao ra v` khˆng cˆn d o.i kˆt th´c thu tuc. ` ¯. e ´ ˙. ’ ¯ . a ¯i o¯ . . ao a u Mach tˆi u.u trong d` thi c´ hai trong lu.o.ng ´ 3.4.1 o ¯ˆ . o o . . . Mˆt vˆ n d` nay sinh trong nhiˆu l˜ vu.c liˆn quan dˆn mˆt d` thi c´ hu.´.ng m` mˆ i cung ˜ . ´ e’ ` ınh . e ´ o a ¯ˆ ˙ e ¯e o ¯ˆ . o o .o ao .o.c g´n hai trong lu.o.ng: w v` b . B`i to´n l` t` mˆt mach Φ m` cu.c tiˆ’u (hoˇc ˙ (vi , vj ) d u . a ¯ ij a ij a a a ım o a. e a . . . . . 96
cu.c d ai) h`m muc tiˆu . ¯. a e . wij (vi ,vj )∈Φ z (Φ) := . (vi ,vj )∈Φ bij ˙’ ınh ˙ ’ Chˇng han, x´t h`nh tr` cua mˆt con t`u hay mˆt m´y bay trˆn mang giao thˆng a ea o a o a e o . . . . . rˇ ng w l` “lo.i nhuˆn” v` b l` “th`.i gian” cˆn thiˆt dˆ’ di chuyˆ’n trˆn cung ˙ ˙ ` ` ´ ¯e a˙˙ ’’ v` gia su a ij a a a ij a o a e e e . . (vi , vj ). B`i to´n d at ra l` t` h`nh tr` dˆ’ tˆi d a lo.i nhuˆn v´.i th`.i gian nho nhˆ t. ˙´ ´ ˙’a a a ¯ˇ a ım a ınh ¯e o ¯ . ao o . . C´c vˆ n d` kh´c c´ thˆ’ ph´t biˆ’u dang b`i to´n t` c´c mach tˆi u.u trong d` thi ˙a ˙ ´e ´ a a ¯ˆ a o e e a a ım a o ¯o . ˆ . . .o.ng: Lˆp lich dˆ’ t´ to´n song song, tˆi u.u d a muc tiˆu trong xu. l´ cˆng ˙ ınh a ´ ˙yo ’ c´ hai trong lu . o a . ¯e o ¯ e . . . nghiˆp. e . B`i to´n t` mˆt mach Φ trong d` thi c´ hai trong lu.o.ng dˆ’ cu.c tiˆ’u h`m muc tiˆu ˙ ˙ a a ım o ¯o . o ˆ ¯e . ea e . . . . . . thuˆt to´n ph´t hiˆn c´c mach c´ d o d`i ˆm nhu. sau. Gia su. z (Φ) c´ thˆ’ giai quyˆt nh` ˙’ ´ oe˙ ˙˙ ’’ e o a a a ea o ¯ˆ a a . . . . rˇ ng c´c trong lu.o.ng wij v` bij l` c´c sˆ thu.c tu` y (du.o.ng, ˆm hoˇc bˇ ng khˆng) nhu.ng ` a` ´ a a a aa o . y´ a .a o . . ˙ m˜n r`ng buˆc (vi ,vj )∈Φ bij > 0, v´.i moi mach Φ trong G. (Trong hˆu hˆt c´c t` ` ´ ’aa thoa o o a e a ınh . . . .ng b ≥ 0 v´.i moi i v` j ). ˙ ’ huˆng, chˇng han c´c vˆ n d` nˆu trˆn, wij ∈ R nhu ´ ´e o a . a a ¯ˆ e e o a . ij Ch´ng ta chon mˆt gi´ tri thu. z k d oi v´.i h`m muc tiˆu z (Φ) v` x´t d` thi c´ trong ´ a.˙ ’ u o ¯ˆ o a e a e ¯o . o . ˆ . . . .o.ng lu . wij = wij − z k bij . k V´.i ma trˆn trong lu.o.ng wij m´.i, x´t b`i to´n d u.`.ng d i ngˇn nhˆ t trˆn G. C´ ba tru.`.ng ´ ´e k o a o e a a ¯o ¯ a a o o . . . .p xay ra: ˙ ’ ho. Tru.`.ng ho.p A. Tˆn tai mach c´ d o d`i ˆm Φ− sao cho `. o o o ¯ˆ a a . . . k wij < 0. )∈Φ− (vi ,vj Tru.`.ng ho.p B. Khˆng tˆn tai mach c´ d o d`i ˆm v` `. o o o o ¯ˆ a a a . . . k wij > 0 (vi ,vj )∈Φ v´.i moi mach Φ. o . . Tru.`.ng ho.p C. Tˆn tai mach c´ d o d`i bˇ ng khˆng (nhu.ng khˆng c´ mach d o d`i ˆm); o ¯ˆ a ` `. o o a o o o. ¯ˆ a a . . . . .c l` t´ a u k wij = 0 (vi ,vj )∈Φ0 v´.i mach Φ0 n`o d o. o a ¯´ . 97
Trong Tru.`.ng ho.p A ch´ng ta c´ thˆ’ n´i rˇ ng z ∗ (gi´ tri cu.c tiˆ’u cua z ) nho ho.n z k v` ˙ ˙˙ o eo` ’ ˙ ’ o u a a.. e ı . k wij − z k wij ≡ bij < 0 )∈Φ− )∈Φ− )∈Φ− (vi ,vj (vi ,vj (vi ,vj chı c´ thˆ’ d ung nˆu ˙ ´ ˙ o e ¯´ ’ e wij (vi ,vj )∈Φ−1 < zk −1 bij (vi ,vj )∈Φ m` hiˆ’n nhiˆn chı ra rˇ ng z ∗ < z k . ˙ ` ˙ ’ ae e a Tu.o.ng tu., trong Tru.`.ng ho.p B ta c´ thˆ’ n´i rˇ ng z ∗ > z k ; v` trong Tru.`.ng ho.p C ˙ o eo` o a a o . . . ∗ k th` z = z . ı Do d o thuˆt to´n t` kiˆm nhi phˆn dˆ’ giai quyˆt b`i to´n nhu. sau: Kho.i d` u v´.i ˙’ ´ ´ . a ¯e ˙ ˙ ¯ˆ o ’a ¯´ a a ım e ea a . . z 1 ; nˆu n´ qu´ l´.n (t´.c l` Tru.`.ng ho.p A) thu. v´.i z 2 < z 1 ; nˆu n´ qu´ nho (t´.c ´ ´ a.˙ ’ ˙o ’ ˙u ’ gi´ tri thu e o ao ua o eoa . .`.ng ho.p B) thu. v´.i z 2 > z 1 . Khi d ˜ c´ c´c cˆn trˆn v` du.´.i (z v` z tu.o.ng u.ng) ta ˙o ’ l` Tru o a ¯a o a a eao ual ´ . . ˙ x´c d .nh z ∗ bˇ ng c´ch thu. z k = (zu + zl )/2 v` thay zu bˇ ng z k nˆu xay ra Tru.`.ng ’ a ¯i ` ` ´˙ ˙ ’ ’ c´ thˆ oe a a a a e o ho.p A, hoˇc thay zl bˇ ng z k nˆu xay ra Tru.`.ng ho.p B. Do sˆ c´c ph´p thu. tı lˆ v´.i 1/η, ` ´˙ ´ ’ ˙ ˙e o ’ ’. a a e o oa e . . . 1 l` sai sˆ cho tru.´.c, v` do mˆi lˆn thu. (x´c d .nh mach d ˆ d`i ˆm hoˇc ˜a ´ o` ˙ a ¯i ’ trong d o 0 < η ¯´ a o o a . ¯o a a a . . t´ to´n ma trˆn trong lu.o.ng) d oi hoi n3 ph´p to´n, nˆn t` nghiˆm cua b`i to´n trˆn d oi ¯` ˙ ’ ˙aa ’ ınh a a e a e ım e e ¯` . . . . hoi O[n3 log 1/η ] ph´p to´n. ˙ ’ e a 98
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 . 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 ¯. 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 . . 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. . . 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 . . . 103
nut 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` ´ 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 . . 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 . . 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 ´` ˙. ’ bao tr`m”. Kh´i niˆm cˆy bao tr`m lˆ ¯a u ae a uaˆ e¯. 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 . 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 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 . . .. . 108