Lí thuyết đồ thị part 4

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

Thêm vào BST

Báo xấu

89
lượt xem 17
download

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

Các lưới có nhiều ứng dụng trong khía cạnh thực tiễn của lý thuyết đồ thị, chẳng hạn, phân tích lưới có thể dùng để mô hình hoá và phân tích mạng lưới giao thông hoặc nhằm "phát hiện" hình dáng của Internet - (Xem thêm các ứng dụng đưới đây. Mặc dù vậy, cũng nên lưu ý rằng trong phân tích lưới, thì định nghĩa của khái niệm "lưới" có thể khác nhau và thường được chỉ ra bằng một đồ thị đơn giản.)...

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 4

• •...... • • .. .. . . . .. . . . . .. . . .. . . . . . . .. .. . . .. .. . . . . .. .. . . .. .. . . . . .. . . . .. . . . .. . . .. ... .. . . . . .. ... . . . . •.................................................•................................................• • • • • .. .. . . . . .. . . . ... .. .. . ...................................................... ..................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • . . . . . . . . . (a) (b) (c) (d) H` 2.10: C´c d` thi h` sao. ınh a ¯ˆ . ınh o Diˆu kiˆn d u. Ngu.o.c lai, nˆu g khˆng ch´.a mˆt dˆy chuyˆn n`o c´ d o d`i l´.n ho.n hoˇc -` ´ ` e ¯˙ ’ e e o u oa e a o ¯ˆ a o a . .. . . . ` ng ba th` c´c th`nh phˆn cua n´ phai c´ mˆt trong c´c dang “h` sao” nhu. trong H` `a˙o ’ ˙oo ’ bˇ a ıa a a. ınh ınh . 2.10. Hiˆ’n nhiˆn nˆu xo´ bˆ t k` mˆt canh cua d` thi h` sao th` s˜ c´ ´ nhˆ t mˆt d ınh ˙ ´ ´ ´ o ¯˙ ˙ ¯ˆ . ınh ’o .’ e ee aa y o . ı e o ıt a . .i canh c`n lai cua g. Vˆy g l` phu tˆi thiˆ’u. ˙ ’´ o.˙ ’ ˙o khˆng liˆn thuˆc v´ . o e oo a a e . . V´ du 2.5.4 Gia su. d` thi trong H` 2.11 biˆ’u diˆn ban d` giao thˆng cua mˆt th`nh ˙ ˜ ˙ ˙ ¯ˆ . ’’o ˙ ¯o ’ ˙ ’ ı. ınh e e ˆ o o a . .`.ng xay ra tˇc ngh˜n v` mˆ i canh tu.o.ng u.ng mˆt ˜’ ´ ˜ ´ o ¯˙ ˙ ’ phˆ. Mˆ i d ınh l` mˆt n´t giao thˆng thu o o aou o a eao. ´ o . . ˙ gi´m ’a ´ ` ¯ˇ a ¯o ` d ai lˆ nˆi hai n´t giao thˆng. Cˆn d at c´c d ˆi tuˆn tra trˆn c´c d ai lˆ sao cho c´ thˆ ¯. o o u o a a e a ¯. o oe . . . . s´t tˆ t ca c´c n´t giao thˆng. Vˆ n d` d ˇt ra l` sˆ tˆi thiˆ’u c´c d ˆi tuˆn tra l` bao nhiˆu? ˙ ´’ ´ e. ´´ e a ¯o ` aa ˙a u o a ¯ˆ ¯a aoo a a e . Cˆu tra l`.i ch´ l` t` phu tˆi thiˆ’u v´.i sˆ phˆn tu. ´ nhˆ t cua d` thi. Dˆ kiˆ’m tra hai ˙ e˙ ˜e ’´ e oo` ´ a ˙ ıt a ˙ ¯o . ´’ˆ ˙o ’ ˙o ’ a ınh a ım tˆp sau l` phu tˆi thiˆ’u: ˙ ’´ ˙o a a e . {(a, d), (b, e), (c, f ), (f, i), (g, h), (k, l)} v` a {(a, b), (b, d), (b, e), (c, f ), (f, g ), (f, i), (h, l)}. Do c´ 11 d ınh v` mˆi canh phu nhiˆu nhˆ t hai d ınh nˆn khˆng thˆ’ phu d` thi ´ ho.n s´u ˙ ˜ ` ´ ¯˙’ ˙ ’ ¯˙’ ˙ ¯o . ıt ’ˆ o ao. e a e o e a canh. . e h b •.........................................................................•.........................................................................•..........................................................................• l .. .. ... .. .. .. .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . ... ... ... ... ... ... . . . . . . . . . . . . ... ... ... ... ... ... . . . . . . . . . . ... ... ... ... ... ... . . . . . . . . ... ... ... . . . . ... ... ... . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . ... ... ... . . ... ... ... . . . . ... . ... . . ... . ... . ... . ... . . . ... . ... . ... . . . ... . . ... . . ... . . . . a• .. .. • • •k . . .. ............................... ............................................................. ................................................................................................. . .. .. . . ... .. ... ... .. ... . ... . .... . ... . . .. . . ... g . . ..... ... . ... ... . d .. . ... .. . . ..... . . ... ... ... ... . ... . . . ... ... ... . ... ... . . ... . . ... ... ... . ... ... . ... . . . ... ... ... . ... ... . . ... . . ... . ... . .. ... . ... ... . . .. . . ... ... ... . ... . ... ... . . ... ... . . ... ... ... . ... . . ... . ... ... . ... . ..... ... ... . ..... . . ... . . ... . ... . ... ... . . ... . .... ... . ... . .. . ... . .. . . . • • •i .... .................................................................. ................................... ............................ ..... .. .. .. .. .. .. c . f .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ... .... ...... ......... ................ .... H` 2.11: ınh 67
Cu.c tiˆ’u ho´ h`m Boole ˙ e aa . Mˆt phˆn quan trong trong viˆc thiˆt kˆ c´c mach sˆ l` cu.c tiˆ’u ho´ h`m Boole tru.´.c khi ˙ ` ´´ ´ o a e e ea oa . e aa o . . . . . ta muˆn xˆy du.ng mach logic cho bo.i h`m Boole bˆn biˆn ´´ ´ ´ ´ ˙˙ ’’ ˙a ’ thiˆt kˆ n´. Gia su e eo oa o e . . f (x, y, z, w) = w x y z + w x y z + w x y z + w xyz + w xyz + wxyz. Ch´ng ta h˜y biˆ’u diˆn mˆi mˆt trong bay th`nh phˆn cua f bo.i mˆt d ınh v` mˆt canh ˙ ˜ ˜ ` ˙ ’ ˙ ’ ˙ ’ o ¯˙ .’ u a e e oo a a ao. . . ´ -ˆ . liˆn thuˆc hai d ınh nˆu v` chı nˆu hai th`nh phˆn chı kh´c nhau d ung mˆt biˆn. D` thi ´ ’´ ` ¯˙ ’ e a ˙e ˙a ’ e o a a ¯´ o e o . . .o.ng u.ng h`m f cho trong H` 2.12. tu ´ a ınh w xyz •. .. .... ... ... ..... ... ..... ... ... ... .. ... . ... ... ... ... e.3................... e4 ... ... ... ... wxyz ... e2 e7 ... wxyz .. . ... ... ... ... ... ... . . ... ... ... ... • • • • . ........................................................ ........................................................ ........................................................ ........................................................ ... .. ... . . ... ... . ... ... . ... . ... ... w x yz w xyz . ... . . . ... . ... ... ... . . . ... e5 e6 . ... ... . ... . ... . ... ... .. . . ... ... ... ... . . ... ... ... . ... . ... ... . ... ... . . ... ... ... ..... ... ..... . e1 . • . . .. .. . . . . . . w x yz . . . . . . . . . . . . . . . . . . . • . . . wx y z H` 2.12: ınh Mˆt canh liˆn thuˆc hai d ınh tu.o.ng u.ng mˆt th`nh phˆn v´.i ba biˆn. ` ´ ¯˙’ o. e o ´ o a ao e . . . Mˆt phu tˆi thiˆ’u cua d` thi cho ta mˆt d o.n gian ho´ h`m Boole f, v´.i c`ng ch´.c ˙ ’´ ˙o ˙ ¯o . ’ ˙ ’ o e ˆ o¯ aa ou u . . . f nhu.ng thiˆt kˆ su. dung ´ cˆ’ng logic ho.n. ˙ ´ e ˙ . ıt o ´’ nˇng nhu a e C´c canh treo e1 v` e7 cˆn thuˆc moi phu cua d` thi. Bo.i vˆy c´c th`nh phˆn x y z ` ` ˙ ˙ ¯o . ’’ ˆ ˙aa ’. a. a a o a a . . ˙ khu. d u.o.c. Hai canh e3 v` e6 (hoˇc e4 v` e5 , hoˇc e3 v` e5 ) s˜ phu c´c ’ ˙¯.’ ˙a ’ v` xyz l` khˆng thˆ a ao e a a a a a e . . . d ınh c`n lai. Do d o ta c´ thˆ’ viˆt lai ˙´ ¯˙’ o. ¯´ oee. f = x y z + xyz + w y z + w y z. w yz •. . . . . . . . . . . xyz . . . . . . . . • • . . . . . . . . xyz . . . . . . . . . . . . . . • . . . w yz H` 2.13: ınh 68
Biˆ’u th´.c n`y lai c´ thˆ’ biˆ’u diˆn bo.i d` thi trong H` 2.13. ˙ ˙˙ ˜ ˙ ¯o . ’ˆ e ua.oee e ınh C´c th`nh phˆn x y z v` xyz khˆng thˆ’ phu bo.i mˆt canh do d o khˆng thˆ’ cu.c tiˆ’u ˙ ˙ ˙ ` ˙˙ ’’ a a a a o e o. ¯´ o e. e . .i ch´ng. Ngo`i ra c´ mˆt canh phu hai d ınh c`n lai w y z v` w y z . Do d o biˆ’u th´.c ˙ ˙ ’ ¯˙’ thˆm v´ e o u a oo. o. a ¯´ e u . ´i thiˆ’u l` ˙a Boole tˆ o e f = x y z + xyz + w y . Nhˆn cu a d` thi ˙ ¯ˆ . ’ 2.6 a o y`` ´ 2.6.1 C´c d .nh l´ vˆ tˆn tai v` duy nhˆ t a ¯i eo .a a X´t d` thi G := (V, Γ). Ta n´i tˆp ho.p S ⊂ V l` nhˆn cua d` thi G nˆu S l` tˆp ˆ’n d .nh .˙ ´ ˙ ¯o . ’ˆ e ¯o . ˆ oa aa e a a o ¯i . . .c l` nˆu ´ a˙ ’ trong v` ngo`i cua G; t´ a e a u ´ 1. Nˆu v ∈ S th` Γ(v ) ∩ S = ∅; v` e ı a ´ 2. Nˆu v ∈ S th` Γ(v ) ∩ S = ∅. e / ı Diˆu kiˆn (1) suy ra rˇ ng nhˆn S khˆng c´ khuyˆn; d iˆu kiˆn (2) suy ra nhˆn S ch´.a moi -` ` e ¯` e e a a o o e e a u . . . ´ ¯˙’ ˙a a ’ d ınh v ∈ V c´ Γ(v ) = ∅; ngo`i ra, r˜ r`ng tˆp trˆng ∅ khˆng phai l` nhˆn. o a oa a o o . V´ du 2.6.1 [Von Neumann-Morgenstern] Kh´i niˆm nhˆn d` u tiˆn d u.o.c d u.a v`o l´ ı. a e a ¯aˆ e ¯. ¯ ay . ´t tr` cho.i v´.i tˆn goi l` “l`.i giai”. ˙ ’ thuyˆ o e oe .ao Gia su. c´ n d a u thu, k´ hiˆu l` (1), (2), . . . , (n), ho c´ thˆ’ thoa thuˆn v´.i nhau dˆ’ ˙ ˙ ´ ˙ ˙ o ¯ˆ ’’ ˙yea ’ ˙ ’ .o e ao ¯e . . .p V ; nˆu d ˆ u thu (i) u.ng t` thˆ a ho.n t` thˆ b th` ta viˆt ´ ´´ ´ ´ ´ ˙ ’ chon t` thˆ v trong tˆp ho . ınh e a e ¯a ınh e ınh e ı e . . a b. Hiˆ’n nhiˆn l` quan hˆ tiˆn th´. tu. to`n phˆn1 . V` nh˜.ng su. th´ u.ng cua c´c c´ ˙ e` ` ˙aa ’ e e a e u. a a ıu ıch ´ . . c´ thˆ’ khˆng ph` ho.p nhau nˆn ta phai d u.a thˆm kh´i niˆm th´ u.ng hiˆu qua ˙ ˙¯ ’ ˙ ’ nhˆn a oeo u. e e ae ıch ´ e . . ´u t` huˆng a d u.o.c th´ u.ng hiˆu qua ho.n t` huˆng b (k´ hiˆu a b) th` ngh˜ ´ ´ ˙ ’ . Nˆ ınh o e ¯. ıch ´ e ınh o ye ı ıa . . l`: c´ mˆt tˆp d ˆ u thu, do cho rˇ ng a ho.n b nˆn ho c´ thˆ’ cho quan d iˆ’m cua m` thˇng ˙ ˙ ` ´ ´ ˙’ ˙ ’ a o o a ¯a a e oe ¯e ınh a .. . ´´ ´ ´ ˙o ’ ˙a ’ thˆ; nˆu ngo`i ra lai c´ b c th` c´ mˆt tˆp c´c d a u thu c´ kha nˇng l`m cho t` huˆng b ee a .o ı o o a a ¯ˆ a ınh o .. thˇng thˆ; nhu.ng v` tˆp ho.p th´. hai khˆng bˇt buˆc phai tr`ng v´.i tˆp ho.p th´. nhˆ t nˆn ´ ´ ´ ´ ˙u ’ a e ıa u o a o oa uae . . . . . c´ thˆ’ khˆng bˇt buˆc a c : quan hˆ khˆng c´ t´ bˇc cˆu2 ! ˙ ´ ´a o ınh a ` oeo a o e o . . Quan hˆ trˆn tˆp V l` tiˆn th´. tu. to`n phˆn nˆu n´ thoa m˜n: t´ phan xa, t´ bˇc cˆu v` hai ´aa 1 a` ` ´o . ınh a ` ˙a ’ ˙ ’ e ea e u. a ae ınh . . phˆn tu. bˆ t k` a, b ∈ V th` hoˇc a b hoˇc b a. ` ’´ a ˙ay ıa a . . Thuˆt ng˜. th´ u.ng hiˆu qua do G. T. Guilbaud d u.a ra trong [40]; Von Neumann v` Morgenstern lai 2 ˙ ’ a u ıch ´ e ¯ a . . . d`ng danh t`. ´p d ao. Vˆ c´c c´ch ph´t biˆ’u to´n hoc kh´c cua su. th´ u.ng hiˆu qua, xem [5]. ˙ `a a u a ¯˙ ’ a ˙ . ıch ´ ’ ˙ ’ u e a e a e . . 69
Bˆy gi`. x´t d` thi G = (V, Γ) trong d o Γ(x) l` tˆp c´c t` huˆng d u.o.c th´ u.ng ´ ¯. a o e ¯ˆ . o ¯´ a a a ınh o ıch ´ . .n x. Goi S l` nhˆn (nˆu c´) cua d` thi. Von Neumann v` Morgenstern d` nghi ´ ˙ ’ e o ˙ ¯ˆ . ’o hiˆu qua ho e aa a ¯ˆ e . . . .i v´.i c´c phˆn tu. cua S thˆi. Su. ˆ’n d inh trong cua S biˆ’u thi rˇ ng: ˙ ˙ ` ´ ` ˙. ’ a˙˙ ’’ ˙’ chı han chˆ tr` cho o a eo o o ¯. e a . . khˆng c´ mˆt t` huˆng n`o cua S d u.o.c th´ u.ng hiˆu qua ho.n mˆt t` huˆng kh´c x; ´ ´ a˙ ’ ˙ ’ o o o ınh o ¯. ıch ´ e o ınh o a . . . su. ˆ’n d .nh ngo`i cua S biˆ’u thi rˇ ng: moi t` huˆng x khˆng thuˆc S khˆng d u.o.c th´ ˙ ˙ ` ´ a˙ ’ o ¯i e a ınh o o o o ¯. ıch . . . . .ng hiˆu qua ho.n mˆt t` huˆng n`o d o cua S, do d o t` huˆng x lˆp t´.c d u.o.c loai tr`.. ´ ´ ˙ ’ a ¯´ ˙ ’ u ´ e o ınh o ¯´ ınh o a u¯. .u . . . V´ du 2.6.2 Khˆng phai moi d` thi d` u c´ nhˆn. Nˆu d` thi c´ nhˆn S0 th` c´c sˆ ˆ’n ´˙ ´o ˙ ’ ı. o . ¯o . ¯ˆ o a ˆ e e ¯ˆ . o a ı a oo ` u kiˆn: ˙o ’ ˙ a ¯e ’ d .nh cua n´ thoa m˜n d iˆ ¯i e. α(G) = max #S ≥ #S0 ≥ min = β (G). S ∈S T ∈T -ˆ . D` thi trong H` 2.14 khˆng c´ nhˆn v` o ınh o oaı α(G) = 1 < 2 = β (G). Tr´i lai, d` thi trong H` 2.15 c´ hai nhˆn l` S = {b, d} v` S = {a, c}. a . ¯ˆ . o ınh o aa a c • . . . .. .. .. .. ... .. ... .. . .. .. .. . .. .. .. . .. .. .. . .. .. .. . .. .. .. .. .. .. .. . .. .. ... .. .. . . .. .. ... . ... ... .. .. . . .. .. .. .. .. .. . .. .. .. . .. .. .. . .. .. .. . .. .. .. .. .. .. .. . .. .. .. . • • .. ....................................................... . ..................................................... . . .. . .. . a b H` 2.14: ınh Bˆy gi`. ta d u.a ra tiˆu chuˆ’n dˆ’ nhˆn biˆt mˆt d` thi c´ nhˆn hay khˆng, v` nhˆn c´ ˙ ˙. ´ o ¯o . o a a o ¯ e a ¯e a e .ˆ o aao ´ duy nhˆ t khˆng? a o d •...........................................................................................................• c .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . ... . . ... . . . . . . . .... . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • . . ........................................................ . .. . ...................................................... . .. a b H` 2.15: ınh 70
Dinh l´ 2.6.3 Nˆu S l` nhˆn cu a d` thi (V, Γ) th` S l` tˆp ho.p cu.c d ai trong ho S c´c -. ´ ˙ ¯ˆ . ’o y e aa ı aa . . ¯. a . . tˆp ˆ’n d. nh trong; t´.c l` ˙ a o ¯i ua . A ∈ S , S ⊂ A ⇒ A = S. Ch´.ng minh. Thˆt vˆy, gia su. ngu.o.c lai tˆn tai tˆp ˆ’n d .nh trong A ch´.a nhˆn S v` A = S. .˙ . . ` . a o ¯i ˙˙ ’’ u aa o u a a .. . d ´ suy ra Γ(a) ∩ S = ∅. Vˆy Γ(a) ∩ A = ∅, mˆu ¯´ ` . Khi d o tˆn tai a ∈ A sao cho a = S ; t` ¯o o u a a . .i A ∈ S . ˜ thuˆn v´ ao Dinh l´ 2.6.4 Trong d` thi d ˆi x´.ng khˆng khuyˆn, moi tˆp ho.p cu.c d ai cu a ho S c´c -. ´ . ¯. ˙ ’ y ¯ˆ . ¯o u o o e .a a . . . tˆp ho.p ˆ’n d. nh trong d` u l` nhˆn ˙ a . o ¯i ¯ˆ a a e . Ch´.ng minh. Gia su. S l` tˆp ho.p cu.c d ai trong S , ta phai ch´.ng minh rˇ ng moi d ınh a ∈ S ` ˙˙ ’’ ˙ ’ . ¯˙ ’ u aa . ¯. u a / . . .i d ınh a ∈ S th` tˆp A = S ∪ {a} d` u thoa m˜n Γ(a) ∩ S = ∅. Thˆt vˆy, nˆu Γ(a) ∩ S = ∅ v´ ¯˙ ´ ˙a ’ o’ ¯ˆ e aa e ıa .. . ˆ’n d .nh trong (v` a ∈ Γ(a), d` ng th`.i S ⊂ A, A = S, mˆu thuˆn v´.i gia thiˆt S l` tˆp ˆ’n ˙ .˙ ˜ ´ ˙ ’ o ¯i ı/ ¯ˆ o o a ao e aao .c d ai. d .nh trong cu ¯ . ¯i . Hˆ qua 2.6.5 Moi d` thi d ˆi x´.ng khˆng khuyˆn d` u c´ nhˆn. ´ ˙ ’ e . ¯ˆ . ¯o u o o e ¯ˆ o a e . Ch´.ng minh. Thˆt vˆy, lˆp d` thi phu (S , Γ) c´ c´c d ınh l` c´c tˆp ˆ’n d inh trong cua d` ¯ o a ¯˙ .˙ ’ ˙ ¯ˆ ’o u a a a ¯o . ˆ a a a o ¯. .. . . .ng d ˜ cho, v` S ∈ Γ nˆu v` chı nˆu S ⊂ S. D` thi phu l` cam u.ng, vˆy theo ¯S e a ˙ e -ˆ . ´ ´ ’´ .a˙ ´ ’ thi d ˆi x´ . ¯o u ¯a a o a . ˙ d` Zorn, tˆn tai d ınh S ∈ S khˆng c´ d`ng d˜i nˆn S l` tˆp ˆ’n d inh trong cu.c d ai v` ’ ¯ˆ ˙ ¯. ` . ¯˙ ’ Bˆ e o o o oo oe aao . ¯. a . - inh l´ 2.6.4 S l` nhˆn cua d` thi d a cho. ˙ ¯o . ¯˜ ’ˆ theo D. y aa Trong d` thi d ˆi x´.ng khˆng khuyˆn, qu´ tr` t` nhˆn l` nhu. sau: ´ ¯ˆ . ¯o u o o e a ınh ım a a ´ ´ ´ o ¯˙ ’ o ¯˙’ Lˆ y mˆt d ınh bˆ t k` v0 v` d ˇt S0 = {v0 }; sau d o lˆ y mˆt d ınh v1 ∈ Γ(S0 ) v` d at a ay a ¯a ¯´ a / a ¯ˇ . . . . S1 = S0 ∪ {v1 }; tiˆp theo lˆ y v2 ∈ Γ(S1 ) v` d ˇt S2 = S1 ∪ {v2 }; v` vˆn vˆn. V` d` thi h˜.u ´ ´ e a / a ¯a aa a ı ¯ˆ . u o . han nˆn s´.m hay muˆn ta s˜ d u.o.c Γ(Sk ) = V, v` v` Sk l` tˆp ho.p cu.c d ai cua S nˆn n´ l` . ¯. ˙ ’ eo o e¯ . aı aa e oa . . . . nhˆn. a Dinh l´ 2.6.6 Diˆu kiˆn cˆn v` d u dˆ’ tˆp S l` nhˆn l` h`m d ˇc tru.ng cu a n´ -. -` ’ ˙. e ` a ¯ ˙ ¯e a ˙ ’o y e .a a a a a ¯a . ´ 1 nˆu x ∈ S, e ϕS (x) := nˆu ngu.o.c lai, ´ 0 e .. thoa m˜n hˆ th´.c ˙aeu ’ . ϕS (x) = 1 − max ϕS (y ). y ∈Γ(x) Nˆu Γ(x) = ∅ th` ta quy u.´.c ´ e ı o max ϕS (y ) = 0. y ∈Γ(x) 71
Ch´.ng minh. Diˆu kiˆn cˆn. Gia su. S l` nhˆn. Do t´ ˆ’n d .nh trong nˆn ϕS (x) = 1 suy -` ˙ e` ˙˙ ’’ u e .a aa ınh o ¯i e ra x ∈ S v` do d ´ a ¯o max ϕS (y ) = 0. y ∈Γ(x) Mˇt kh´c, do t´ ˆ’n d .nh ngo`i nˆn ϕS (x) = 0 suy ra x ∈ S v` do d ´ ˙ a a ınh o ¯i ae / a ¯o . max ϕS (y ) = 1. y ∈Γ(x) T`. d ´ suy ra hˆ th´.c d ˜ ph´t biˆ’u. ˙ u ¯o e u ¯a a e . Diˆu kiˆn d u. Gia su. ϕS (x) l` h`m d ac tru.ng cua mˆt tˆp ho.p S n`o d o. Nˆu hˆ th´.c cua -` ´. e ¯˙’ ˙˙ ’’ ˙ ’ a ¯´ e e u ˙ ’ e a a ¯ˇ oa . . .. . ˙a ’ d .nh l´ thoa m˜n th` ta c´ ¯i y ı o 1. x ∈ S suy ra ϕS (x) = 1 nˆn maxy∈Γ(x) ϕS (y ) = 0. Vˆy Γ(x) ∩ S = ∅. e a . 2. x ∈ S suy ra ϕS (x) = 0 nˆn maxy∈Γ(x) ϕS (y ) = 1. Vˆy Γ(x) ∩ S = ∅. / e a . Do d o S l` nhˆn. ¯´ aa Dinh l´ 2.6.7 [Richardson] Nˆu d` thi h˜.u han khˆng c´ mach v´.i d ˆ d`i le , th` n´ c´ -. ´o o ¯o a ˙ ’ y e ¯ˆ . u o o. ıoo . . .ng khˆng nhˆ t thiˆt duy nhˆ t). ´ ´ ´ nhˆn (nhu a o a e a Ch´.ng minh. Xem, chˇng han [4]. ˙ ’ u a . Tr` cho.i Nim 2.6.2 o Gi˜.a hai d ˆ u thu m` ch´ng ta k´ hiˆu l` (A) v` (B ) c´ mˆt d` thi (V, Γ) cho ph´p x´c ´ ˙au ’ u ¯a yea a o o ¯o . .ˆ ea . d .nh mˆt tr` cho.i n`o d o, trong tr` cho.i ˆ y mˆi thˆ l` mˆt d ınh cua d` thi; d ınh kho.i d` u ˜ ´ ´ e a o ¯˙ ’ ˙ ¯o . ¯˙ ’ˆ ’ ˙ ¯a ’ˆ ¯i oo a ¯´ o a o . . .o.c chon bˇ ng c´ch r´t thˇm, v` c´c d a u thu lˆn lu.o.t d i: d` u tiˆn d a u thu (A) chon ` ´ ˙` ´ ’a ˙ ’ v0 d u . ¯ a a u a a a ¯ˆ . ¯ ¯ˆ a e ¯ˆ . . ˙nh v1 trong tˆp ho.p Γ(v0 ); sau d ´ (B ) chon d ınh v2 trong tˆp Γ(v1 ); tiˆp theo (A) lai chon ´ ’ ˙’ dı ¯ a ¯o .¯ a e . . . . . d ınh v3 trong tˆp Γ(v2 ), . . . . Nˆu mˆt d a u thu chon d u.o.c d ınh vk m` Γ(vk ) = ∅ th` v´n d ´ ´ ´ ¯˙’ ˙ . ¯ . ¯˙ ’ ’ a e o ¯ˆ a ı a ¯o . . kˆt th´c; d ˆ u thu n`o chon d u.o.c d ınh cuˆi c`ng th` thˇng cuˆc v` d a u thu kia thua. Hiˆ’n ˙ ´ ´ ´ ´ ´ ˙a ’ ¯ . ¯˙ ’ ˙ ’ e u ¯a ou ıa o a ¯ˆ e . . .u han nˆn cuˆc cho.i s˜ kˆt th´c sau mˆt sˆ h˜.u han bu.´.c. nhiˆn do ta chı x´t d` thi h˜ ´ .´ ˙ e ¯o . u ’ e ˆ e o ee u oou o . . . Dˆ’ ky niˆm mˆt tr` cho.i tiˆu khiˆ’n quen thuˆc m` Nim d ˜ tˆ’ng qu´t ho´, ta goi tr` -e ˙ e ˙’. ˙ ˙ oo e e o a ¯a o a a .o . . .i v`.a mˆ ta l` tr` cho.i Nim v` k´ hiˆu l` (V, Γ) c˜ng nhu. d` thi x´c d inh n´. B`i to´n o˙a o’ cho u ay e a u ¯ˆ . a ¯. o oaa . d at ra l` ph´t hiˆn c´c thˆ thˇng; ngh˜ l` c´c d ınh cua d` thi m` ta phai chon dˆ’ bao d am ˙’ ´´ ıa a a ¯˙ ’ ˙ ¯ˆ . a ’o ˙ ’ ¯e ˙ ¯ ˙ ’ ¯ˇ aaea ea . . . .o.ng chˆng tra ra sao. Kˆt qua chu yˆu nhu. sau: ´ ´ ´ ´ ´ ’´ ˙’ ˙ ’ ˙e chˇc thˇng mˇc d` d oi phu a a a u ¯ˆ o e . 72
-. Dinh l´ 2.6.8 Nˆu d` thi c´ nhˆn S v` nˆu mˆt d ˆi thu d ˜ chon mˆt d ı’nh trong nhˆn S, ´o ´ .´ ˙ ¯a . ’ o ¯˙ y e ¯ˆ . o a ae o ¯o a . ´ a ˙ ¯˙ ’ ’ th` viˆc chon n`y ba o d a m cho anh ta thˇ ng hoˇc ho`. ıe a a a . . . Ch´.ng minh. Thˆt vˆy, nˆu d a u thu (A) chon d ınh v1 ∈ S th` hoˇc Γ(v1 ) = ∅ l´c d ´ anh ´ ´ ˙ ’ . ¯˙’ u aa e ¯ˆ ıa u ¯o .. . ´ng; hoˇc d oi phu.o.ng buˆc phai chon mˆt d ınh v2 trong V \ S, do d o dˆn lu.o.t m` ´ ´ ˙ ’ o ¯˙ .’ ta thˇ a a ¯ˆ o ¯´ ¯e ınh, . . . . d a u thu (A) lai c´ thˆ’ chon mˆt d ınh v3 ∈ S v` c´. nhu. thˆ m˜i. Nˆu dˆn mˆt l´c n`o d o, ˙ ´ ´ ´´ ˙ ’ o ¯˙ ’ ¯ˆ oe. au ea e ¯e o u a ¯´ . . . ’´ ` ´ ˙a o ¯˙ ’ mˆt trong c´c d a u thu thˇng bˇ ng c´ch chon mˆt d ınh vk m` Γ(vk ) = ∅ th` ta c´ vk ∈ S. o a ¯ˆ a a a ı o . . . ´u thu thˇng nhˆ t d .nh phai l` (A). Ta c´ d iˆu phai ch´.ng minh. ’´ ´ ¯i ` ˙a ˙a ’ ˙ ’ Vˆy d ˆ a ¯a a o ¯e u . Mˆt phu.o.ng ph´p co. ban dˆ’ cho.i tˆt l` t` h`m Grundy (nˆu n´ tˆn tai) (xem [4]) ˙ ´ e o` . ´ ˙ ¯e ’ o a o a ım a o . . d o suy ra nhˆn cua d` thi d ˜ cho. Ban d oc quan tˆm vˆ c´c tr` cho.i trˆn d` thi c´ `a ˙ ¯o . ¯a ’ˆ v` t` ¯´ au a . ¯. a e o e ¯o . o ˆ thˆ’ xem [4] (Chu.o.ng 6). ˙ e 73
74
Chu.o.ng 3 C´c b`i to´n vˆ d .`.ng d a ` ¯u o a a e ¯i Trong c´c u.ng dung thu.c tˆ, ta cˆn t` d u.`.ng d i (nˆu c´) gi˜.a hai d ınh cua d` thi. Dˇc ˙ ¯o . - a ´ ` ım ¯ o ´ ¯˙ ’ ’ˆ a´ .e a ¯ eo u . . .`.ng d i ngˇn nhˆ t gi˜.a hai d ınh cua mˆt d` thi c´ y ngh˜ to l´.n. C´ ´ ´u ¯˙ ’ ˙ ’ biˆt, b`i to´n t` d u o e a a ım ¯ ¯ a a o ¯o . o ´ ˆ ıa o o . . ˙ dˆn vˆ b`i to´n nhu. vˆy t`. nhiˆu b`i to´n thu.c tˆ. V´ du, b`i to´n t` h`nh tr` ’a `a ˜e ` ´ thˆe a au e a a .e ı.a a ım a ınh . tiˆt kiˆm nhˆ t (theo tiˆu chuˆ’n khoang c´ch, th`.i gian hoˇc chi ph´ trˆn mˆt ban d` giao ˙ ´e ´ ˙ ’ o ˙ ¯o ’ e a e a a o a ı) e ˆ . . . thˆng; b`i to´n chon phu.o.ng ph´p tiˆt kiˆm nhˆ t dˆ’ d u.a mˆt hˆ d ong lu.c t`. trang th´i ´˙ ´e o a a a e a ¯e ¯ o e ¯ˆ .u. a . . ... ´t nhiˆu phu.o.ng ph´p du.a trˆn l´ thuyˆt d` ` ´ ¯ˆ n`y sang trang th´i kh´c v.v... Hiˆn nay c´ rˆ a a a e oa e a ey eo . . . thi to ra l` c´c phu.o.ng ph´p c´ hiˆu qua nhˆ t. ´ ˙’ ˙ ’a aa aoe . . Chu.o.ng n`y tr` b`y c´c thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t trˆn d` thi c´ trong sˆ. ´ ´ ´ a ınh a a a a ım ¯ o ¯ a a e ¯ˆ . o . o o . Du.`.ng d gi˜.a hai d ˙nh -o ’ 3.1 ¯i u ¯ı Du.`.ng d gi˜.a hai d ˙nh -o ’ 3.1.1 ¯i u ¯ı Trong nhiˆu tru.`.ng ho.p, ch´ng ta cˆn tra l`.i cˆu hoi: Tˆn tai d u.`.ng d i µ t`. d ınh s dˆn ` ` ` . ¯o ´ ˙o a ’ ˙ ’ u ¯˙ ’ e o u a o ¯ ¯e . .´.ng G := (V, E )? Nˆu c´, h˜y chı ra c´ch d i cua d u.`.ng d i µ. d ınh t cua d` thi c´ hu o ´ ¯˙’ ˙ ¯o . o ’ˆ ˙ ’ a ¯ ˙ ¯o ’ eoa ¯ L`.i giai cua b`i to´n n`y kh´ d o.n gian: ch´ng ta chı cˆn ´p dung thuˆt to´n t` kiˆm ˙` a ´ ˙˙aaa ’’ ˙ ’ ’a o a¯ u a a ım e . . theo chiˆu rˆng (hoˇc chiˆu sˆu) trˆn d` thi c´ hu.´.ng G nhu. sau. G´n mˆ i d ınh cua G mˆt ˜’ `o `a o ¯˙ ˙ ’ e. a e e ¯ˆ . o o o a o . . .o.ng ph´p lˇp, dˆn dˆn ta s˜ cho mˆ i d ınh v mˆt chı sˆ n`o d o bˇ ng d o ` ˜’ ˙ o a ¯´ ` ’´ a `` ’´ ˙o o ¯˙ chı sˆ. Bˇ ng phu aa aa e o a ¯ˆ . . . d`i d u.`.ng d i ngˇn nhˆ t (sˆ cung ´ nhˆ t) t`. s t´.i v. D´nh dˆ u d ınh s bˇ ng chı sˆ 0. Nˆu -a ´ ` ´o ´ ´u ´’ ’´ ´ a ¯˙ ˙o a¯o ¯ a a ıt a o a e c´c d ınh d u.o.c d ´nh dˆ u bˇ ng chı sˆ m lˆp th`nh mˆt tˆp ho.p P (m) d a biˆt, th` ta d anh a` ´a ’´ ´ a ¯˙ ’ ¯ . ¯a ˙o a a oa ¯˜ e ı ¯´ . .. . .p: ´ ’´ ˙o . ¯˙’ ˙a ’. dˆ u chı sˆ (m + 1) cho moi d ınh cua tˆp ho a . .a d u.o.c d anh dˆ u | tˆn tai v ∈ P (m) v´.i (v , v ) ∈ E }. ´ `.i P (m + 1) := {vj chu ¯ . ¯´ a o o ij 75
Thuˆt to´n d`.ng khi khˆng thˆ’ d ´nh dˆ u d u.o.c n˜.a. C´ hai tru.`.ng ho.p xay ra: ˙ ´ ˙ ’ a au o e ¯a a ¯. u o o . . 1. Dınh t d u.o.c d anh dˆ u, chˇng han t ∈ P (m) v´.i m n`o d ´, th` ta x´t c´c d ınh v1 , v2 , ..., -˙ ˙ ’ ´ ’ e a ¯˙ ’ ¯ . ¯´ a a o a ¯o ı . sao cho v1 ∈ P (m − 1), v2 ∈ P (m − 2), . . . , vm ∈ P (0). , ..., v , t} l` d u.`.ng d i phai t` ˙ ım. ’ Khi d o µ := {s = v , v ¯´ a¯ o ¯ m m−1 1 2. Dınh t khˆng d u.o.c d anh dˆ u. Trong tru.`.ng ho.p n`y, ta kˆt luˆn khˆng tˆn tai d u.`.ng -˙ ´ ´a ` .¯o ’ o ¯ . ¯´ a o a e o o . . . s dˆn t. ´ d i t` ¯e ¯u Theo c´ch xˆy du.ng cua thuˆt to´n, dˆ d`ng ch´.ng minh rˇ ng ˜a ` ˙ ’ a a a a e u a . . Mˆnh d` 3.1.1 Nˆu d` thi d u.o.c x´c d. nh bo.i d˜y liˆn tiˆp c´c d ı’nh, th` thuˆt to´n c´ ´o ´ ˙ae ’ e a ¯˙ e ¯ˆ e e ¯ˆ . ¯ . a ¯i ı a ao . . .i gian O(m). th` o -ˆ . e D` thi liˆn thˆng manh 3.1.2 o o . Nhˇc lai l` d` thi c´ hu.´.ng G goi l` liˆn thˆng manh nˆu hai d ınh s v` t t`y y cua G luˆn ´ ´ ¯˙’ a u´˙ ’ a . a ¯o . o o ˆ .ae o e o . .`.ng d i t`. s dˆn t. Hiˆ’n nhiˆn rˇ ng ˙ e` o`. ´ luˆn tˆn tai mˆt d u o o o¯ ¯ u ¯e e a . Dinh l´ 3.1.2 Cho G = (V, E ) l` d` thi c´ hu.´.ng, v` v ∈ V. Khi d ´ G liˆn thˆng manh -. y a ¯ˆ . o o o a ¯o e o . ´u v` chı’ nˆu moi cˇp d ı’nh a, b ∈ V, tˆn tai mˆt d u.`.ng d i t`. a dˆn v v` mˆt d u.`.ng d i t`. ´ `. ´ ˙e ˙ nˆ a e . a¯ o o ¯ o ¯ u ¯e a o¯o ¯ u . . . ´ v dˆn b. ¯e Du.a trˆn thuˆt to´n t` kiˆm theo chiˆu sˆu, ta c´ thˆ’ mˆ ta c´ch x´c d inh mˆt d` ˙ ´ `a o e o˙a ’ e a a ım e e a ¯. o ¯ˆ .o . . .´.ng c´ liˆn thˆng manh hay khˆng thˆng qua d inh l´ sau: thi c´ hu o .o oe o o o ¯. y . Dinh l´ 3.1.3 Cho G = (V, E ) l` d` thi c´ hu.´.ng, v` v ∈ V. K´ hiˆu G := (V, E ) l` d` -. y a ¯ˆ . o o o a ye a ¯ˆ o . thi c´ hu.´.ng nhˆn d u.o.c t`. G bˇ ng c´ch d a o hu.´.ng mˆ i cung trong E. Khi d ´ G l` liˆn ` ˜ a ¯˙ ’ o o a ¯. u a o o ¯o ae . . thˆng manh nˆu v` chı’ nˆu thuˆt to´n t` kiˆm theo chiˆu sˆu trˆn d` thi c´ hu.´.ng G, ´ ´ ´ `a e a ˙e o a a ım e e e ¯ˆ . o o o . . .i d` u t`. v, d at d u.o.c moi d ı’nh cu a G v` thuˆt to´n t` kiˆm theo chiˆu sˆu trˆn d` thi ´ `a ˙a ’ . ¯˙ ˙ ’ kho ¯ˆ u ¯. ¯ . a a a ım e e e ¯ˆ . o . c´ hu.´.ng G , kho.i d` u t`. v, d at d u.o.c moi d ı’nh cu a G . ˙ ¯ˆ u ’a ¯˙ ˙ ’ oo ¯. ¯ . . Dinh ngh˜ 3.1.4 D` thi vˆ hu.´.ng G goi l` d u.o.c d. nh hu.´.ng manh nˆu c´ thˆ’ d .nh hu.´.ng -. -ˆ . o o ˙ ´ ıa o . a ¯ . ¯i o e o e ¯i o . .´.ng tu.o.ng u.ng nhˆn d u.o.c l` liˆn thˆng manh. trˆn c´c canh cua G sao cho d` thi c´ hu o ˙ ’ ea. ¯o . o ˆ ´ a¯. ae o . . 76
Dinh l´ sau cho ch´ng ta mˆt d ˇc tru.ng cua d` thi vˆ hu.´.ng d u.o.c d inh hu.´.ng manh. -. ˙ ¯ˆ . o o ’o y u o ¯a ¯ . ¯. o .. . Ta n´i cˆu trong d` thi vˆ hu.´.ng liˆn thˆng l` mˆt canh m` bo d i th` d` thi s˜ mˆ t t´ o` ´ a ˙¯ ’ a ¯o . o o ˆ e o ao. ı ¯o . e a ınh ˆ . liˆn thˆng. e o Dinh l´ 3.1.5 D` thi vˆ hu.´.ng G d u.o.c d. nh hu.´.ng manh nˆu v` chı’ nˆu n´ liˆn thˆng -. -ˆ . o ´ ´ e a ˙e oe y o o ¯ . ¯i o o . o` v` khˆng c´ cˆu. ao a Ch´.ng minh. B`i tˆp. u aa . Du.a trˆn thuˆt to´n t` kiˆm theo chiˆu sˆu, ta c´ thˆ’ d .nh hu.´.ng c´c canh cua d` ˙ ´ `a ˙ ¯o ’ˆ e a a ım e e o e ¯i o a. . . .´.ng d u.o.c d inh hu.´.ng manh nhu. sau. Lˆ y mˆt d ınh bˆ t k` trong d` thi vˆ hu.´.ng ´ ´y o ¯˙ .’ thi vˆ hu o .o ¯ . ¯. o a a ¯ˆ . o o o . G l`m d ınh kho.i d` u v` thu.c hiˆn thuˆt to´n t` kiˆm theo chiˆu sˆu. V` d` thi vˆ hu.´.ng ´ `a a ¯˙ ’ ˙ ¯ˆ a . ’a e a a ım e e ı ¯o . o o ˆ . . ´ ´ l` liˆn thˆng, kˆt qua cua viˆc t` kiˆm n`y cho ta mˆt cˆy bao tr`m1 T = (Vn , En ), trong ˙˙ ’’ ae o e e ım e a oa u . . ´ ˙nh cua G. Nˆu e = (vi , vj ) l` mˆt canh trong cˆy bao tr`m ’ ˙ ’ d o Vn = {v1 , v2 , . . . , vn } l` c´c d ı ¯´ aa¯ e ao. a u . T, ta d .nh hu.´.ng n´ t`. d ınh c´ chı sˆ nho ho.n dˆn d ınh c´ chı sˆ l´.n ho.n. T´.c l` nˆu ’´ ´’ ’´ ´ o u ¯˙ ’ o ˙o ˙ ’ ¯e ¯˙ o ˙oo ¯i o uae .´.ng canh e t`. v dˆn v , v` nˆu j < i th` d inh hu.´.ng canh e t`. v dˆn v . ´ ´ ´ i < j, d .nh hu o ¯i u i ¯e j a e ı ¯. o u j ¯e i . . Nˆu canh e = (vi , vj ) cua G khˆng thuˆc cˆy T, th` ta d inh hu.´.ng canh n`y t`. d ınh c´ chı ´ ˙ ’ a u ¯˙ ’ o˙ ’ e. o oa ı ¯. o . . .n ho.n dˆn d ınh c´ chı sˆ nho ho.n. T´.c l` nˆu i > j, d inh hu.´.ng canh e t`. v dˆn v , ´ ´’ ’´ ˙ ´ ´ ¯e ¯˙ o ˙o ’ sˆ l´ oo uae ¯. o u i ¯e j . ´u j > i th` d .nh hu.´.ng canh e t`. vj dˆn vi . ´ v` nˆ ae ı ¯i o u ¯e . H` 3.1 minh hoa d` thi vˆ hu.´.ng v` c´ch d .nh hu.´.ng n´. ınh . ¯ˆ . o o o a a ¯i o o a a • • ...... ...... . . ..... ..... .... . ..... .... . ..... .... . ..... .... . ..... . . .... .... .... .... . . . .... . .... . .. . .. . .. . .. .... .... ... ... . . .... .... .... .... . . ... ... . . . .... ... ... . .... .... .... . . ... ... . . .. ... . . . .... ..... ... ... .... . . ... ... . . .. . . . ...... . .. .... ... .... . . . ... .... .... .... . . .... .... .... ... ... . . ... ... . .. .. ... .. . . .... .... . . .... .... ... . . ... c c ... . . ... .. .. . . .... .... . . .... .... ... ... . . ... ... . . .. .. . . ... .... .... . . ... .... .... ... . . .. . . .. .. ... . . ................................................................................ ................................................................................ b• • •d b• • •d ... . . .. ................................................................................. .... .................................................................................. . . . . . . ... . . ..... . ...... . . ... . .... . . . .. .. .. . . . .. ..... ........ . ... . . ... . ... . .. . .. .. .. . . .. . .. . . .... .. .. ... ... .... . .... . . . ... ... .... .... .... .... . . .... .... . . .. .. . . . . ... ... .... . .... .... .... ... ... . . . .... .... .... .... . . . . . . . . .... .... .. ... ... . .... .... . . ... ... .... .... .... . . . .... . . . . .... .... . .... .... ....... ... . .. .... .... ....... . . . .... ....... ... .... . .... ....... . . . . ... . . . . .. . . . ... .. ... . ..... .... ... . . . . ... ... . ... ... . ........... . .. ....... . . . .... ....... .... ....... . .. . .. . . ... ... . . . . .... .... ... ... .... .. .. .... ... ... . . .... . . .... .... .... ... .... .. . . .... . ... .. . . . .... ... . .... .... . . . .... .... ... .... ....... . ... .... . . . . .... . . .... . ... . . . .... .. .... .... .... . ... .. .... . ..... .. . .... . .... . ..... .... . . ....... . . . .... . ... . ....... .. . . .... . ...... ... . ... . . . . . ..... . .. . .. .......................................................... . ... • • • • ......................................................... .. . . . .. .. .. .......................................................... .......................................................... ... .. . . . .. .. e e f f (a) (b) H` 3.1: (a) D` thi vˆ hu.´.ng G. (b) D` thi G d u.o.c d .nh hu.´.ng. -ˆ . o o -ˆ . ınh o o ¯ . ¯i o Kh´i niˆm n`y s˜ d u.o.c tr` b`y trong ??. 1 ae a e¯ . ınh a . 77
Du.`.ng d ngˇn nhˆ t gi˜.a hai d ˙nh -o ´ ´ ’ 3.2 ¯i a a u ¯ı Cho d` thi c´ hu.´.ng G = (V, E ) m` c´c cung cua n´ d u.o.c g´n c´c trong lu.o.ng cho bo.i ma ˙ o¯ . a a ’ ˙ ’ ¯o . o o ˆ aa . . .`.ng d i µ t`. mˆt d ınh ´ u o ¯˙ .’ trˆn vuˆng cˆ p n : W = (wij = (w(vi , vj )). B`i to´n d ˇt ra l` t` d u o a o a a a ¯a a ım ¯ ¯ . . ´t ph´t s ∈ V dˆn mˆt d ınh cuˆi l` t ∈ V sao cho tˆ’ng c´c trong lu.o.ng trˆn d u.`.ng d i µ : ˙ ´ ´a ˙ ’ xuˆa a ¯e o¯ o o a e ¯o ¯ . . . w(ek ) ek ∈µ ´ ˙ ’a l` nho nhˆ t. a C´c phˆn tu. wij , i, j = 1, ..., n, cua ma trˆn trong lu.o.ng c´ thˆ’ du.o.ng, ˆm hoˇc bˇ ng ˙ a` ` a˙ ’ ˙ ’ a a oe a .a . . . .´.ng G khˆng ch´.a c´c mach µ v´.i khˆng. Mˆt d iˆu kiˆn duy nhˆ t d at ra l` d` thi c´ hu o o ¯` ´. o e e a ¯ˇ a ¯ˆ . o o o ua o . . . ˙ng trong lu.o.ng trˆn mach µ ˆm. V` rˇ ng, nˆu c´ mˆt mach µ nhu. vˆy v` v l` mˆt d ınh ’ ` ´oo ˙ ’ tˆ o e a ıa e a a a o¯ . . . . . . . n`o d ´ cua n´, th` xuˆ t ph´t t`. n´t s ta d i dˆn d ınh v, v` sau d o d i v`ng quanh mach µ ´ ´’ a ¯o ˙ o ’ ¯ ¯e ¯˙ ıa auu a ¯´ ¯ o . mˆt sˆ d u l´.n lˆn rˆi m´.i dˆn t ta s˜ thu d u.o.c mˆt d u.`.ng d i c´ trong lu.o.ng d u nho. V` o o ¯˙ o ` ` .´’ ´ ¯˙’ ˙’ a o o ¯e e ¯. o ¯o ¯o. ı . . vˆy, trong tru.`.ng ho.p n`y, d u.`.ng d i ngˇn nhˆ t l` khˆng tˆn tai. ´ ´ `. a o a ¯o ¯ a aa o o . . Nhˆn x´t rˇ ng, nˆu ma trˆn trong lu.o.ng W thoa m˜n ae` ´ ˙a ’ a e a . . . . ´ 1 nˆu (vi , vj ) ∈ E, e wij := nˆu ngu.o.c lai, ´ 0 e .. th` d u.`.ng d i ngˇn nhˆ t t`. s dˆn t d u.o.c x´c d .nh bˇ ng thuˆt to´n t` kiˆm theo chiˆu rˆng ´ ` ´ ´ ¯ . a ¯i ´ `o ı¯ o ¯ a a u ¯e a a a ım e e. . . d ˜ tr` b`y trong phˆn tru.´.c. ` nhu ¯a ınh a a o Tru.´.c tiˆn ch´ng ta x´t thuˆt to´n Dijkstra, d o.n gian v` rˆ t hiˆu qua, dˆ’ giai b`i to´n ’˙’ ´e ˙ aa ’ ˙ ¯e ˙ a a oe u e a a ¯ . . .`.ng ho.p ma trˆn trong lu.o.ng W c´ c´c phˆn tu. khˆng ˆm. Sau d ´ ph´t `a˙ ’ d at ra trong tru o ¯ˇ a oa oa ¯o a . . . . . .`.ng ho.p tˆ’ng qu´t. triˆ’n n´ dˆ’ giai quyˆt b`i to´n trong tru o ˙ ˙’ ˙ ´ e o ¯e ˙ eaa .o a Tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm 3.2.1 o a o a . . . . Thuˆt to´n Dijkstra [20] t` d u.`.ng d i ngˇn nhˆ t t`. d ınh s dˆn d ınh t trong d` thi c´ hu.´.ng ´ ´ ´’ a u ¯˙ ’ ¯e ¯ ˙ a a ım ¯ o ¯ a ¯o . o o ˆ . .o.ng khˆng ˆm. Phu.o.ng ph´p n`y du.a trˆn viˆc g´n c´c nh˜n tam th`.i cho c´c c´ trong lu . o. oa aa e eaa a. o a . . d ınh: Nh˜n cua d ınh vi , k´ hiˆu L(vi ), l` mˆt cˆn trˆn cua d ˆ d`i d u.`.ng d i t`. s dˆn vi . ´ ¯˙’ ˙ ¯˙ ’ ’ ˙ ¯o a ¯ o ’ a ye aoa e ¯ u ¯e . .. . C´c nh˜n n`y sau d ´ tiˆp tuc d u.o.c giam b´.t bo.i mˆt thu tuc lˇp v` tai mˆ i bu.´.c lˇp c´ ˜ ´ ˙ ’ ˙ ’ ˙. a a. ’ a aa ¯o e . ¯ . o o o oao . . . .i tro. th`nh nh˜n cˆ d inh. Khi d ınh v d u.o.c g´n nh˜n cˆ d inh th` ´ ´ ˙a ’ ¯˙ ’ d ung mˆt nh˜n tam th` ¯´ o a. o a o ¯. ¯. a a o ¯. ı . i ˙ giam L(vi ); sˆ n`y ch´ l` d ˆ d`i d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi . ’˙ ´ ´ ´ ´ khˆng thˆ ’ o e oa ınh a ¯o a ¯ o ¯ a a u ¯e . 78
Thuˆt to´n Dijkstra (wij ≥ 0) a a . 1. [Kho.i tao] Dˇt ˙ . -a ’ . ´ 0 nˆu vi = s, e L(vi ) := nˆu ngu.o.c lai. ´ +∞ e .. v´.i moi vi ∈ V. D´nh dˆ u d ınh s c´ nh˜n cˆ d .nh, c´c d ınh kh´c c´ nh˜n tam th`.i. -a ´’ ´ a ¯˙ a ¯˙ ’ o o a o ¯i aoa. o . - ˇt c = s. Da. 2. [Cˆp nhˆt] V´.i moi vi ∈ Γ(c) sao cho vi c´ nh˜n tam th`.i d at a a o oa. o ¯ˇ . . . . L(vi ) := min{L(vi ), L(c) + w(c, vi )}; 3. T` d ınh vi∗ c´ nh˜n tam th`.i sao cho ım ¯˙ ’ oa. o L(vi∗ ) := min{L(vi ) < +∞ | vi c´ nh˜n tam th`.i}. oa. o -a ´’ ´ a ¯˙ 4. D´nh dˆ u d ınh vi∗ c´ nh˜n cˆ d .nh v` d ˇt c := vi∗ . o a o ¯i a ¯a. 5. (a) (Nˆu t` d u.`.ng d i t`. s dˆn t) Nˆu vi = t th` thuˆt to´n d`.ng, L(t) l` d u.`.ng d i ´ ´ ´ e ım ¯ o ¯ u ¯e e ı a au a¯ o ¯ . . s dˆn t; ngu.o.c lai, chuyˆ’n sang Bu.´.c 2. ˙ ´ ´ ´ ngˇn nhˆ t t` ¯e a au e o .. (b) (Nˆu t` tˆ t ca c´c d u.`.ng d i xuˆ t ph´t t`. s) Nˆu khˆng thˆ’ g´n nh˜n cˆ d .nh ˙ ´ ´’ ´ ´ ´ e ım a ˙ a ¯ o ¯ a au e o ea a o ¯i .´.c 4 th` thuˆt to´n d`.ng; gi´ tri L(v ) cua d ınh v c´ nh˜n cˆ ´ ˙nh vi∗ trong Bu o ’ ˙ ¯˙ ’ ’ cho d ı ¯ ı a au a. io ao . i .`.ng d i ngˇn nhˆ t t`. s dˆn v . Ngu.o.c lai chuyˆ’n sang Bu.´.c 2. ˙ ´ ´ ´ d .nh cho ta d ˆ d`i d u o ¯i ¯o a ¯ ¯ a a u ¯e i e o . .. Dinh l´ 3.2.1 Thuˆt to´n Dijkstra cho ta d u.`.ng d i ngˇn nhˆ t t`. s dˆn t (nˆu c´). -. ´ ´ ´ ´ y a a ¯o ¯ a a u ¯e eo . Ch´.ng minh. Tru.´.c hˆt ch´ y rˇ ng c´c d ınh khˆng d u.o.c g´n nh˜n cˆ d .nh s˜ khˆng tˆn u´ ` ´ ´ ` a ¯˙’ u oe a o ¯. a a o ¯i eo o .`.ng d i t`. s dˆn n´ (nh˜.ng d ınh n`y c´ nh˜n L bˇ ng ∞). ` ´ ¯˙ ’ tai d u o ¯ ¯ u ¯e o u aoa a . Gia su. L(vi ) cua c´c d ınh c´ nh˜n cˆ d .nh o. bu.´.c n`o d o l` d o d`i d u.`.ng d i ngˇn ´ ´ ˙˙ ’’ ˙ a ¯˙ ’ ’ ˙’ o a o ¯i o a ¯´ a ¯ˆ a ¯ o ¯ a . . s dˆn v . K´ hiˆu S l` tˆp tˆ t ca c´c d ınh n`y v` S l` tˆp c´c d ınh c´ nh˜n tam ´ ´ .´’ nhˆ t t` ¯e i y e 1 a a a ˙ a ¯˙ ’ a a 2 a a a ¯˙ ’ au oa. . . .i. Cuˆi Bu.´.c 2 cua mˆ i lˆn lˇp, nh˜n tam th`.i L(v ) l` d o d`i d u.`.ng d i ngˇn nhˆ t µ ˜a . ´ ´ o` a ´ ˙ ’ th`o o o a. o a ¯ˆ a ¯ o ¯ a ai . i . s dˆn v qua c´c d ınh trong tˆp S . (V` trong mˆ i lˆn lˇp chı c´ mˆt d ınh d u.o.c d u.a v`o ˜` a ´i ˙ ’ ˙ o o ¯˙ ¯ . ¯ ’ ’ t` ¯e u a¯ a1 ı oa . a . . S1 nˆn cˆp nhˆt lai L(vi ) chı xay ra trong Bu.´.c 2). ˙˙ ’’ ea a. o . . X´t d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi∗ khˆng ho`n to`n d i qua c´c d ınh cua S1 m` ´ ´ ´ a ¯˙ ’ ˙ ’ e ¯o ¯ a a u ¯e o a a¯ a .a ´ nhˆ t mˆt d ınh thuˆc S v` gia su. v ∈ S l` d ınh d` u tiˆn nhu. vˆy trˆn d u.`.ng d i ´ o ¯˙ ’ ˙˙j ’’ ˙ ’ ¯a ch´ ıt a u o 2a 2 a¯ ˆ e a e ¯o ¯ . . . n`y. Do wij khˆng ˆm, d oan d u.`.ng d i t`. vj dˆn vi∗ phai c´ d o d`i ∆ khˆng ˆm sao cho ´ ˙ o ¯ˆ a ’ a oa ¯. ¯o ¯u ¯e oa . L(vj ) < L(vi∗ ) − ∆ < L(vi∗ ). Tuy nhiˆn d iˆu n`y mˆu thuˆn v´.i khˇng d .nh rˇ ng L(vi∗ ) c´ ˜ ˙ ’ ` e ¯` ea a ao a ¯i a o .i nho nhˆ t, v` do d o c´c d ınh trˆn d u.`.ng d i ngˇn nhˆ t dˆn v ∗ thuˆc S v` ´ ´a ´´ ˙ ’a ¯´ a ¯˙ ’ nh˜n tam th` a. o e ¯o ¯ a a ¯e i o 1a . do d o L(vi∗ ) l` d ˆ d`i cua d u.`.ng d i n`y. a ¯o a ˙ ¯ o ’ ¯´ ¯a . 79
V` S1 kho.i tao l` {s} v` trong mˆ i bu.´.c lˇp, d ınh vi∗ d u.o.c thˆm v`o S1 , nˆn bˇ ng ˜ e` ˙.a ’ o a ¯˙ ’ ı a o ¯. e a a . .`.ng d i ngˇn nhˆ t t`. s dˆn v v´.i moi d ınh v ∈ S . Do d o thuˆt ´ ´ ´ ¯˙’ qui nap, L(vi ) l` d ˆ d`i d u o a ¯o a ¯ ¯ a a u ¯e i o ¯´ a . . . . i 1 .i giai tˆi u.u. ’´ ˙o to´n cho l` a o Mˆnh d` 3.2.2 Thuˆt to´n Dijkstra d `i ho i th`.i gian O(n2 ). Nˆu d` thi thu.a v` d u.o.c x´c ´o ¯o ˙ ’o e ¯ˆe aa e ¯ˆ . a¯ . a . . .i d˜y liˆn tiˆp c´c d ı’nh, th` th`.i gian cu.c d ai cu a thuˆt to´n l` O(m log n). ´ ˙ ’ e a ¯˙ ¯. ˙ ’ d. nh bo a e ¯i ıo a aa . . Ch´.ng minh. Trong tru.`.ng ho.p d` thi liˆn thˆng manh d` y d u n d ınh v` cˆn t` d u.`.ng d i a ` ım ¯ o ¯ ¯a ¯ ˙ ¯˙ ’ ’ u o . ¯ˆ . e o o ˆ a . ngˇn nhˆ t t`. s dˆn moi d ınh kh´c, thuˆt to´n cˆn n(n − 1)/2 ph´p cˆng v` so s´nh trong ´ ´ ´ a` ¯˙’ a a u ¯e a a a eo a a . . . .´.c 2 v` n(n − 1)/2 ph´p so s´nh kh´c trong Bu.´.c 3. Ngo`i ra, c´c Bu.´.c 2 v` 3 cˆn x´c a` Bu o a e a a o a a o aa ˙nh d u.o.c g´n nh˜n tam th`.i nˆn cˆn thˆm n(n − 1)/2 ph´p so s´nh. C´c sˆ n`y ` ´ ’ ¯. a d .nh c´c d ı ¯i a¯ a. oea e e a aoa .`.ng d i ngˇn nhˆ t t`. s dˆn t, v` c˜ng l` cˆn trˆn cho sˆ c´c ph´p to´n cˆn thiˆt dˆ’ t` d u o ´˙ ´ ´ a` ´ ´ u aa e oa e a e ¯e ım ¯ ¯ a a u ¯e a . .o.c khi t l` d ınh cuˆi c`ng d u.o.c g´n nh˜n cˆ d inh. ´ ´ a ¯˙ ’ thˆt vˆy, c´c gi´ tri n`y d at d u . aaa a . a ¯. ¯ o u ¯. a a o ¯. .. Khi Thuˆt to´n Dijkstra kˆt th´c, c´c d u.`.ng d i ngˇn nhˆ t d u.o.c x´c d .nh bˇ ng dˆ ´ ` ´ ´ a a e u a ¯o ¯ a a ¯ . a ¯i a ¯e . . .o.ng tr` (3.1) du.´.i d ay. Do d ´ nˆu v l` d ınh tru.´.c d ınh v trong d u.`.ng d i ´ ¯o e i a ¯ ˙ ’ o ¯˙ ’ qui theo Phu ınh o ¯ˆ ¯o ¯ i ngˇn nhˆ t t`. s dˆn vi th` v´.i moi d ınh vi cho tru.´.c, d ınh vi c´ thˆ’ lˆ y l` d ınh m` ˙´ ´ ´ ´ . ¯˙’ o ¯˙ ’ o e a a ¯˙ ’ a a u ¯e ıo a L(vi ) = L(vi ) + w(vi , vi ). (3.1) Nˆu tˆn tai duy nhˆ t d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi th` c´c cung (vi , vi ) trˆn d u.`.ng ´ e`. ´o ´ ´ ´ a ¯o ¯ a a u ¯e ıa e ¯o .´.ng (xem Chu.o.ng 4) v´.i gˆc l` d ınh s. Nˆu c´ nhiˆu ´ ´ ´ eo` ´ o o a ¯˙ ’ d i ngˇn nhˆ t tao th`nh mˆt cˆy c´ hu o ¯ a a. a oao e . .n mˆt d u.`.ng d i ngˇn nhˆ t t`. s dˆn bˆ t k` mˆt d ınh kh´c, th` Phu.o.ng tr` 3.1 s˜ d u.o.c ´ ´ ´´ a u ¯e a y o ¯˙ .’ ho o¯o ¯ a a ı ınh e¯ . . thoa m˜n bo.i ho.n mˆt d ınh kh´c vi v´.i vi n`o d o. ˙a ’ ˙ ’ o ¯˙ ’ a o a ¯´ . Thu tuc sau minh hoa thuˆt to´n Dijkstra. Trong thu tuc n`y, mang M ark [] d u.o.c su. ˙. ’ ˙. a ’ ˙ ’ ¯. ˙ ’ a a . . ˙ d anh dˆ u c´c d ınh c´ nh˜n tam th`.i hay cˆ d .nh: M ark [i] = FALSE nˆu d ınh vi ’ ¯´ ´ a ¯˙ ´ ¯i ´ ¯˙ ’ ’ dung dˆ ¯e a oa. o o e . c´ nh˜n tam th`.i; ngu.o.c lai bˇ ng TRUE. Gi´ tri Label[i] tu.o.ng u.ng nh˜n L( vi ) v` P red[i], ` oa. o a a. ´ a a .. .´.c d ınh v trong d u.`.ng d i ngˇn nhˆ t t`. s dˆn ´ ´ ` ´ ´ sau khi kˆt th´c thuˆt to´n, l` d ınh liˆn tru o ¯˙ a a ¯˙ ’ ’ e u a e ¯o ¯ a a u ¯e . i vi . Nˆu tˆn tai d u.`.ng d i ngˇn nhˆ t t`. s dˆn t, th` thu tuc PathTwoVertex() s˜ in ra thˆng ´ e ` . ¯o ´o ´ ´ ı ˙.’ ¯ a a u ¯e e o tin cua d u.`.ng d i n`y. ˙ ¯o ’ ¯a void Dijkstra(byte Start, byte Terminal) { byte i, Current; AdjPointer Tempt; Path Pred; int Label[MAXVERTICES], NewLabel, Min; Boolean Mark[MAXVERTICES]; 80
for(i = 1; i Next; while (Tempt != NULL) { if (Mark[Tempt->Vertex] == FALSE) { NewLabel = Label[Current] + Tempt->Length; if (NewLabel < Label[Tempt->Vertex]) { Label[Tempt->Vertex] = NewLabel; Pred[Tempt->Vertex] = Current; } } Tempt = Tempt->Next; } Min = +Infty; for (i = 1; i
return; } Mark[Current] = TRUE; } printf("Ton tai duong di tu %d", Start); printf(" den %d", Terminal); printf("\nDuong di qua cac dinh:"); printf("\n % d " , Start); PathTwoVertex(Pred, Start, Terminal); printf("\nDo dai la: %d ", Label[Terminal]); } Tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y 3.2.2 o a y´ . . . . Thuˆt to´n Dijkstra chı ´p dung trong tru.`.ng ho.p ma trˆn trong lu.o.ng W khˆng ˆm. Tuy ˙a ’ a a o a oa . . . . . . nhiˆn, nhiˆu b`i to´n thu.c tˆ, W l` ma trˆn chi ph´ cho nˆn nh˜.ng cung mang lai lo.i nhuˆn ` ´ e eaa e a a ı, e u a . . .. . .`.ng ho.p n`y, phu.o.ng ph´p cho du.´.i d ay t` d u.`.ng d i ngˇn ´ ˙o ’ phai c´ chi ph´ ˆm. Trong tru o ıa a a o ¯ˆ ım ¯ o ¯ a . nhˆ t t`. s dˆn tˆ t ca c´c d ınh kh´c. Dˆy c˜ng l` phu.o.ng ph´p lˇp v` du.a trˆn c´ch d ´nh a -a u ´ ´´’ a u ¯e a ˙ a ¯ ˙ ’ a aa a. e a ¯a . .´.c lˇp th´. k c´c nh˜n biˆ’u diˆn gi´ tri d o d`i cua c´c d u.`.ng d i ngˇn ˙ ˜ ´ ´ a . ¯ˆ a ˙ a ¯ o ¯ ’ nh˜n, trong d o cuˆi bu o a a ¯´ o u a a e e a . . ´t (t`. s dˆn tˆ t ca c´c d ınh kh´c) c´ sˆ cung khˆng vu.o.t qu´ (k + 1). Thuˆt to´n n`y ´ a ˙ a ¯˙ ´’ ´ ’ nhˆ a u ¯e a oo o a a aa . . d u.a ra lˆn d` u tiˆn bo.i Ford [26] v`o gi˜.a nˇm 1950. Sau d o d u.o.c Moore [45] v` Bellman ` ¯a ˙ ’ ¯ aˆ e a ua ¯´ ¯ . a [3] cai tiˆn nhu. sau. ’´ ˙e Thuˆt to´n Ford, Moore, Bellman a a . K´ hiˆu Lk (vi ) l` nh˜n cua d ınh vi o. cuˆi lˆn lˇp th´. (k + 1). ˙ o` a ´a . a a ˙ ¯˙’ ’ ’ ye u . 1. [Kho.i tao] Dˇt S = Γ(s), k = 1; v` ˙ . -a ’ a .  ´ 0 nˆu vi = s, e  1 ´ w(s, vi ) nˆu vi = s, vi ∈ Γ(s), e L (vi ) :=  nˆu ngu.o.c lai.  ´ +∞ e .. 2. [Cˆp nhˆt nh˜n] V´.i mˆi vi ∈ Γ(S ), vi = s, thay d o’i nh˜n cua n´ theo quy tˇc: ˙ ˜ ´ a˙o ’ a a a oo ¯ˆ a . . Lk+1 (vi ) := min[Lk (vi ), min {Lk (vj ) + w(vj , vi )}], (3.2) vj ∈Ti 82
trong d o Ti := Γ−1 (vi ) ∩ S. Tˆp S ch´.a tˆ t ca c´c d ınh vi sao cho d u.`.ng d i ngˇn nhˆ t ´ ´’ ´ u a ˙ a ¯˙ ’ ¯´ a ¯o ¯ a a . . s dˆn v c´ sˆ cung l` k. ´ ´ (hiˆn h`nh) t` ¯e i o o ea u a . Tˆp Ti ch´.a tˆ t ca c´c d ınh vj sao cho d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi c´ sˆ cung l` ´ ´’ ´ ´ ´ u a ˙ a ¯˙ ’ a ¯o ¯ a a u ¯e oo a . .c l` v ∈ S ) v` kˆt th´c bˇ ng cung (v , v ). Ch´ y rˇ ng, nˆu v ∈ Γ(S ) th` d u.`.ng ` u´ ` ´ ´ k (t´ a j u ae ua a ei ı¯ o ji ´n nhˆ t t`. s dˆn vi khˆng thˆ’ c´ sˆ cung l` (k + 1) v` ta khˆng thay d ˆ’i nh˜n ˙oo ˙ ´ u ¯e ´ ´ d i ngˇ ¯ a a o e a a o ¯o a ˙ ¯˙ ’’ cua d ınh n`y: a Lk+1 (vi ) := Lk (vi ), v´.i moi vi ∈ Γ(S ). o . 3. [Kiˆ’m tra kˆt th´c] (a) Nˆu k ≤ n − 1 v` Lk+1 (vi ) = Lk (vi ), v´.i moi vi ∈ V, th` thuˆt ˙ ´ ´ e e u e a o ı a . . to´n d`.ng; nh˜n cua d ınh vi cho ta d ˆ d`i d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi . ´ ´ ´ a ˙ ¯˙ ’ ’ au ¯o a ¯ o ¯ a a u ¯e . (b) Nˆu k < n − 1 v` L (v ) = L (v ), v´.i v n`o d o, th` chuyˆ’n sang Bu.´.c 4. ˙ ´ k+1 k e a o a ¯´ ı e o i i i (c) Nˆu k = n − 1 v` L (vi ) = L (vi ), v´.i vi n`o d o, th` d` thi G c´ mach v´.i d o ´ k+1 k e a o a ¯´ ı ¯o . ˆ o. o ¯ˆ . ´ d`i ˆm. Thuˆt to´n kˆt th´c. aa a ae u . -a 4. [Cˆp nhˆt S ] Dˇt a a . . . S := {vi | Lk+1 (vi ) = Lk (vi )}. (Tˆp S bˆy gi`. ch´.a tˆ t ca c´c d ınh m` d u.`.ng d i ngˇn nhˆ t t`. s dˆn n´ c´ sˆ cung ´ ´’ ´ ´ ´ o u a ˙ a ¯˙ ’ a a a¯ o ¯ a a u ¯e o o o . l` (k + 1)). a 5. Thay k bo.i (k + 1) v` lˇp lai Bu.´.c 2. ˙ ’ aa . o . Khi thuˆt to´n kˆt th´c v` d` thi khˆng c´ mach d ˆ d`i ˆm, ch´ng ta c´ thˆ’ t` tˆ t ˙ ´ ´ a ae u a ¯o . o ˆ o . ¯o a a u o e ım a . . .`.ng d i (nˆu tˆn tai) ngˇn nhˆ t t`. s dˆn tˆ t ca c´c d ınh kh´c. Ho.n n˜.a c´c d u.`.ng ´ ca c´c d u o ¯ e ` . ´o ´ ´´’ ˙a¯ ’ a u ¯e a ˙ a ¯˙ ’ a a u a ¯o d i c´ thˆ’ nhˆn d u.o.c tru.c tiˆp nˆu, trong ph´p cˆng v`o c´c nh˜n Lk (vi ) o. Phu.o.ng tr` ˙ ´´ ˙ ’ ¯ o e a ¯. ee eo aa a ınh . . . .u tr˜. thˆng tin mˆ i d ınh trong suˆt qu´ tr` t´ to´n, ˜’ ´ k o ¯˙ 3.2, ta thˆm mˆt nh˜n P (vi ) lu e o a uo o a ınh ınh a . ˙nh kˆ tru.´.c d ınh vi trˆn d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi o. bu.´.c lˇp ´ ` ´ u ¯e ´ k ’ ˙ ’ ˙ ’ trong d ´ P (vi ) l` d ı ¯o a¯ e o¯ e ¯o ¯ a a oa . . k. Ta c´ thˆ’ kho.i tao ˙˙.’ th´ u oe ´ s nˆu vi ∈ Γ(s), e P 1 (vi ) := nˆu ngu.o.c lai. ´ 0 e .. Nh˜n P k (vi ) d u.o.c cˆp nhˆt theo Phu.o.ng tr` 3.2 trong Bu.´.c 2 sao cho P k+1 (vi ) = P k (vi ) a ¯. a a ınh o . . nˆu gi´ tri nho nhˆ t d at d u.o.c o. phˆn tu. d` u tiˆn trong dˆ u ngoˇc cua Phu.o.ng tr` 3.2; ´ ´ ’` ´ ˙ ’ a ¯. ¯ . ˙ a ˙ ¯ˆ ’a a˙ ’ e a. e a ınh . .o.c lai. Nˆu k´ hiˆu P(v ) l` vector d u.o.c xˆy du.ng t`. c´c nh˜n ´ ´ k+1 hoˇc P (vi ) = vj nˆu ngu . . a e eye a ¯. a ua a . . . i P khi kˆt th´c thuˆt to´n, th` d u.`.ng d i ngˇn nhˆ t t`. s dˆn vi nhˆn d u.o.c theo th´. tu. ´ ´ ´ ´ e u a a ı¯o ¯ a a u ¯e a ¯. u. . . ngu.o.c: . s, . . . , P 3 (vi ), P 2 (vi ), P (vi ), vi , trong d o P 2 (vi ) c´ ngh˜ l` P (P (vi )), . . . . ¯´ o ıa a Doan chu.o.ng tr` sau minh hoa thuˆt to´n d ˜ tr` b`y. -. ınh a a ¯a ınh a . . 83
void Ford_Moore_Bellman(byte Start) { byte i, k, Terminal; AdjPointer Tempt1, Tempt2; Path OldPred, NewPred; int OldLabel[MAXVERTICES], NewLabel[MAXVERTICES], Min; Boolean Done, Mark[MAXVERTICES]; for (i = 1; i Next; while (Tempt1 != NULL) { Mark[Tempt1->Vertex] = TRUE; if (Tempt1->Vertex != Start) { OldPred[Tempt1->Vertex] = Start; OldLabel[Tempt1->Vertex] = Tempt1->Length; } Tempt1 = Tempt1->Next; } for (i = 1; i
while (Tempt1 != NULL) { NewPred[Tempt1->Vertex] = Tempt1->Vertex; Min = OldLabel[Tempt1->Vertex]; Tempt2 = V_in[Tempt1->Vertex]->Next; while (Tempt2 != NULL) { if (Mark[Tempt2->Vertex] == TRUE) { if ((OldLabel[Tempt2->Vertex] + Tempt2->Length) < Min) { NewPred[Tempt1->Vertex] = Tempt2->Vertex; Min = OldLabel[Tempt2->Vertex] + Tempt2->Length; } } Tempt2 = Tempt2->Next; } NewLabel[Tempt1->Vertex] = Min; Tempt1 = Tempt1->Next; } } } Done = TRUE; for (i = 1; i
printf("\n Duong di qua cac dinh:"); printf(" % d " , Start); PathTwoVertex(OldPred, Start, Terminal); i = Terminal; printf(" Do dai la: %d ", OldLabel[Terminal]); printf("\n "); getch(); } else { printf("\n "); printf("Khong ton tai duong di tu %d", Start); printf(" den %d", Terminal); } return; } for (i = 1; i