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

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

Thêm vào BST

Báo xấu

97
lượt xem 17
download

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

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 5 Bài toán Euler và bài toán Hamilton

Chủ đề:

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

Lưu

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

Chu.o.ng 5 B`i to´n Euler v` b`i to´n Hamilton a a aa a L´ thuyˆt d` thi ph´t triˆ’n bˇt nguˆn t`. nh˜.ng b`i to´n cˆ’ d iˆ’n, trong sˆ d o b`i to´n Euler ˙´ ˙˙ ´ˆ `uu ´ y e ¯o . a ea o a a o ¯e o ¯´ a a ˜ ˜’ o` a o ¯˙ ¯ ´ v` b`i to´n Hamilton t` h`nh tr` d i qua mˆ i canh d ung mˆt lˆn v` qua mˆi d ınh d ung aa a ım a ınh ¯ o. ¯´ .a .o.ng u.ng d ong vai tr` quan trong. o` mˆt lˆn tu .a ´ ¯´ o . Hai b`i to´n n`y c´ liˆn quan dˆn nh˜.ng u.ng dung: c´c b`i to´n t` h`nh tr` tˆt ´ ´ a a a oe ¯e u´ a a a ım a ınh o . .`.i d u.a thu. Trung Hoa, ngu.`.i ch`o h`ng), tu. d ˆng ho´ thiˆt kˆ bˇ ng m´y t´ e e` ´ ´ ´a nhˆ t (ngu o ¯ a o aa . ¯o a a ınh, . lˆp lich, vˆn vˆn. a. aa . Mˇc d` hai b`i to´n n`y d u.o.c ph´t biˆ’u rˆ t giˆng nhau, nhu.ng m´.c d o kh´ trong ˙´o ´ au a a a ¯. a ea u ¯ˆ o . . ´ ´ ˙ ’ viˆc giai quyˆt ch´ng l` rˆ t kh´c nhau. e e u aa a . Ch´ng ta s˜ ch´.ng minh rˇ ng trong d` thi vˆ hu.´.ng, tˆn tai thuˆt to´n d a th´.c t` ` `. u eu a ¯ˆ . o o o o a a¯ u ım . .`.i d u.a thu. Trung Hoa c´ thˆ’ d u.a vˆ t` cˇp gh´p ho`n ˙ ` ım a h`nh tr` Euler v` b`i to´n ngu o ¯ a ınh aa a o e¯ e e a . .o.ng nho nhˆ t [30] (c˜ng xem Phˆn 7.5). C´c thuˆt to´n n`y s˜ d u.o.c tr` ´ ` ˙o. ’ ˙ ’a hao c´ trong lu . u a a a a a e¯ . ınh . ` b`y trong c´c Phˆn 5.1 v` 5.2. a a a a Mˇt kh´c, vˆ n d` tˆn tai chu tr` hay mach Hamilton l` nh˜.ng b`i to´n khˆng d a a ¯ˆ ` . ´ eo a a ınh au a a o¯ . . .c khˆng d u.o.c d` cˆp o. d ˆy. Ban d oc quan tˆm c´ thˆ’ xem, chˇng han [30]. Ch´ng ta ˙ ˙ ’ ˙ ¯a ’ th´ u o ¯ . ¯ˆ a e. . ¯. a oe a u . chı tr` b`y trong Phˆn 5.3 nh˜.ng kˆt qua ch´ liˆn quan dˆn su. tˆn tai cua c´c chu tr` ` ´ ¯e . ` . ˙ a ´ ˙ ınh a ’ ˙ ınh e ’ ’ a u e o ınh .ng minh c´ t´ kiˆn thiˆt thuˆt to´n hoˇc o ¯` ´ ´ hay mach Hamilton. Khi c´ d iˆu kiˆn, c´c ch´ e e a u o ınh e e a a a . . . . c´ thˆ’ d` xuˆ t nh˜.ng phu.o.ng ph´p heuristic. ˙e ´ o e ¯ˆ a u a 5.1 B`i to´n Euler a a Dinh ngh˜ 5.1.1 Gia su. G = (V, E ) l` d` thi vˆ hu.´.ng (d o.n hoˇc d a d` thi). Dˆy chuyˆn -. ` ˙˙ ’’ ıa a ¯o . o o ˆ ¯ a ¯ ¯ˆ .o a e . http://www.ebook.edu.vn 127
Euler l` dˆy chuyˆn ch´.a tˆ t ca c´c canh cua d` thi, mˆi canh d ung mˆt lˆn. Chu tr` ˜ ` ´’ o` u a ˙a . ˙ ¯o . o . ’ˆ aa e ¯´ .a ınh .i d ınh cuˆi. Euler l` dˆy chuyˆn Euler m` d ınh d` u tr`ng v´ ¯˙ ` ´ a ¯˙ ¯ˆ ’ o’ aa e a u o V´ du 5.1.2 (B`i to´n Euler) C´ch d ˆy khoang ba trˇm nˇm, nhiˆu ngu.`.i dˆn th`nh phˆ ` ´ ˙’ ı. aa a ¯a a a e oa a o .´.c Nga (sau n`y l` th`nh phˆ Kaliningrat) d a t`.ng thˇc mˇc vˆ n d` nhu. ´ ´´e ´ ˙ ’ K¨nigsberg cua nu o o aaa o ¯˜ u a a a ¯ˆ ´ c´ sˆng Pregel chay qua, gi˜.a sˆng c´ c` lao Kneiphof, v` c´ 7 chiˆc cˆu e` ´a ˙ ’ sau: Th`nh phˆ o o a o uo ou ao . trˆn H` 5.1(a); c´ thˆ’ d i dao qua khˇp c´c cˆu nhu.ng mˆ i cˆu chı d i ˙ ´ ´ ˜a aa` o` ˙¯ ’ bˇc qua sˆng nhu e a o ınh o e¯ . a .c a, b, c, d cua th`nh phˆ nhu. mˆt d ınh, mˆi cˆu ˜ ˜a o` ´ ´ o` ˙ ’ o ¯˙ .’ mˆt lˆn thˆi khˆng? Nˆu ta coi mˆ i khu vu .a o o e o a o . .c nhu. mˆt canh nˆi hai d ınh, th` ban d` th`nh phˆ K¨nigsberg l` mˆt ´ ´o ˙ ’ ˙ ¯ˆ a ’ qua lai hai khu vu o. o ¯ ı o o ao . . . . d` thi (H` 5.1(b)). Thˇc mˇc cua ngu.`.i dˆn th`nh phˆ ch´ l`: c´ thˆ’ v˜ d u.o.c d` thi ˙ ´ ´’ ´ a˙ ¯o . ınh ˆ a oa a o ınh a o e e ¯ . ¯ˆ . o ` oeu` a`. bˇ ng mˆt n´t b´t liˆn hay khˆng? N´i c´ch kh´c: tˆn tai chu tr` Euler? a e o oa o ınh . Nh` to´n hoc L. Euler (1707-1783) l` ngu.`.i d` u tiˆn d ˜ ch´.ng minh b`i to´n khˆng aa a o ¯aˆ e ¯a u aa o . .i giai (nˇm 1736, xem [22], [23]), v` v` vˆy b`i to´n thu.`.ng d u.o.c goi l` b`i to´n Euler ˙ ’ c´ l` oo a aıa a a o ¯. .aa a . ` c´c cˆu o. K¨nigsberg. `˙o ’ vˆ a a e a . ... ..... ... ... . . . .. .. . ... a . . .... . . ..... . .. ... .. . ... .. .. ... .. ... . ... .. . ... ....... .... ....... ..... . . ........ ... . . ........ ........ ......... . . ... .. ...... . .. ....... . ... ....................... .. ............ . ............................................................... . . ... . ................................................. .. . . ... .. .. . . .. .. . ... . .. . . ... . .. .. .. . . ... .. .. .. . . .. .. ... .. . . .. .. . .. . ... .. .. . .. . ... .. . .. . .. ... ... .. .. .. .. . .. .. .. ... .. .. .. .. ... .. .. .. .. ... .. .. .. .. ......................... ... .................... .. ... .. .. .. ... ..... ... ... ..... .. ............................ .. ... ............................... .... .. . ... .. .... ..... . . ... .... .. . ... ... ... ... ... ... .. . .. ... .. . .. .. . .. .. . .. ... .. . . ........................................... c c . . ...................... b b . ... . . ..................... ......................................... ..................... . . . . ... . . ....................... . . ... . ... . . .. . . .. .. . . . .. .. .. ... ... . .. . ... ... ... .. ... ... .. .... .. ................................ .. . ................................. . .... ... .. .... .... ... .. .... . .. .. ....... ......................... .. ................. .. .. .. .. . .. .. .. ... ... .. .. .. .. .. .. .. ... . .. .. ... .. .. .. .. .. . .. .. . ... .. ... . .. . .. .. .. . .. . .. ... . .. ... .. .. . . .. .. . .. .. . .. . .. .. . . .. .. .. . .. . .. . .. ........................................... .. .............................................. .. ... ... . .. . . ......................... ........ . . . ... ................. ........... . .. ... . . ... ....... ... . . . . .. . . ........ ........ ........ ... ........ . ... . . ...... . ..... ..... .... . ... . ... . .. .. .. .. .. .. .. ... ... .. .. .. . .... .. d .. . .... .. . .... .. . .... .. .... ... . .. d (a) (b) H` 5.1: (a) Ban d` cua th`nh phˆ K¨nigsberg. (b) D` thi tu.o.ng d u.o.ng. -ˆ . ´ ˙ ¯ˆ ˙ ’ o’ ınh a oo o ¯ Dinh l´ 5.1.3 [Euler] Da d` thi vˆ hu.´.ng liˆn thˆng G = (V, E ) c´ dˆy chuyˆn Euler nˆu -. - ¯ˆ . o o ` ´ y o e o oa e e a˙` ´´ v` chı’ nˆu sˆ c´c d ı’nh bˆc le bˇ ng 0 hoˇc 2. a ˙ e o a ¯˙ . ’a a . Ch´.ng minh. Tru.´.c hˆt ch´ y rˇ ng d` thi khˆng liˆn thˆng khˆng thˆ’ ch´.a dˆy chuyˆn ˙ u´ ` ´ ` u oe a ¯o . o ˆ e o o eua e hoˇc chu tr` Euler. a ınh . Bˆy gi`. ta ch´.ng minh d iˆu kiˆn cˆn. Nˆu µ l` dˆy chuyˆn Euler, th` chı c´ hai d ınh ¯` e` ´ ` ı ˙o’ ¯˙’ a o u e .a e aa e d` u v` cuˆi c´ bˆc le. Nˆu ngo`i ra, hai d ınh n`y tr`ng nhau (chu tr` Euler) th` khˆng ´ ´ ¯a a o o a ˙ ’ ¯˙’ ˆ e a a u ınh ıo . o ¯˙’ a˙ ’ c´ d ınh bˆc le. . http://www.ebook.edu.vn 128
Kˆ tiˆp ta ch´.ng minh d iˆu kiˆn d u bˇ ng quy nap theo sˆ canh m cua G. Hiˆ’n nhiˆn ˙ e ¯˙ ` ´´ ¯` ´ ’a ˙ ’ ee u e o. e e . . . d inh l´ d ung cho moi d` thi liˆn thˆng m canh. Nˆu G c´ ´ ´ ˙˙ ’’ d .nh l´ d ung nˆu m = 1. Gia su ¯. ¯i y ¯´ e y ¯´ ¯o . e ˆ o e o . . . c´c d ınh n`y l` a v` b (nˆu tˆ t ca c´c d ınh cua G c´ bˆc chˇn, chon ˜ ´´’ hai d ınh bˆc le, gia su a ¯˙ ¯˙’ a˙ .’ ˙˙ ’’ ’ e a ˙ a ¯˙ ’ ˙ ’ aa a oa a . . ˙nh a bˆ t k` v` lˆ y b = a). K´ hiˆu µ l` dˆy chuyˆn m` ta d i trˆn d` thi G xuˆ t ph´t t`. a ´ y aa ´ ` ´ ’ dı ¯ a ye aa e a ¯ e ¯o . ˆ a au . theo hu.´.ng tu` y, d i qua mˆ i canh d ung mˆt lˆn. Nˆu tai th`.i d iˆ’m n`o d ´ ta o. d ınh x = b ˙ ˜ o` ´ ˙ ¯˙ ’’ o y´ ¯ o. ¯´ .a e. o ¯e a ¯o . dung mˆt sˆ le canh liˆn thuˆc v´.i x nˆn c´ thˆ’ d i theo canh kh´c chu.a ˙¯ . ´’ ¯˜ ˙ ’ o o˙ . ngh˜ l` ta d a su . ıa a e oo eoe a . . d u.o.c su. dung. Nˆu ta khˆng thˆ’ d i d u.o.c n˜.a, ngh˜ l` d ang o. d ınh b. Nˆu tˆ t ca c´c canh ˙ ´ ´´’ ¯. ˙ . ’ ˙ ¯˙ ’’ e a ˙a . e o e¯ ¯ . u ıa a ¯ d a d u.o.c su. dung, µ l` mˆt dˆy chuyˆn Euler v` d .nh l´ d ung. Trong tru.`.ng ho.p ngu.o.c ` ˙. ’ ¯˜ ¯ . aoa e a ¯i y ¯´ o . . . ` thi con G d u.o.c x´c d .nh bo.i c´c canh chu.a d u.o.c su. dung chı c´ nh˜.ng d ınh bˆc ˙a. ’ ˙. ’ ˙o u ’ ¯˙ ’ lai, d o . . ¯ˆ ¯ . a ¯i ¯. a . chˇn. K´ hiˆu G1 , G2 , . . . , Gp l` c´c th`nh phˆn liˆn thˆng cua G ch´.a ´ nhˆ t mˆt canh. ˜ ` ´o. ˙ ’ a ye aa a ae o u ıt a . . Khi d ´ c´c d` thi Gi c´ sˆ canh ´ ho.n m v` do d ´ theo gia thiˆt quy nap, ch´ng ch´.a mˆt ´ ´ ˙ ’ ¯o a ¯ˆ . o oo. ıt a ¯o e u u o . . chu tr` Euler µi . V` G liˆn thˆng, dˆy chuyˆn µ c´ chung v´.i c´c d` thi G1 , G2 , . . . , Gp c´c ` ınh ı e o a e o o a ¯o . ˆ a d ınh theo th´. tu. i1 , i2 , . . . , ip . Khi d o h`nh tr` ınh: xuˆ t ph´t t`. a d i trˆn µ dˆn d ınh i1 , d i ´ ´’ ¯˙’ ¯e ¯˙ u. ¯´ a a au¯e ¯ . i vˆ i , d i trˆn µ dˆn d ınh i d i doc theo chu tr` µ t`. i vˆ i , `1¯ e ´ ¯˙ `2 ’ doc theo chu tr` µ1 t` 1 e ınh u ¯e 2¯ ınh 2 u 2 e . . v` vˆn vˆn, l` mˆt dˆy chuyˆn Euler xuˆ t ph´t t`. a v` kˆt th´c tai b. Dinh l´ d u.o.c ch´.ng -. ` ´ ´ aa a a o a e a au ae u. y¯ . u . minh. -ˆ . e ˙ -. D` thi thoa c´c d iˆu kiˆn cua Dinh l´ Euler goi l` d` thi Euler. ˙ a ¯` ’ ’ o e y . a ¯ˆ . o . ` 5.1.1 Thuˆt to´n t` dˆy chuyˆn Euler a a ım a e . C´ch ch´.ng minh Dinh l´ Euler 5.1.3 cho ta mˆt thuˆt to´n xˆy du.ng dˆy chuyˆn Euler -. ` a u y o a aa a e . . . trong mˆt d` thi Euler. o ¯ˆ . o . 1. Xˆy du.ng mˆt dˆy chuyˆn d o.n gian µ xuˆ t ph´t t`. s. `¯ ´ ˙ ’ a oa e a au . . 2. Nˆu tˆ t ca c´c canh cua G d a d u.o.c su. dung th` d`.ng v` ta c´ µ l` dˆy chuyˆn Euler. ´´’ ` e a ˙a . ˙ ’ ¯˜ ¯ . ˙ . ’ ıu a o aa e .o.c lai sang Bu.´.c 3. Ngu . . o 3. K´ hiˆu G1 l` d` thi con cua G gˆm c´c canh chu.a d u.o.c su. dung. Chon d ınh c cua G1 ` ˙ ’ ¯. ˙ . ’ . ¯˙’ ˙ ’ ye a ¯o . ˆ oa. . .ng chu tr` d o.n gian µ trong d` thi G xuˆ t ph´t ` ` ´ ˙ ’ nˇ m trˆn dˆy chuyˆn µ. Xˆy du a ea e a ınh ¯ ¯o . 1 a ˆ a . 1 . d ınh c. ˙ ’ t` ¯ u 4. Mo. rˆng dˆy chuyˆn µ bˇ ng c´ch gˇn thˆm chu tr` µ1 tai d ınh c (t´.c l` d˜y c´c ` ´ ` ˙o ’. . ¯˙ ’ a e a a a e ınh uaa a .o.c ch`n v`o d˜y c´c canh cua µ). ˙ ’ ˙ ’ canh cua µ1 d u . ¯ eaaa. . 5. Thay G bo.i G1 v` lˇp lai bu.´.c 2. ˙ ’ aa . o . -ˆ . V´ du 5.1.4 D` thi trong H` 5.2 c´ mˆt chu tr` Euler ı. o ınh oo ınh . (v1 , e1 , v2 , e2 , v3 , e3 , v2 , e4 , v3 , e15 , v4 , e14 , v5 , e13 , v4 , e12 , v6 , e11 , http://www.ebook.edu.vn 129
e2 .................................. .... .......................... ......... ........ ...... ...... ...... ...... ..... ..... ..... ..... .... .... .... .... .... e3 .. .... . .... .... .... ... v2 v3 ... . ... ...................................................................................... ........................................................................................... ... .... ... .... . ... . .... .... ..... ... .... . ... . .. . ... .... . ..... . ... .... . ..... .... .... .... . ... ..... .... ..... . ... . .... .. . ... ... . ..... ....... ..... . e4 . .. . ... ...... .. ... ......... . ... . ...... ... ...... . ... . ... ... ... ........ ...... . ........ ....... .. .. ... ........ ... . . ............................ ............................ . ... ... . ... ... .. . .. . . . ... . .... ... ... .... . ... . ... . . ... . e1 .... ... .... . ... . ... ... . . . . ... .... .... . ... ... . ... . . . .... ... .... ... . ... ... . e16 e15 . . . . ... .... .... ... ... . ... . . . . ... .... ... .... ... . ... . . . ... . . e17 ... .... ... .... . ... . ... . ... . . .... ... .... . ... . ... ... . . . . ... .... .... . ... ... . ... . . . ... .... .... . ... ... ... . . . . . ... .... ... . ... .... e14 ... . . . . ... .... ... ... .... . ... . v7 . .. . . . . .... ... . .... ... ....................... ..... ....................... .... . . .... .... e5 . . .... ... ....... . ........... .... . ... ...... .. . ..... .. . . .. ... . . . ... . .... v1 v5 v4 ...... . ........................................................... ...... ....... .... .. . .......................................................... . ..... .. ... ..... . .. .... .. ... .. . ...... ..... ...... . ... . .. . ... . . ..... . ... . ..... ... . .......... . .. . ... ...... .. . .. . . ... .............................. .... .... ........ . . . ............. ......... .... .... .. .... . . ... .. . . .... e13 . .... ... ... . ... . . .. .. .... .. . . ... .... .. ... . .. . . .... . .. ... ... ... ... .... .. . . . . ... .... ... ... . . ... .. .... .. . . ... . .... ... . ... ... . .... . .. ... .. . . ... .... ... . e6 . ... .... e10 . .. . ... .. ... .... . . .. ... .... ... . . ... . ... ... . .... ... .. . . .... .. . ... . ... ... . .... ... . ... ... .... . . e8 e11 e12 ... . ... . .... ... ... . ... ... . .... . . ... ... .... . ... ... . ... ... .... . . ... . . .... ... .. ... . ... ... .... . . e7 . ... ... .... ... . . ... ... ... .... . . ... . . .... .. ... .. ... . . ... .... . .. . ... .... . . ... . .. ... .... .. . . . ... .... . ... .. ... ... . .. .... . . . ... .... .. ... .. . . . .. . .... . ... . ... ... . .... ... .. . .... . ... .. . ... ... . ... .... . . .... . ... ... . ... ... ... . . ..... .... . ... .. . .... . .... . ..... .... . . . .... ... . . . . .. .... . . .... . .. ... . .. .... .. ..... .. ................................................................................................ ............................................................................................ .... . .. e9 v8 v6 H` 5.2: Mˆt v´ du vˆ d` thi Euler. o ı . ` ¯ˆ . ınh eo . v5 , e16 , v3 , e17 , v7 , e10 , v6 , e9 , v8 , e8 , v7 , e5 , v1 , e7 , v8 , e6 , v1 ). Mˆt dˆy chuyˆn hay chu tr` Euler c´ thˆ’ d u.o.c x´c d inh bo.i mˆt danh s´ch c´ th´. ˙ ` ˙’ oa e ınh o e ¯ . a ¯. o a ou . . . c´c d ınh cua G ch´.a trong n´. Chˇng han, ta c´ thˆ’ su. dung mˆt cˆ u tr´c danh s´ch ˙˙ . ˙ ’ ´ ˙ ’ ˙ ’ ’ tu a ¯ u o a oe oa u a . . . ´ liˆn kˆt ee typedef struct PathNode *PathPtr; struct PathNode { byte Vertex; PathPtr Next; }; dˆ’ d ´nh dˆ u c´c d ınh liˆn tiˆp trˆn dˆy chuyˆn, trong d ´ V ertex l` sˆ hiˆu d ınh trˆn dˆy ˙ ´ ´ ` ´. a a ¯˙ ’ a o e ¯˙ ’ ¯e ¯a e e ea e ¯o ea .a sˆ hiˆu cua d ınh kˆ V ertex trˆn dˆy chuyˆn. ` ´´ u´. ` ` chuyˆn; v` con tro N ext chı n´t kˆ tiˆp ch´ o e ˙ ¯˙ ˙ ’ ˙u ee ’ ’’ e a e ea e ˜ thˆ y rˇ ng, danh s´ch n`y c´ sˆ n´t bˇ ng (m + 1). ` ´u ` ´a Dˆ a e a a oo a T`. d ˆy vˆ sau ta s˜ gia thiˆt G d u.o.c cho bo.i mang c´c danh s´ch kˆ V out[] (c´ u ¯a ` ´ ` e˙ ’ ˙’ ˙ ’ e e ¯. a a e o ´), trong d ´ v´.i mˆ i d ınh vi ∈ V, V out[i] l` danh s´ch c´c d ınh liˆn thuˆc d ınh vi ˜ ¯˙ o’ a ¯˙’ o ¯˙’ trong sˆ o ¯o o a a e . . v` tru.`.ng d o d`i Length o. n´t th´. j (tu.o.ng u.ng d ınh vj ) l` sˆ canh liˆn thuˆc v´.i d ınh ´ ˙u ’ ¯˙ ’ o o ¯˙ ’ a o ¯ˆ a u ´ ao. e . . .c hiˆn thuˆt to´n, mˆ i khi d i qua canh (v , v ) n`o d ´, ta giam d o ˜ ˙ ¯ˆ ’ vi . Trong qu´ tr` thu a ınh . e a a o ¯ a ¯o . . . . ij http://www.ebook.edu.vn 130
d`i Length mˆt d o.n vi o. n´t th´. j trong danh s´ch V out[i] dˆ’ d ´nh dˆ u canh d ˜ d u.o.c su. ˙ ´ .˙ u ’ ¯a ¯ . ˙ ’ a o¯ u a ¯e ¯a a. . dung. . V` mˆ i canh cua d` thi d u.o.c kiˆ’m tra nhiˆu nhˆ t hai lˆn nˆn d o ph´.c tap cua thuˆt ˙ ˜ ` ´ ` ˙ ¯o . ¯ . ’ˆ ˙ ’ ıo. e e a a e ¯ˆ u . a . . to´n l` O(m). aa B`i to´n ngu.`.i d .a thu. Trung Hoa 5.2 a a o ¯u X´t d` thi vˆ hu.´.ng liˆn thˆng G := (V, E ) c´ trong sˆ (t´.c l` mˆi canh e ∈ E ta g´n mˆt ˜ ´ e ¯ˆ . o o o e o o. ouao. a o . ´ w(e) goi l` trong lu.o.ng cua canh e). ˙. ’ sˆ o .a. . B`i to´n ngu.`.i d u.a thu. Trung Hoa (khˆng d u.o.c d .nh hu.´.ng) ph´t biˆ’u rˇ ng t` mˆt ˙a ae` aa o¯ o ¯ . ¯i o ım o . .a hai d ınh cho tru.´.c a, b ∈ V su. dung mˆi canh cua G ´ nhˆ t mˆt lˆn v` c´ ˜ ` ´ o` ao ¯˙ ’ ˙. ’ ˙ ’ dˆy chuyˆn gi˜ a e u o o. ıt a a . ´ ˙ ’a d o d`i nho nhˆ t (xem [44]). ¯ˆ a . Nhiˆu b`i to´n vˆ h`nh tr` (ngu.`.i d u.a thu., ngu.`.i giao s˜.a, ngu.`.i ch`o h`ng, v.v) `e a a`a e ınh o¯ o u o aa ˙ ph´t biˆ’u o. dang n`y. Trong tru.`.ng ho.p d` thi c´ hu.´.ng, trong d o mˆi cung cua G ’a ˙˙. ˜ e’ ˙ ’ c´ thˆ oe a o . ¯o . o o ˆ ¯´ o cˆn d u.o.c su. dung ´ nhˆ t mˆt lˆn, b`i to´n c´ thˆ’ d u.a vˆ b`i to´n luˆng v´.i chi ph´ nho ˙ ` ¯. ˙ . ´ o` `a ` ’ ˙ ’ a ıt a a a a o e¯ e a o o ı . ´ nhˆ t (b`i tˆp). a aa . T`. d ˆy vˆ sau ch´ng ta chı x´t d` thi vˆ hu.´.ng. Khˆng mˆ t t´ tˆ’ng qu´t c´ thˆ’ ˙ ˙ u ¯a ` ´ ˙ e ¯ˆ . o o ’ e u o o a ınh o aoe .`.ng ´’ ´ ´ `au ˙ ’ e ¯˙ a ¯˙ ’ gia thiˆt d ınh xuˆ t ph´t a v` d ınh kˆt th´c b trˆn dˆy chuyˆn l` tr`ng nhau. Trong tru o a a e u ea e .p ngu.o.c lai, ta chı cˆn thˆm mˆt canh (a, b) v´.i d o d`i bˇ ng khˆng. V´.i mˆ i chu tr` o ¯ˆ a ` ˜ ˙` ’a ho e o. a o o o ınh . .. . . .i n`y, tˆn tai mˆt dˆy chuyˆn trˆn G c´ c`ng d o d`i v` c´ d o d`i nho nhˆ t trˆn d` thi m´ a ` . ´ e ¯o . o ` ˙ ’a o ¯ˆ a ˆ o oa e e o u ¯ˆ a a . . . ´ ˙ ’a do d o l` nho nhˆ t. ¯´ a ˜ Nˆu G l` d` thi Euler th` tˆn tai mˆt chu tr` Euler d i qua mˆ i canh d ung mˆt lˆn ´ ı` . o` e a ¯ˆ . o o o ınh ¯ o. ¯´ .a . .u cua b`i to´n. ´ ˙aa ’ v` v` vˆy l` mˆt nghiˆm tˆi u aıa a o e o . . . N´i chung, G khˆng phai l` d` thi Euler, nˆn tˆn tai mˆt sˆ c´c d ınh bˆc le. K´ hiˆu e`. .´ ˙ a ¯o . ’ o o a ¯˙ ’ a˙ .’ o o ˆ o ye . V1 l` tˆp c´c d ınh cua G c´ bˆc le. Dˆ thˆ y rˇ ng sˆ phˆn tu. cua tˆp V1 l` mˆt sˆ chˇn. Khi ´˜ ’˜a` e´a o` ˙˙a ´a ’’. a a a ¯˙ ’ ˙ ’ oa˙ aooa . . . d o b`i to´n ngu.`.i d u.a thu. Trung Hoa d u.a vˆ viˆc thˆm mˆt sˆ canh v`o G dˆ’ tro. th`nh ˙’ `e ´ ¯e ˙ a ¯´ a a o¯ ¯ e. e oo. a . ` thi Euler v` c`ng l´c, cu.c tiˆ’u ho´ tˆ’ng c´c trong lu.o.ng cua c´c canh d u.o.c thˆm v`o. ˙ ˙ ˙a. ’ do . ¯ˆ au u e ao a ¯. e a . . . Ch´ng ta khˆng thˆm mˆt canh e = (vi , vj ) tr`. khi d ˜ tˆn tai mˆt canh e = (vi , vj ) ¯a ` . u o e o. u o o. . . .o.ng cua canh e l` w(e ) := w(e). Canh e goi l` ban sao cua e. ˙. ’ .a˙ ’ ˙ ’ trong G v` g´n trong lu . aa a . . X´t mˆt l`.i giai tˆi u.u cua b`i to´n v` d at E l` tˆp c´c canh d u.o.c thˆm v`o G. K´ ’´ ˙o ˙ a a a ¯ˇ ’ e oo aa a . ¯. e a y . . . .o.c. hiˆu G = (V, E + E ) l` d` thi Euler nhˆn d u . e a ¯ˆ . o a¯ . . http://www.ebook.edu.vn 131
Bˆ’ d` 5.2.1 Gia su. vi l` mˆt d ı’nh bˆc le trong G. Khi d ´ tˆp E ch´.a mˆt dˆy chuyˆn ˙e ` ˙˙ ’’ a o ¯˙ a˙ .’ o ¯ˆ ¯o a u oa e . . . . cˆ p nˆi d ı’nh v v´.i mˆt d ı’nh v = v c´ bˆc le trong G. ´´ so a o ¯ ˙ o ¯˙ oa ˙ ’ o . . i j i Ch´.ng minh. V´.i moi d ınh vk ∈ V1 ta c´ dG (vk ) ≡ 1 (mod 2) v` dG (vk ) ≡ 0 (mod 2); ngo`i . ¯˙’ u o o a a .ng d (v ) ≥ d (v ). Do d ´ tˆn tai ´ nhˆ t mˆt canh e ∈ E liˆn thuˆc ¯o ` . ıt a ´o. ra, theo c´ch xˆy du a a o e o . . . G k Gk 1 ¯˙’ d ınh vi . K´ hiˆu vi1 l` d ınh kh´c vi m` canh e1 liˆn thuˆc. Nˆu dG (vi1 ) ≡ 1 (mod 2) th` bˆ’ d` ˙e ´ a ¯˙’ ye a a. e o e ı o ¯ˆ . . .o.c ch´.ng minh v´.i v = v . Ngu.o.c lai, nˆu d (v ) ≡ 0 (mod 2) th` d (v ) ≥ d (v ) + 2 ´ G i1 du . ¯ u oj ..e ı G i1 i1 G i1 a` . . o ¯˙ ’ a ¯˙’ v` tˆn tai canh e2 ∈ E , e2 = e1 , liˆn thuˆc d ınh vi1 . K´ hiˆu vi2 l` d ınh kh´c vi1 m` canh o e ye a a. . . ˙ d` d u.o.c ch´.ng minh v´.i vj = vi2 . Ngu.o.c lai, ’ ¯ˆ ¯ . ´ e2 liˆn thuˆc. Nˆu dG (vi2 ) ≡ 1 (mod 2) th` bˆ e e o e ıo u o . .. `.. o ¯˙ ’ tˆn tai canh e3 ∈ E , e3 = e2 , liˆn thuˆc d ınh vi2 , v` vˆn vˆn. o e aa a . Do d o ta xˆy du.ng d u.o.c mˆt dˆy chuyˆn so. cˆ p d`i nhˆ t c´ thˆ’ ˙ ` ´ ´ ¯´ a ¯. oa e aa aoe . . (vi , e1 , vi1 , e2 , vi2 , . . . , ep , vip ). Nˆu dG (vip ) ≡ 1 (mod 2) th` bˆ’ d` d u.o.c ch´.ng minh v´.i vj = vip . Ngu.o.c lai, tˆn tai canh ˙e ´ ..`.. e ı o ¯ˆ ¯ . u o o .`.ng ho.p n`y, tˆn tai chı sˆ a` ’´ o ¯˙ ’ ˙o ep+1 ∈ E , ep = ep+1 , liˆn thuˆc d ınh vip v` vip+1 . Trong tru o e a o. . . ´e ’´ ’ ˙a ˙a . q, 1 ≤ q ≤ p, sao cho viq ≡ vip+1 v` ta c´ mˆt chu tr` xuˆ t hiˆn. Loai bo tˆ t ca c´c canh a oo ınh a . . . trong chu tr` n`y ta d u.o.c mˆt d` thi con G cua G sao cho n´ vˆ n l` d` thi Euler v` ˜ ˙ ’ ınh a ¯. o ¯ˆ .o o a a ¯ˆ . o a . .n n˜.a ho u dG (vk ) ≥ dG (vk ), v´.i moi d ınh vk ∈ V. . ¯˙’ o Lˇp lai c´ch xˆy du.ng dˆy chuyˆn trˆn, xuˆ t ph´t t`. d ınh viq chı su. dung c´c canh ` ´ a u ¯˙ ’ ˙˙ . ’’ a.a a a e e a a. . . ˙ ’ cua G . Do sˆ c´c canh trong E l` h˜.u han, nˆn sau mˆt sˆ h˜.u han bu.´.c ta d u.o.c mˆt d ınh ´ .´ o ¯˙ .’ oa . au e oou o ¯. . . .o.c ch´.ng minh v´.i v = v . vip sao cho dG (vip ) ≡ 1 (mod 2) v` bˆ’ d` d u . ˙e a o ¯ˆ ¯ u oj ip Bˆ’ d` 5.2.2 Gia su. vi v` vj l` hai d ı’nh thoa m˜n c´c d iˆu kiˆn cu a Bˆ’ d` 5.2.1 v` k´ ˙e ˙e ˙ a a ¯` ˙˙ ’’ ¯˙ ’ ˙ ’ o ¯ˆ a a e e o ¯ˆ ay . .o.ng u.ng l` ` hiˆu dˆy chuyˆn tu ea e ´ a . µ := {e1 , e2 , . . . , ep } aa ˙ ’ ˙ ’ trong d ´ ek ∈ E , k = 1, 2, . . . , p. C´c canh e1 , e2 , . . . , ep l` c´c ba n sao cu a c´c canh ¯o a. a. ` e1 , e2 , . . . , ep trong G v` x´t dˆy chuyˆn µ := {e1 , e2 , . . . , ep } trong G. Khi d ´ µ l` dˆy ae a e ¯o aa chuyˆn (trong G) c´ trong lu.o.ng nho nhˆ t nˆi d ı’nh vi v´.i d ı’nh vj . ` ´´ ˙ ’ a o ¯˙ o ¯˙ e o. . Ch´.ng minh. Nˆu tˆn tai mˆt dˆy chuyˆn µ = {e1 , e2 , . . . , eq } nˆi d ınh vi v´.i d ınh vj trong e`. ´o `¯ ´’ o ¯˙ o ¯˙ ’ u oa e ¯¯ ¯ . .n th` bˇ ng c´ch loai c´c canh e , e , . . . , e khoi G v` thˆm c´c ban sao ı` ˙ ’ ˙ ’ a˙ ’ G c´ d o d`i nho ho o ¯ˆ a a a .a. ae . 12 p http://www.ebook.edu.vn 132
e1 , e2 , . . . , eq cua e1 , e2 , . . . , eq ta nhˆn d u.o.c mˆt d` thi Euler m´.i c´ tˆ’ng trong lu.o.ng nho ˙ ¯ ˙¯¯’ ˙ ’ ¯¯ ¯ a ¯. o ¯ˆ . .o o oo . . . .n, mˆu thuˆn. ˜ ho a a Bˆy gi`. x´t d` thi d` y d u K(V1 ) trˆn tˆp c´c d ınh V1 trong d o c´c canh thˆm v`o o e ¯ˆ . ¯a ¯ ˙ ’ e a a ¯˙ ’ a o ˆ ¯´ a . e a . .o.ng w bˇ ng d o d`i cua dˆy chuyˆn nho nhˆ t trong G gi˜.a hai d ınh v ` ` ´ ˙a ’ ˙ ’a ˙ ’ (vi , vj ) c´ trong lu . o. ij a ¯ˆ a e u ¯ . i v` vj . Khi d ´ mˆ i canh cua K(V1 ) tu.o.ng u.ng v´.i mˆt dˆy chuyˆn trong G. V` w(e) ≥ 0 v´.i ˜ ` ˙ ’ a ¯o o . ´ ooa e ı o . moi canh e ∈ E nˆn wij c´ thˆ’ d u.o.c x´c d .nh bˇ ng thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t, ˙ ` ´ ´ e o e ¯ . a ¯i a a a ım ¯ o ¯ a a .. . ˙ ’ chˇng han Floyd (xem 3.3.2) hay Dantzig [16]. a . Dinh l´ 5.2.3 Tˆn tai tu.o.ng u.ng mˆt-mˆt gi˜.a l`.i gia i tˆi u.u cu a b`i to´n ngu.`.i d u.a -. `. ’´ ˙o ˙a ’ y o ´ oouo a o¯ . . thu. Trung Hoa v´.i mˆt cˇp gh´p ho`n ha o c´ trong lu.o.ng nho nhˆ t trong d` thi K(V1 ). ´ ˙o. ’ ˙ ’a o oa e a ¯ˆ . o .. . Ch´.ng minh. X´t mˆt l`.i giai tˆi u.u cua b`i to´n ngu.`.i d u.a thu. Trung Hoa v` d at E l` ’´ ˙o ˙aa ’ u e oo o¯ a ¯ˇ a . . tˆp c´c canh thˆm v`o G. Theo Bˆ’ d` 5.2.1 ta c´ thˆ’ thiˆt lˆp tu.o.ng u.ng v´.i mˆ i d ınh ˙e ˙ ˜’ ´. o ¯˙ aa. e a o ¯ˆ oe ea ´ o . vi ∈ V1 v´.i mˆt d ınh vj ∈ V1 bˇ ng mˆt dˆy chuyˆn so. cˆ p µij m` c´c canh thuˆc E . Theo ` ` ´ o o ¯˙ .’ a oa e a aa . o . . ˙ d` 5.2.2, µij c´ d o d`i nho nhˆ t. Trong d` thi K(V1 ) c´c dˆy chuyˆn µij tu.o.ng u.ng canh ’ ¯ˆ ´ ` ˙a ’ Bˆ e o o ¯ˆ a ¯o . ˆ aa e ´ . . (vi , vj ). Do d o tˆ t ca c´c d ınh cua V1 d u.o.c kˆt ho.p, hai v´.i hai, v` c´c canh (vi , vj ) tu.o.ng ´’ ´ ¯´ a ˙ a ¯˙ ’ ˙ ’ ¯. e . o aa . u.ng dˆy chuyˆn µij cua G , tao th`nh mˆt cˇp gh´p ho`n hao K cua d` thi K(V1 ). (Trong ` ˙ ’ ˙ ’ ˙ ¯o . ’ˆ ´ a e a oa e a . .. ` thi d` y d u v´.i sˆ chˇn d ınh luˆn luˆn tˆn tai mˆt cˇp gh´p ho`n hao; xem Phˆn 7.5). ´˜ `. ` ˙ o o a ¯˙ ’ ’ ˙ ’ d o . ¯a ¯ ¯ˆ ˆ o oo oa e a a .. .o.ng cua cˇp gh´p ho`n hao K bˇ ng tˆ’ng c´c trong lu.o.ng cua c´c canh cua E ˙ ` ˙a ’. ˙ ’ ˙a. ’ ˙ ’ V` trong lu . ı. e a a o a . . .i giai cua b`i to´n ngu.`.i d u.a thu. Trung Hoa l` tˆi u.u nˆu v` chı nˆu K l` mˆt cˇp ´ ´ ’´ ˙˙aa ’’ e a ˙e nˆn l` eo o¯ ao aoa .. gh´p ho`n hao v´.i trong lu.o.ng nho nhˆ t. Ta c´ d iˆu phai ch´.ng minh. ´ o ¯` ˙o ’ ˙ ’a ˙ ’ e a e u . . Do d o nghiˆm cua b`i to´n ngu.`.i d u.a thu. Trung Hoa d u.a vˆ b`i to´n t` mˆt cˇp `a ˙a ’ ¯´ e a o¯ ¯ e a ım o a . .. ˙ o c´ trong lu.o.ng nho nhˆ t cua d` thi d` y d u Kn . Viˆc x´c d .nh nghiˆm cua ´’o ’o. ˙ ’ a ˙ ¯ˆ . ¯ˆ ¯ ˙ ’ ˙ ’ gh´p ho`n ha e a a e a ¯i e . . . .c tap v` do d o s˜ khˆng d u.o.c tr` b`y o. d ˆy. Ban ınh a ˙ ¯a ’ b`i to´n sau l` mˆt thuˆt to´n kh´ ph´ . a aa ao a a au ¯´ e o ¯ . . . . ˙ tham khao c´c t`i liˆu [14], [30]. ’ ˙aae ’ d oc quan tˆm c´ thˆ ¯. a oe . e`.. ´o Nhˆn x´t 5.2.4 Nˆu tˆn tai canh e trong G sao cho w(e) < 0 th` b`i to´n khˆng c´ nghiˆm a e ıa a o o e . . .u: Thˆt vˆy, bˇ ng c´ch thˆm mˆt tˆp E hu.u han c´c ban sao cua c´c canh cua G ta ` ´ .a˙ ’ ˙a. ’ ˙ ’ tˆi u o aa a a e oa ˜ .. .. c´ thˆ’ thˆm canh e mˆt sˆ chˇn lˆn d u l´.n, v` do d o nhˆn d u.o.c mˆt d` thi Euler v´.i d ˆ .´˜a ˙ o o a ` ¯˙ o ’ oee a ¯´ a ¯ . o ¯o . .ˆ o ¯o . . . .o.ng khˆng ˆm l` khˆng mˆ t t´ tˆ’ng ˙ ´ ´ ˙ y´ ’ ˙ ’ d`i nho tu` y. Vˆy gia thiˆt c´c canh c´ trong lu . a a ea. o. oaao a ınh o . qu´t dˆ’ loai tr`. tru.`.ng ho.p tˆm thu.`.ng n`y. ˙ .` a ¯e . u o a o a V´ du 5.2.5 X´t d` thi trong H` 5.3 v´.i c´c sˆ trˆn c´c canh l` trong lu.o.ng canh. Ta ´ ı. e ¯ˆ . o ınh oaoea. a. . . ˜. ` n t` mˆt chu tr` qua mˆ i canh ´ nhˆ t mˆt lˆn v` c´ d ˆ d`i nho nhˆ t. ´ o` ´ ˙ ’a cˆ ım o a ınh o ıt a . a a o ¯o a . . Tˆ’ng c´c trong lu.o.ng c´c canh cua G bˇ ng 31. V` G khˆng l` d` thi Euler nˆn d ˆ d`i ˙ ` ˙ ’ o a a. a ı o a ¯o . ˆ e ¯o a . . . .n ho.n 31. ınh ` ım e o ˙ ’ cua chu tr` cˆn t` s˜ l´ a http://www.ebook.edu.vn 133
3 m m 6 ......................................................................................... 2 ........ . . . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . ... . . ... . . 2 . . ... ... . . . . 4 1 ... . . ... . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . . . ... ... . . . . ... . . ... . . . . ... 3 m2 ... . . . . .. . m m 1 ......................................................................................... 7 3 ........................... ........................... .. . . . ... ... . . . . . . .. ... . . . . ... . . ... . . ... . . ... . . . . ... . . .. . . ... . . ... . . . . 2 4 .. .. . . . . ... ... . . 3 . . ... . . ... . . . . ... ... . . . . ... . . ... . . . . ... .. . . . . ... ... . . . . 7 . . ... ... . . m m 5 ......................................................................................... 4 H` 5.3: ınh Tˆp c´c d ınh bˆc le l` V1 = {1, 2, 3, 4}. Theo thuˆt to´n t` d u.`.ng d i ngˇn nhˆ t (xem ´ ´ a a ¯˙ ’ a ˙a .’ a a ım ¯ o ¯ a a . . .o.ng 3), ta t` tˆ t ca c´c dˆy chuyˆn c´ d ˆ d`i nho nhˆ t gi˜.a c´c cˇp d ınh cua V trong ´ ˙a a ` o ¯o a ´ ’ ˙ a u a a ¯˙ ’ ’ ˙1 ’ Chu ım a e . . G. Ta nhˆn d u.o.c m` trˆn d ˆ d`i d u.`.ng d i ngˇn nhˆ t: ´ ´ a¯. a a ¯o a ¯ o ¯ a a . . . 1 2 3 4   10 4 5 7 24 5 0 2   .  35 2 0 3 47 5 3 0 Tiˆp dˆn ta xˆy du.ng d` thi d` y d u K(V1 ) trong d ´ trong lu.o.ng canh (vi , vj ) l` d o ´´ ¯o . ¯a ¯ ˙ ’ e ¯e a ˆ ˆ ¯o . a ¯ˆ . . . . ˙ a dˆy chuyˆn ngˇn nhˆ t gi˜.a vi v` vj (xem H` 5.4). ´ ` ´u ’a d`i cu a e a a a ınh 4 m m 1 ......................................................................................................... 2 . . . . . . ... . . . ... ... ... . . . . ... ... ... . . ... . . ... . . ... ... ... . . . . ... ... ... . . ... . . . . ... ... . .. . . ... . . ... .. . . ... ... . . ... . . ... ... . . ... ... . . ... ... . . . . ... .... ... .... . . . . . . ..... 7 2 .... . . . . . . . .... ... .... . . ... .... . . . . ... ... . . ... . . ... .. . . ... ... . . ... ... . . 5 5 . . ... . . . . ... ... ... . . ... . . ... ... . . ... . . ... . . . ... ... . . ... ... . . . . ... . ... . . ... ... . . ... . . . . ... . . ... . .... . . ... . 3 ... . .... .. . ... . . . m m 4 3 ............................................. ............................................ - ˆ . ¯ˆ ¯ ˙ H` 5.4: D` thi d` y d u K(V1 ). ’ ınh o a Cˇp gh´p ho`n hao v´.i trong lu.o.ng nho nhˆ t trˆn K(V1 ) gˆm c´c canh (1, 2) v` (3, 4) ´ ` ˙o ’ ˙ae ’ a e a o a. a . . . .o.ng bˇ ng 4 + 3 = 7). C´c dˆy chuyˆn tu.o.ng u.ng l` {1, 7, 2} v` {3, 4}. ` ` (trong lu . a aa e ´ a a . Nghiˆm tˆi u.u cua b`i to´n nhˆn d u.o.c bˇ ng c´ch thˆm v`o d` thi ban d` u c´c canh a¯. ` ´ ˙aa ’ e o a a e a ¯ˆ . o ¯ˆ a . a . . - ` thi G nhˆn d u.o.c l` d` thi Euler (H` 5.5). (1, 7), (7, 2) v` (3, 4). Dˆ . a o a ¯ . a ¯ˆ . o ınh . http://www.ebook.edu.vn 134
m m 6 ............................................................................................... 2 ........ . . . . . . . ... . . ... . . .. . . . ... . . ... . . . . . ... . ... . . . . . . ... . . ... . . . . . . ... . ... . . . . . . ... . . . ... . . . . . . ... . ... . . . . . . . ... . . ... . . . . . . . ... ... . . . . . . . ... . . ... ...................... ... . . . ................... ......... . . ........ ... ... ..... .. . . . . .. ..... . . ........ ... . ........ . . ... ..... . .... . .. .. .. . . m m m 1 7 3 ............................................. ............................................ ........................... ........................... . .. ... . ... . . . . . . . . . ... . ... .. . . . . . ... . . ... . . . . . . . .. ... . . ... . . . . . .. ... ... . . .. . . . . ... ... .. . . . . . .. .. . . .. .. . . ... . . ... .. .. . . . . ... ... ... ... . . . . ... . . ... ... ... . . . . . .. .. . . . ... ... . . ... ... . . ... . . ... ... ... . . . . .. ....... .. ....... m m . 5 4 .... .... ............................................. ............................................ H` 5.5: D` thi Euler G nhˆn d u.o.c t`. G bˇ ng c´ch thˆm c´c canh tu.o.ng u.ng c´c dˆy -ˆ . ` ınh o a ¯. u a a e a. ´ aa . ` n nho nhˆ t gi˜.a 1 v` 2 v` gi˜.a 3 v` 4. ´u ˙ ’a chuyˆe a au a ˙ ’ ´ ˙ ` ım o ’a Cuˆi c`ng ta chı cˆn t` mˆt chu tr` Euler trong G , chˇng han ou ınh a . . {6, 2, 3, 7, 2, 7, 1, 7, 4, 5, 1, 6} l` chu tr` c´ d ˆ d`i 31 + 7 = 38 l` nghiˆm tˆi u.u cˆn t` ´ ` ım. a ınh o ¯o a a e o a . . 5.3 B`i to´n Hamilton a a Gia su. G := (V, E ) l` d` thi liˆn thˆng (hay liˆn thˆng manh trong tru.`.ng ho.p c´ hu.´.ng) ˙˙ ’’ a ¯o . e ˆ o e o o .oo . o ¯˙ ’ c´ n d ınh. Dinh ngh˜ 5.3.1 Dˆy chuyˆn (hay d u.`.ng d i) d i qua tˆ t ca c´c d ınh cua d` thi G, mˆi -. ˜ ` ´’ a ˙ a ¯˙ ’ ˙ ¯o . ’ˆ ıa a e ¯o ¯¯ o .`.ng d i Hamilton). o` ` ¯˙’ d ınh mˆt lˆn, goi l` dˆy chuyˆn Hamilton (hay d u o .a .aa e ¯ ¯ Theo d .nh ngh˜ dˆy chuyˆn (hay d u.`.ng d i Hamilton) l` so. cˆ p, v` c´ d ˆ d`i (n − 1). ` ´ ¯i ıa, a e ¯o ¯ a a a o ¯o a . ´’ a ˙ a ¯˙’ Chu tr` (hay mach) Hamilton l` mˆt chu tr` (hay mach) d i qua tˆ t ca c´c d ınh ınh ao ınh ¯ . . . cua d` thi G, mˆi d ınh d ung mˆt lˆn. Dˆ thˆ y rˇ ng, chu tr` Hamilton l` chu tr` so. cˆ p ˜’ ˜a` o` e´a ´ ˙ ¯o . ’ˆ o ¯˙ ¯ ´ a ınh a ınh a . .a mˆt chu tr` Hamilton (trong ` c´ d o d`i n. Ta n´i rˇ ng, G l` d` thi Hamilton nˆu n´ ch´ ´ o ¯ˆ a oa a ¯ˆ . o eou o ınh . . .`.ng ho.p vˆ hu.´.ng) hoˇc mˆt mach Hamilton (trong tru.`.ng ho.p c´ hu.´.ng). tru o oo a o o .oo . . . . V´ du 5.3.2 Nˇm 1859, nh` to´n hoc Hamilton (1805-1865) ngu.`.i Ailen d ˜ cho b´n mˆt ı. a aa o ¯a a o . . d` cho.i d oc d ´o, phˆn ch´ l` mˆt khˆi nhi diˆn d` u (khˆi d a diˆn c´ 12 mˇt ng˜ gi´c d` u ` ´ ´ ¯o ˆ ¯ˆ ¯a a ınh a o o e ¯ˆ e o¯ eo a u a ¯ˆ e . . .. . . ˜ ’. ˜ ’ v` 20 d ınh, mˆ i d ınh c´ 3 canh) l`m bˇ ng gˆ . O mˆi d ınh c´ ghi tˆn mˆt th`nh phˆ l´.n: o ˙ o ¯˙ ˜’ ` ´ ¯˙’ o ¯˙ a o a a o e o a oo . . .i l` t` mˆt d u.`.ng d i doc theo c´c ˙ ’ Beruych, Quang chˆu, Deli, Frangfua, v.v... C´ch cho a ım o ¯ o a a ¯. a . http://www.ebook.edu.vn 135
canh cua thˆp nhi diˆn d` u v` qua mˆ i d ınh (th`nh phˆ) v`.a d ung mˆt lˆn. Muˆn tr` cho.i ˜’ ´ o` ´ ˙ ’ o ¯˙ a . e ¯ˆ a e a o u ¯´ .a o o . . . .o.c hˆ p dˆ n ho.n c´ thˆ’ quy d inh tru.´.c tr` tu. qua mˆt v`i th`nh phˆ d` u tiˆn, v` dˆ’ ˙ ˙ ´˜ ´a du . a a ¯ oe ¯. o ınh . oa a o ¯ˆ e a ¯e . . dˆ d`ng c´c th`nh phˆ d a d i qua, o. mˆi d ınh cua khˆi thˆp nhi diˆn d` u c´ d ´ng gi´p nh´ ˜ a ’˜’ ´ ´a ˙ o ¯˙ ˙ ’ u oe a a o ¯˜ ¯ o . e ¯ˆ o ¯o e . . ´c d inh m˜ to, quanh d ´ c´ thˆ’ quˆ n so.i dˆy nho dˆ’ chı d oan d u.`.ng d a d i qua. Vˆ ˙a.a ’˙’ ´ ` ˙ ¯e ˙ ¯ . ¯ o mˆt chiˆ ¯ o e u ¯o o e ¯˜ ¯ e . .n gian, Hamilton d ˜ thay khˆi thˆp nhi diˆn d` u bˇ ng mˆt h` phˇng. B`i to´n sau dˆ’ d o ˙ e ¯ˆ ` ˙ ’ ´a ˙ ’ ¯e ¯ ¯a o ea o ınh a aa . .. . d u.o.c ph´t biˆ’u du.´.i dang d` thi nhu. sau. Ta biˆt rˇ ng h` thˆp nhi diˆn d` u c´ 12 mˇt, ˙ e` ´a ¯. a e o. ¯ˆ . o ınh a . e ¯ˆ o e a . . . ˜ ˜’ 30 canh, 20 d ınh; mˆ i mˇt l` mˆt ng˜ gi´c d` u, mˆ i d ınh l` d` u m´t cua 3 canh. C´c d ınh ¯˙ ’ o ¯˙ u˙ ’ a ¯˙’ o aao u a ¯ˆ e a ¯a ˆ . . . . v` c´c canh cua h` thˆp nhi diˆn d` u lˆp th`nh mˆt d` thi nhu. H` 5.6. B`i to´n d ˇt ˙ ınh a ’ aa . e ¯ˆ a e. a o ¯o . ˆ ınh a a ¯a . .. . . ˙ a d` thi G. ’ ¯ˆ . ra l` h˜y t` mˆt chu tr` Hamilton cu o a a ım o ınh . • • ....................................................................... ...................................................................... . .. . . .. . .. .. .. . . .. . .. .. .. . .. .. .. . . .. .. . . . .. . . .. . . .. . . . . .. . . .. . . .. . . . .. . . .. . . .. . . . . . .. . .. .. . . . . . . . .. .. . . .. .. . . . • • • . . .. . . . ................................................ . . . ................................................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . . . . . . . ....... . . . ........ . . . . . . . . .. . . . . . ... ... ... . ... . . . • • . . . . .. . . ... . ... . ... . ... . ... . . .... . ...... ... ... ... . . .. .. . . .... . . . . ....... ...... .... .. . ... ... . ... . .... . . . ... ..... • • . ... ..... ........ . . . . . . .... . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • . . . . . . . . . . ...... . . ...... . . ....... . . ....... . . . . . .. .. . . . . .... . . . . ... .... .... ... .... ... . . . . ... . . . . • • .. .. . . .... . . ... . .... .... . ... ... .... ......................... . ... . . . ......................... . . .... ... . .... ... .. . . .... .. . ....... . ... ... ...... . ... ... .... .. . ....... ... ... . ... ... .... ... ... • • • • ... ... . ..... ..... ..... ..... ... ... . ... . . .... . .... . .... ... ... ... ... ... .... .. .... . . .... ... .... ... ... ... .... ... .... ... . ... .. .. .... .... ... ... .... ... ... .... .... ... ... ...... .... ... ... .... .... • ... ... ... .... .... .... .. . .. .. .... .... .... . .... . .... . .... .... .... . .... . .... .... . .... . .... .... . .... . .... ... . .... .... . .... . .... .... . .... . . .. .... . .... .... . .... .... . .... . .... .... . .... . .... .... . .... . ...... .... . ...... . • ....... ....... .. H` 5.6: H`nh tr` xung quanh thˆ gi´.i (khˆi thˆp nhi diˆn d` u) cua Hamilton. ´ ´a ˙ ’ ınh a ınh eo o . e ¯ˆ e . . V´ du 5.3.3 (B`i to´n ngu.`.i ch`o h`ng). Mˆt ngu.`.i ch`o h`ng viˆng thˇm n kh´ch h`ng ´ ı. aa o aa o o aa e a a a . . th`nh phˆ v v` sau d o tro. vˆ vi tr´ xuˆ t ph´t. Anh ta biˆt ´ ´ ¯´ ˙ ` . ı a ´ ´ ’e v1 , v2 , . . . , vn , xuˆ t ph´t t` a a au o0a a e khoang c´ch d0j t`. v0 dˆn tˆ t ca c´c kh´ch h`ng vj v` khoang c´ch dij gi˜.a hai kh´ch h`ng ´´’ ˙ ’ ¯e a ˙ a ˙ ’ a u a a a a u a a vi v` vj (d ˇt dij = dji ). a ¯a . Ngu.`.i ch`o h`ng cˆn d i dˆn c´c kh´ch h`ng cua m` theo th´. tu. n`o dˆ’ tˆ’ng qu˜ng ˙˙ ` ¯ ¯e a´ ˙ ’ o aa a a a ınh u . a ¯e o a .`.ng d i l` nho nhˆ t? N´i c´ch kh´c cˆn t` mˆt chu tr` Hamilton v´.i d ˆ d`i nho nhˆ t ´ a ` ım o ´ ˙a ’ ˙a ’ du o ¯ ¯a oa a ınh o ¯o a . . .o.c xˆy du.ng t`. tˆp c´c d ınh v , v , v , . . . , v , v` trong trˆn d` thi d` y d u c´ trong sˆ d u . a ´ e ¯o . ¯ˆ ¯ ˙ o . ’ u a a ¯˙ ’ ˆ a o¯ a. . . 012 n .o.ng canh (v , v ) l` d . Vˆ c´c thuˆt to´n giai b`i to´n n`y c´ thˆ’ xem, chˇng han [30]. ˙ ˙ ’ `a ˙aaaoe ’ lu . a ij e a a a . . . ij Trong tru.`.ng ho.p d ınh cuˆi vn+1 kh´c d ınh xuˆ t ph´t v0 , b`i to´n d u.a vˆ t` dˆy ´ ´ ` ım a . ¯˙ ’ a ¯˙ ’ o o a a a a¯ e ` n Hamilton t`. v0 dˆn vn+1 c´ tˆ’ng d ˆ d`i nho nhˆ t. Bˇ ng c´ch biˆn d o’i mˆt c´ch ˙ ¯o a ˙oa ` ´ ´ ´ ¯ˆ ˙ ’ chuyˆe u ¯e oo a a a e . . th´ ho.p trˆn d` thi, ta c´ thˆ’ d u.a vˆ b`i to´n t` chu tr` Hamilton c´ tˆ’ng d ˆ d`i nho ˙ ˙ ` a a ım ˙ ’ ıch . e ¯o . ˆ o e¯ e ınh o o ¯o a . ´ nhˆ t. a http://www.ebook.edu.vn 136
V´ du 5.3.4 (B`i to´n lˆp lich). Trong mˆt sˆ b`i to´n lˆp lich, ta cˆn t` mˆt th´. tu. .´ ` ım o ı. a aa. ooa aa. a u. . . . .c hiˆn n tiˆn tr` cho tru.´.c (hai tiˆn tr` khˆng d u.o.c thu.c hiˆn c`ng mˆt l´c) v` thoa ´ ´ ˙ ’ thu e e ınh o e ınh o ¯ . eu ou a . . . . . .ng r`ng buˆc nhˆ t d inh; bˇ ng c´ch xˆy du.ng d` thi G trong d ´ tˆp c´c d ınh cua ` ´ ¯o a a ¯ ˙ ’ ˙’ m˜n nh˜ a u a o a ¯. a a a ¯o . ˆ . . . .o.ng u.ng v´.i tˆp c´c tiˆn tr` v` mˆt cung liˆn thuˆc hai d ınh v v` v nˆu tiˆn tr` ´ ´e ´ ˙ ’ G tu ´ oaa e ınh a o e o ¯ iaje ınh . . . i d u.o.c thu.c hiˆn tru.´.c tiˆn tr` j, b`i to´n d u.a vˆ t` mˆt d u.`.ng d i Hamilton trong G. ´ ` ım o ¯ o ¯. e oe ınh a a¯ e ¯ . . . V´ du 5.3.5 (Lˆp lich v` b`i to´n ngu.`.i ch`o h`ng trˆn d` thi c´ hu.´.ng). Trong thu.c tˆ ´ ı. a. aa a o aa e ¯o . o o ˆ .e . ta thu.`.ng lˆp kˆ hoach m` mˆ i cung (vi , vj ), biˆ’u diˆn mˆt r`ng buˆc n`o d o, gˇn v´.i mˆt ˙ ˜ ˜ ´ ´ o ae. ao e e oa o a ¯´ a o o . . . . sˆ thu.c tij l` khoang th`.i gian ´ nhˆ t c´ thˆ’ bˇt d` u thu.c hiˆn cˆng viˆc th´. j khi cˆng ˙´ a ´ ´ ˙ ’ o. a o ıt a o e a ¯ˆ eo e u o . . . viˆc th´. i d a tiˆn h`nh. ´ e u ¯˜ e a . Th`.i gian nho nhˆ t dˆ’ thu.c hiˆn tˆ t ca c´c tiˆn tr` d u.o.c x´c d inh bˇ ng c´ch t` ´˙ ` .´’ ´ ˙ ’ a ¯e . e a ˙a e o ınh ¯ . a ¯. a a ım .`.ng d i Hamilton c´ d ˆ d`i nho nhˆ t trˆn d` thi c´ hu.´.ng. Dˆy ch´ l` b`i to´n -a ´ e ¯o . o ˙’ mˆt d u o o¯ ¯ o ¯o a a ˆ o ınh a a a . . ngu.`.i ch`o h`ng trˆn d` thi c´ hu.´.ng. Vˆ thuˆt to´n giai b`i to´n n`y c´ thˆ’ xem, chˇng ˙ ˙ ’ ` ˙aaaoe ’ o aa e ¯o . o o ˆ e a a a . han [30]. . B`i to´n ngu.`.i ch`o h`ng trˆn d` thi vˆ hu.´.ng hoˇc c´ hu.´.ng thu.`.ng gˇp trong cuˆc aa o aa e ¯ˆ . o o o aoo o a o . . . sˆng v` c´ nhiˆu u.ng dung: lˆp th`.i kho´ biˆ’u, lˆp lich, lˇp d at hˆ thˆng d iˆn, tˆ’ng ho.p ˙ ˙ ´ ´ `´ ´ ¯e o ao e a o aea. a ¯ˇ e o o . . . .. . . c´c mach logic tuˆn tu., v.v. ` a a. . Ngo`i ra, nhiˆu b`i to´n c´ thˆ’ d u.a vˆ b`i to´n ngu.`.i ch`o h`ng: b`i to´n nhiˆu ngu.`.i ˙ ` a a o e¯ `a a ` a e e o aa aa e o .`.ng d i ngˇn nhˆ t v´.i d iˆu kiˆn qua tˆ t ca c´c d ınh (hay ´ a o ¯` ´ ´’ a ˙ a ¯˙ ’ ch`o h`ng, mˆt v`i b`i to´n t` d u o ¯ aa o a a a ım ¯ a e e . . ˙ a mˆt tˆp cho tru.´.c chı mˆt lˆn, c´c chu tr` (hay mach) Euler c´ chi ph´ nho ˙o` ’ ’.a ˙ ’ cung) cu oa o a ınh o ı .. . ´ nhˆ t. a Cuˆi c`ng, ta c´ thˆ’ chı ra rˇ ng, b`i to´n ngu.`.i ch`o h`ng trˆn d` thi c´ hu.´.ng c´ ˙’ ` ´ oe˙ ou a a a o aa e ¯o . o o ˆ o .a vˆ tru.`.ng ho.p d` thi vˆ hu.´.ng. ˙ du ` ’¯ thˆ e e o . ¯ˆ . o o o Tr´i v´.i b`i to´n ngu.`.i d u.a thu. Trung Hoa, ngoai tr`. nh˜.ng tru.`.ng ho.p d ˇc biˆt, aoa a o¯ u u o . ¯a e . . . .`.i ta chu.a t` d u.o.c mˆt thuˆt to´n d a th´.c dˆ’ giai b`i to´n ngu.`.i ch`o h`ng. C´c ˙˙a u ¯e ’ ngu o ım ¯ . o a a¯ a o aa a . . thuˆt to´n hiˆu qua nhˆ t su. dung c´c phu.o.ng ph´p nh´nh v` cˆn [30]. ´’ ˙ ’a˙. a a e a a a aa . . . Dinh ngh˜ 5.3.6 Mˆt chu tr` (tu.o.ng u.ng, mach) d i qua tˆ t ca c´c d ınh, mˆ i d ınh ´ -. ˜’ ´’ a ˙ a ¯˙ ’ o ¯˙ ıt ıa o ınh ´ ¯ . . ´t mˆt lˆn, goi l` chu tr` (tu.o.ng u.ng, mach) tiˆn Hamilton. D` thi G ch´.a mˆt chu -ˆ . ` ` nhˆa oa .a ınh ´ e o u o . . . tr` hay mach nhu. vˆy goi l` d` thi tiˆn Hamilton. Dˆ thˆ y rˇ ng, d iˆu kiˆn cˆn v` d u dˆ’ ’˙ ˜a` a . a ¯o . ` e´a ¯` e ` a ¯ ˙ ¯e ınh ˆ e e a . . . ` thi tiˆn Hamilton l` G liˆn thˆng (liˆn thˆng manh). ` G l` d o . e a ¯ˆ a e o e o . T` kiˆm mˆt chu tr` (hay mach) Hamilton c´ d o d`i nho nhˆ t trˆn d` thi c´ trong ´ ´ ˙ a e ¯o . o . ’ ım e o ınh o ¯ˆ a ˆ . . . .a vˆ b`i to´n x´c d inh chu tr` (hay mach) trong d` thi d` y d u G nhˆn d u.o.c tˆp sˆ d u ` a ´ ¯o . ¯a ¯ ˙ ’ o¯ e a a ¯. ınh ˆ ˆ a ¯. a . . . http://www.ebook.edu.vn 137
c´c d ınh cua G v` trong lu.o.ng trˆn canh (cung) (vi , vj ) cua G b` ng d ˆ d`i cua dˆy chuyˆn ` a ¯˙ ’ ˙’ ˙ ’ ˇ ¯o a ˙ a ’ a. e. a e . . .`.ng d i) ngˇn nhˆ t t`. v dˆn v trong G. ´ ´ ´ (d u o ¯ ¯ a a u i ¯e j Nhiˆu dang b`i to´n ngu.`.i ch`o h`ng ch´ l` c´c b`i to´n tiˆn Hamilton, v` dˆ’ giai˙’ ` ınh a a a a ` a ¯e ˙ e aa o aa e . ch´ng tru.´.c hˆt ta cˆn t` ma trˆn tu.o.ng u.ng c´c dˆy chuyˆn (d u.`.ng d i) ngˇn nhˆ t. ´ ´ ` ım ` ¯o ´ u oe a a ´ aa e ¯ a a . Cuˆi c`ng nhˆn x´t rˇ ng, tˆn tai mˆt tru.`.ng ho.p m` b`i to´n chu tr` tiˆn Hamilton ` ´ `.o ınh ` ou aea o o aa a e . . . ˙ d u.a vˆ b`i to´n ngu.`.i d u.a thu. Trung Hoa; d iˆu n`y xay ra khi ’¯ ´ `a a ¯` ˙ ’aoe ea˙ ’ c´ d o d`i nho nhˆ t c´ thˆ o ¯ˆ a e o¯ . G l` d` thi d ˆi ngˆ u1 cua d o.n d` thi vˆ hu.´.ng G∗ n`o d ´ v` khi d ˆ d`i cua c´c canh (vi , vj ) ˜ ´a ˙ ¯ ¯o . o o ’ ¯o a ˙ a . ’ a ¯ˆ . ¯o o ˆ a ¯o a . c´ dang ai + aj . Trong tru.`.ng ho.p n`y, b`i to´n t` chu tr` tiˆn Hamilton trong G ch´ ınh ` o. o a a a ım e ınh . .`.i d u.a thu. Trung Hoa trong G∗ v´.i d o d`i canh e∗ cua G∗ l` a . ˙ ’ l` b`i to´n ngu o ¯ aa a o ¯ˆ a . ai . i Nhˆn x´t tu.o.ng tu. cho b`i to´n t` mach tiˆn Hamilton c´ d ˆ d`i nho nhˆ t trong ` ´ ˙ ’ ae a a ım . e o ¯o a a . . . .`.ng ho.p d` thi c´ hu.´.ng G l` d` thi d ˆi ngˆ u cua d a d` thi c´ hu.´.ng n`o d ´. ˜ ˙ ¯ ¯o . o o ´ ’ tru o . ¯ˆ . o o o a ¯ˆ . ¯o o a ˆ a ¯o C´c d ` u kiˆn cˆn d e’ tˆn tai chu tr` Hamilton ˙o e ` ¯ˆ ` 5.3.1 a ¯iˆe a ınh . . Hiˆ’n nhiˆn rˇ ng, mˆt d iˆu kiˆn cˆn dˆ’ tˆn tai chu tr` Hamilton l` G 2-liˆn thˆng. Tuy ˙ ˙o ` o ¯` e ` ¯e ` . e ea e .a ınh a e o . ’ ¯` ˙ i d iˆu kiˆn d u. ˙ ’ nhiˆn, d ˆy khˆng pha e e ¯a o e¯ . H` 5.7 l` mˆt v´ du d` thi 2-liˆn thˆng khˆng ch´.a chu tr` Hamilton (ho.n n˜.a, ınh a o ı . ¯ˆ . o e o o u ınh u . ˙ chı ra rˇ ng, d ´ l` d` thi c´ sˆ d ınh ´ nhˆ t thoa m˜n t´ chˆ t n`y). ’˙ ` ´’ ´ ´ c´ thˆ ’ ¯o a ¯ˆ . o o ¯˙ ıt a ˙ a ınh a a ’ oe a o • .... ... ... ...... ... ...... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... . ... ... ... ... .. . ... ... ... ... ... .. ... . ... ... ... ... .. . ... ... ... ... ... .. ... . ... ... ... ... .. . ... ... ... ... ... ... .. . ... ... ... ... .. . ... ... ... ... ... ... .. . ... ... ... ... ... .. .. .......................................................................................................... ........................................................................................................... • • • .. ... ... . . . ... . ... .. ... . ... ... ... ... ... ... ... ... ... ... ... ... .. . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ...... ... ... ...... • ...... . -ˆ . H` 5.7: D` thi 2-liˆn thˆng c´ sˆ d ınh ´ nhˆ t khˆng c´ chu tr` Hamilton. ´’ ´ o o ¯˙ ıt a ınh o e o o o ınh D` thi vˆ hu.´.ng Petersen (H` 5.8) l` v´ du kh´c khˆng c´ chu tr` Hamilton. Dˆy -ˆ . o o -a o ınh aı. a o o ınh l` d` thi ch´ quy 3-liˆn thˆng nho nhˆ t c´ tˆ t ca c´c d ınh bˆc ba. Nhiˆu phan v´ du vˆ ´ ´’ ` ’ ı.` ˙ ’ a o a ˙ a ¯˙ ’ ˙ a ¯ˆ . ınh o e o a e e . .o.c xˆy du.ng t`. d` thi Petersen. b`i to´n Hamilton d u . a aa ¯ u ¯ˆ . o . Dˆ thi vˆ hu.´.ng G∗ l` d` thi d ˆi ngˆ u cua G = (V, E ) nˆu mˆ i d ınh cua G∗ tu.o.ng u.ng v´.i mˆt canh 1- ` ˜ ˜’ ´ ´ ˙ ’ o ¯˙ ˙ ’ o .o o a ¯ˆ . ¯o o a e ´ o o. . e ∈ E v` hai d ınh trong G∗ kˆ nhau nˆu hai canh tu.o.ng u.ng kˆ nhau. D` thi c´ hu.´.ng G∗ l` d` thi d ˆi -ˆ . o ` ´ ` ´ ¯˙ ’ a e e ´ e o o a ¯ˆ . ¯o o . ngˆ u cua G = (V, E ) nˆu mˆ i d ınh e∗ cua G∗ tu.o.ng u.ng v´.i mˆt cung e ∈ E v` tˆn tai cung (e∗ , e∗ ) trong ˜ ˜’ ´ a` . ˙ ’ o ¯˙ ˙ ’ a e ´ o o o . 12 G∗ nˆu d ınh ngon cua cung e1 l` d ınh gˆc cua cung e2 . ´’ ´’ e ¯˙ ˙ ’ a ¯˙’ o˙ . http://www.ebook.edu.vn 138
• .... ... ... . ... ... . ... ... . ...... ... . ...... . ... . ... . ... ... ... . ... . ... . ... ... ... . ... . ... .. . . ... . ... ... ... . .. . . ... ... ... . ... ... . ... .. . . ... ... . ... ... . .. . . ... ... ... ... . . ... ... .. . . ... . ... ... ... . . .. . ... . ... ... ... . ... . • ... .. . . ... ... ... . ... .. .. ... . ... ... ... . ... . .. ... ... .. . . .. ... . ... ... ... .. .. . ... ... . .. .. ... • • ... .. .. .. ... . ... . ...... . .. . ........ . ..... . . ..... . . . .. ....... . ..... ... . .. ........ ..... .. . . . . ... ..... .. . ..... . . ..... ..... .. . . . ..... .. . . . . • • ....................................................................... ..................................... ......................... . . .. .. . .. . .. . .... .... .... ... . .. . .. . . . .. .... .... . .... .... . . .. . . . . ...... .. .... .... . . .. . ..... .. . . .... . .... . . .. .. .... .. .... .. .. .... .... . .. .. .. .. . .... . .. .. .... .. . .. . ..... . .... .. .... ...... . .... ...... .. . .. . . . . . .. . .... .. ......... . .. . . . . .... ...... . . .. .... . .. .. . . ...... . . .... . . .... . .. .. . .. .... . .. . ... . . .... . . ... ...... .. . .... .. ..... ...... .. .. ... • • ... ... ... .. . .. .. . .. .. .. .. .. . .. . .. .. .. .. .. . . .. .. .. . .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .... .. • • ... ....................................................... ...................................................... . -ˆ . H` 5.8: D` thi Petersen. ınh o C´ nhiˆu d iˆu kiˆn cˆn kh´c (xem [30], [14]) nhu.ng khˆng c´ mˆt d iˆu kiˆn cˆn v` d u o ` ¯` e` o o ¯` e ` a ¯˙ ’ e e .a a o e .a . . tˆn tai chu tr` (mach) Hamiton. vˆ su ` . `.o e ınh . Do d o ch´ng ta s˜ tˆp trung mˆt sˆ d iˆu kiˆn d u dˆn dˆn c´c phu.o.ng ph´p c´ t´ ’˜ o o ¯` .´e ´ e ¯ ˙ a ¯e a ¯´ u ea a o ınh . . .ng chu tr` Hamilton. xˆy du a ınh . C´c d ` u kiˆn d ˙ vˆ su. tˆn tai chu tr` Hamilton e ¯u ` . ` ’e 5.3.2 a ¯iˆe o ınh . . Mˆnh d` 5.3.7 Kn l` d` thi Hamilton. e ¯ˆ e a ¯ˆ . o . Ch´.ng minh. Hiˆ’n nhiˆn. ˙ u e e X´t d` thi vˆ hu.´.ng n d ınh G := (V, E ). Gia su. s v` t l` hai d ınh khˆng kˆ nhau sao ` ¯˙’ ˙˙ ’’ ¯˙’ e ¯o . o o ˆ aa o e cho dG (s) + dG (t) ≥ n. K´ hiˆu G + (s, t) l` d` thi nhˆn d u.o.c t`. G bˇ ng c´ch thˆm canh (s, t). Khi d o ` ye a ¯ˆ . a ¯ . u o a a e ¯´ . . . Mˆnh d` 5.3.8 Nˆu G + (s, t) l` d` thi Hamilton th` G l` d` thi Hamilton. Ta n´i t´nh ´ e ¯ˆe e a ¯ˆ . o ı a ¯ˆ . o oı . chˆ t n`y l` ˆ’n d. nh Hamilton qua ph´p biˆn d ˆ’i G → G + (s, t). ˙ ˙ ´ ´ a a a o ¯i e e ¯o Ch´.ng minh. Gia su. G + (s, t) ch´.a chu tr` Hamilton µ := (v1 , v2 , . . . , vn ). Nˆu µ khˆng ´ ˙˙ ’’ u u ınh e o .o.c lai, G ch´.a mˆt dˆy chuyˆn Hamilton µ \ (s, t) ` d i qua canh (s, t) th` G l` Hamilton. Ngu . . ¯ ı a u oa e . . nˆi s v` t. (Khˆng mˆ t t´ tˆ’ng qu´t, c´ thˆ’ gia thiˆt s = v1 , t = vn ). ˙ ˙’ ´ ´ ´ aoe˙ o a o a ınh o e http://www.ebook.edu.vn 139
Ta ch´.ng minh rˇ ng tˆn tai ´ nhˆ t mˆt chı sˆ i, 3 ≤ i ≤ n, sao cho s kˆ v´.i vi v` t kˆ ` ` . ıt a ´o ’´ `o a` ˙o u a o e e . .i v . v´ i−1 o ˙a ’. Thˆt vˆy, x´t c´c tˆp con cua tˆp Y := {v3 , v4 , . . . , vn−1 } : aa eaa .. . A = {vi | (s, vi ) ∈ E v` 3 ≤ i ≤ n − 1}, a B = {vi | (t, vi−1 ) ∈ E v` 3 ≤ i ≤ n − 1}. a ` V` s v` t khˆng kˆ nhau trong G nˆn ı a o e e #A + #B = dG (s) + dG (t) − 2 ≥ n − 2 aae` `. v` nhˆn x´t rˇ ng #Y = n − 3 suy ra tˆn tai a o . vi ∈ A ∩ B (3 ≤ i ≤ n − 1). Do d ´, thˆm c´c canh (s, vi ) v` (t, vi−1 ) v` xo´ canh (vi , vi−1 ) ta d u.o.c mˆt chu tr` Hamilton ¯o e a . a a a. ¯. o ınh . .o.c ch´.ng minh. trong G (xem H` 5.9), v` mˆnh d` d u . ınh ae ¯ˆ ¯ e u . v2 v3 v2 v3 • • • • ........................ ....................... ........................ ....................... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . .. .. ... ... ... ... ... ... .. .. ... ... ... ... ... ... ... ... . . ... ... ... ... ... ... ... ... s = v1 • v1 • • • ... ... .. ... ... ... ... ... . . ... ... . . .. .. .. . . . . . . ... . ... . . . . ... . ... ... ... . . . . −→ . ... . . ... . . . . ... ... . ... ... . . . . . ... . ... . . . . ... ... . ... . ... . . • vi−1 • vi−1 . . ... . t = vn • t = vn • ... . . . .. ..................................... .... ... ... ..... ... ... ... ... .... .................. ..................................... .... .... .... ...... .... .... .... .... .... . . .. .................. .. .. . .. .. ... ... . ... ... ... ... . . ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... . ... . . . .. .. ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... . ... ... ... ... ... ... .... ... ... ... ... ... ... ... ... . ... ... .. ........................ ........................ • • • • ................. ..... ....................... . .. vi vi H` 5.9: ınh Gia su. G l` d o.n d` thi n d ınh v` k l` sˆ nguyˆn thoa 1 ≤ k ≤ n. X´t thu tuc dˆ ´ ˙˙ ’’ ¯ˆ . ¯˙ ’ ˙ ’ ˙ . ¯e ’ a¯ o a ao e e . . G, thˆm c´c canh nˆi c´c d ınh khˆng kˆ nhau m` tˆ’ng c´c bˆc cua ˙ ´ ´ ` o a ¯˙ ’ aa˙ ’ quy sau: Xuˆ t ph´t t` a au e a. o e ao . ch´ng l´.n ho.n hoˇc bˇ ng k. (Sˆ ph´p to´n d `i hoi trong thu tuc n`y tı lˆ v´.i n4 ). V` c´c a` ´ a ¯o ˙ ’ ˙ . a ˙e o ’ ’. u o .a oe ıa bˆc khˆng giam, d` thi nhˆn d u.o.c khˆng phu thuˆc v`o th´. tu. c´c canh d u.o.c thˆm. D` -ˆ ˙ ’ a o ¯o . a ¯ . ˆ o oa u.a . ¯. e o . . . . .a G) goi l` k −bao d ong cua G v` k´ hiˆu l` [G] . V´.i k = n, t`. Mˆnh d` 5.3.8 ˙ ’ thi n`y (ch´ .a u .a ¯´ ay e a o u e ¯ˆ e . . k suy ra -. Dinh l´ 5.3.9 [8] G l` d` thi Hamilton nˆu v` chı’ nˆu [G]n l` d` thi Hamilton. ´ ´ e a ˙e y a ¯ˆ . o a ¯ˆ . o Trong tru.`.ng ho.p tˆ’ng qu´t, t` chu tr` Hamilton trong [G]n khˆng phai l´c n`o ˙ ˙u a ’ o .o a ım ınh o .n trong G. Tuy nhiˆn, v´.i nh˜.ng tru.`.ng ho.p d ac biˆt, chˇng han khi [G] l` d` ˜ ˙ ’ c˜ng dˆ ho u e e o u o ¯ˇ e a n a ¯ˆ o . . . . ˙ dˆ d`ng xˆy du.ng chu tr` Hamilton trong [G]n : ’˜a thi d` y d u Kn ta c´ thˆ e . ¯a ¯ ˙ ’ ˆ oe a ınh . http://www.ebook.edu.vn 140
-. -` Dinh l´ 5.3.10 Diˆu kiˆn d u dˆ’ G l` d` thi Hamilton l` [G]n = Kn . ’˙ e ¯ ˙ ¯e y e a ¯ˆ . o a . C´ thˆ’ chı ra rˇ ng hˆu hˆt c´c d iˆu kiˆn d u d ˜ biˆt (d u.o.c liˆt kˆ du.´.i d ay) liˆn quan ˙’ ` ` a e a ¯` ´ ´ oe˙ e ¯ ˙ ¯a e ¯ . e e o ¯ˆ ’ a e e . . ˙ ˙ -. ´n bˆc cua G suy ra [G]n = Kn v` do d ´ l` c´c hˆ qua cua Dinh l´ 5.3.10. ˙ ’ ’’ dˆ a ¯e a ¯o a a e y . . Gia su. G l` d o.n d` thi liˆn thˆng n d ınh. ˙˙ ’’ ¯˙’ a¯ ¯ˆ . e o o Hˆ qua 5.3.11 [Ore] [47] Nˆu dG (vi ) + dG (vj ) ≥ n v´.i moi (vi , vj ) ∈ E th` G l` d` thi ´ ˙’ e e o / ı a ¯o . ˆ . . Hamilton. v´.i moi d ı’nh vi ∈ V th` G l` d` thi Hamilton. n ´ ˙ ’ . ¯˙ Hˆ qua 5.3.12 [Dirac] [17] Nˆu dG (vi ) ≥ e e o ı a ¯ˆ . o . 2 Hˆ qua 5.3.13 [P´sa] [51] Nˆu c´c d ı’nh cu a G d u.o.c d ´nh sˆ thu. tu. sao cho ´ ´ ˙ ’ e a ¯˙ ˙ ’ e o ¯ . ¯a o.. . dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ) ´ v` nˆu ae n ∀k : 1 ≤ k < ⇒ dG (vk ) > k, 2 th` G l` d` thi Hamilton. ı a ¯ˆ . o Hˆ qua 5.3.14 [Bondy] [7] Gia su. c´c d ı’nh cu a G d u.o.c d ´nh sˆ thu. tu. sao cho ´ ˙ ’ ˙ ˙ a ¯˙ ’’ ˙ ’ e ¯ . ¯a o.. . dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ). e ¯` ´ Nˆu d iˆu kiˆn sau d ung: e e ¯´ . p < q, dG (vp ) ≤ p, dG (vq ) ≤ q − 1 ⇒ dG (vp ) + dG (vq ) ≥ n, th` G l` d` thi Hamilton. ı a ¯ˆ . o Hˆ qua 5.3.15 [Chv´tal] [13] Nˆu c´c d ı’nh cu a G d u.o.c d ´nh sˆ thu. tu. sao cho ´ ´ ˙ ’ e a ¯˙ ˙ ’ e a ¯ . ¯a o.. . dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ) ´ v` nˆu ae n dG (vk ) ≤ k < ⇒ dG (vn−k ) ≥ n − k 2 th` G l` d` thi Hamilton. ı a ¯ˆ . o http://www.ebook.edu.vn 141
Hˆ qua 5.3.16 [Las Vergnas] [42] [30] Nˆu c´c d ı’nh cu a G d u.o.c d ´nh sˆ thu. tu. v1 , v2 , . . . , vn ´ ´ ˙ ’ e a ¯˙ ˙ ’ e ¯ . ¯a o .. . sao cho  j < k, k ≥ n − j   (vj , vk ) ∈ E / ⇒ dG (vj ) + dG (vk ) ≥ n   dG (vj ) ≤ j, dG (vk ) ≤ k − 1 th` G l` d` thi Hamilton. ı a ¯ˆ . o C´c ch´.ng minh. Ch´.ng minh cua Hˆ qua 5.3.11 suy tru.c tiˆp t`. c´ch xˆy du.ng [G]n : tˆ t ´ ´ ˙ ’ ˙ ’ a u u e e ua a a . . . ca c´c canh (vi , vj ) ∈ E c´ thˆ’ d u.o.c thˆm v` do d ´ ta c´ [G]n = Kn . Hˆ qua 5.3.12 suy tru.c ˙ ˙a . ’ e˙ ’ / o e¯ . e a ¯o o . . tiˆp t`. Hˆ qua 5.3.11. ´ ˙ ’ eue . Ho.n n˜.a, dˆ d`ng thˆ y rˇ ng, d` thi thoa m˜n c´c d iˆu kiˆn cua Hˆ qua 5.3.13, 5.3.14 ˜a a` ´a ˙ a a ¯` ’ e˙ ’ ˙ ’ u e ¯ˆ . o e e . . ´’ ˙aa ’ ˙ ’ e˙ ˙ ’ hay 5.3.15 c˜ng thoa m˜n c´c gia thiˆt cua Hˆ qua 5.3.16. u e . Dˆ’ ch´.ng minh Hˆ qua 5.3.16, ta s˜ su. dung kˆt qua sau cho d iˆu kiˆn d u dˆ’ [G]n = Kn . -e u ˙ ’˙ ´ ¯` e˙ ’ e˙ .’ ˙ ’ e ¯ ˙ ¯e e e . . Dinh l´ 5.3.17 [8] Nˆu c´c d ı’nh cu a G d u.o.c d ´nh sˆ thu. tu. v1 , v2 , . . . , vn sao cho -. ´ ´ e a ¯˙ ˙ ’ y ¯ . ¯a o..  i
•.... .. . ..... ..... ..... ..... .... . .. ....... .... . ... ....... .... ... .... ... .... .. .... . .. .... .. .... .... .... .... .. .. . .. .... .... ... ... .. .. .. .... .... .... .... .. .. .... .... .... .... .. .. .. .... .. .... . .. .... .... .. .. .... .. .... .. . .. .... .... .. .... .. .... .. .. . • .... • .. .... .... .... .. .. .. .. . . .. . . .. .. . .. . . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. . .. . .. . . . .. . . .. .. . .. . . . .. . .. .. . . .. . . . .. . .. .. . . .. . . . .. . . ... .. . . .. .. . . . .. . . .. . . .. .. . . .. . .. . . . .. ... . .. . .. . . ... • • . . . .. .. . .... ... . .. . . .... .... .... .... .. . .... .... .... .... .... .... .. . .... .... .... .... ... . .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....... .... ....... •.... ... H` 5.10: V´.i d` thi n`y, [G]6 = K6 nhu.ng khˆng thˆ’ ´p dung Hˆ qua 5.3.16. ˙ ˙ ’ ınh o ¯ˆ . a o o ea e . . Dinh l´ 5.3.18 [Meyniel, 1973] Gia su. G = (V, E ) l` d` thi c´ hu.´.ng n d ı’nh liˆn thˆng -. ˙˙ ’’ ¯˙ y a ¯ˆ . o o o e o manh khˆng khuyˆn sao cho o e . (vi , vj ) ∈ E v` (vj , vi ) ∈ E ⇒ dG (vi ) + dG (vj ) ≥ 2n − 1. / a / Khi d ´ G ch´.a mˆt mach Hamilton. ¯o u o . . Ch´ng ta s˜ d u.a ra ch´.ng minh c´ t´ kiˆn thiˆt d .nh l´ n`y (theo Minoux, 1977) ´ ´ u e¯ u o ınh e e ¯i ya .c tap O(n4 ) dˆ’ t` mach Hamilton. Ch´.ng minh du.a trˆn ˙ ım . v` mˆt thuˆt to´n c´ d o ph´ . ao a a o ¯ˆ u ¯e u e . . . . phu.o.ng ph´p (khˆng kiˆn thiˆt) cua Bondy v` Thmassen (1977). Tru.´.c hˆt, ch´ng ta cˆn ´ ´ ´ ` ˙ ’ a o e e a oe u a .´ mˆt sˆ kh´i niˆm. ooae . Gia su. S ⊂ V. V´.i mˆi vi ∈ V (c´ thˆ’ vi ∈ S ), k´ hiˆu δS (i) l` sˆ c´c cung nˆi (theo ˙ ˜ ´ ´ ˙˙ ’’ o o oe ye aoa o . .´.ng bˆ t k`) d ınh v v´.i tˆp con S. V` G khˆng c´ khuyˆn nˆn ta luˆn luˆn c´ ´ a y ¯˙ ’ hu o io a ı o o ee o oo . vi ∈ S ⇒ δS (i) ≤ 2#S − 2. V´.i S l` tˆp con thu.c su. cua V ta goi S −bˆ h`nh l` mˆt d u.`.ng d i m` c´c d ınh d` u v` .˙ ’ ¯ a a ¯˙ ’ o aa oa a o ¯o ¯ˆ a a . . . . . ´ ´ ´ a a ¯˙ ’ cuˆi (khˆng nhˆ t thiˆt phˆn biˆt) thuˆc S v` c´c d ınh trung gian l` phˆn biˆt v` tao th`nh o o a e a e o aa e a. a . . . ´ng cua tˆp V \ S. Mˆt S −d u.`.ng d i l` mˆt S −bˆ h`nh m` c´c d iˆ’m˙ ˙a ’. mˆt tˆp con kh´c trˆ oa a o o ¯o ¯a o oa a a ¯e .. . . . d` u v` cuˆi kh´c nhau. ´ ¯a a o ˆ a Ta c´ bˆ’ d` sau: ˙e o o ¯ˆ Bˆ’ d` 5.3.19 Gia su. µ = (v0 , v1 , . . . , vp ) l` d u.`.ng d i so. cˆ p cu a G, S l` tˆp c´c d ı’nh cu a ˙e ´’ ˙˙ ’’ a˙ a a a ¯˙ ˙ ’ o ¯ˆ a¯ o ¯ . ´u khˆng tˆn tai hai d ı’nh liˆn tiˆp vk v` vk+1 (0 ≤ k ≤ p − 1) cu a µ `. ´ ˙ ˙ ’ n´ v` d ˇt v ∈ V \ S. Nˆ o a ¯a e o o ¯ e e a . sao cho (vk , v ) ∈ E v` (v, vk+1 ) ∈ E th` a ı δS (v ) ≤ #S + 1. http://www.ebook.edu.vn 143
Ch´.ng minh. X´t c´c tˆp con cua S \ {vp } : ˙ ’ u eaa . A := {vi ∈ S \ {vp } | (vi , v ) ∈ E } v` a A := {vi ∈ S \ {vp } | (v, vi+1 ) ∈ E }. ´ ˙ ’ Theo gia thiˆt, A ∩ B = ∅ v` #(A ∪ B ) ≤ #S − 1 (do vp ∈ A, vp ∈ B ). Vˆy e a / / a . δS (v ) ≤ #A + #B + 2 = #(A ∪ B ) − #(A ∩ B ) + 2 ≤ #S + 1, d iˆu phai ch´.ng minh. ¯` ˙ ’ e u Bˆy gi`. ch´ng ta ch´.ng minh Dinh l´ 5.3.18. -. a ou u y Ch´.ng minh cua D. nh l´ 5.3.18. X´t d` thi G thoa m˜n c´c d iˆu kiˆn cua d .nh l´. ˙ -i ˙ a a ¯` ’ ’ e ˙ ¯i ’ u y e ¯o . ˆ e y . e`. ´ (1) V` G liˆn thˆng manh nˆn tˆn tai mˆt mach d ˆ d`i ´ nhˆ t hai. ı e o o o . ¯o a ıt a . . . Ta n´i mach µ trong G l` tu.a cu.c d ai nˆu v´.i moi d ınh v ∈ µ khˆng tˆn tai hai d ınh ´ `. . ¯˙ ’ ¯˙’ o a. . ¯. e o / o o . ´ vk v` vk+1 liˆn tiˆp trˆn mach µ sao cho a e e e . (vk , v ) ∈ U v` (vk+1 , v ) ∈ U. a Hiˆ’n nhiˆn rˇ ng dˆ’ kiˆ’m tra mˆt mach c´ phai tu.a cu.c d ai hay khˆng, hoˇc dˆ’ ph´t ˙ ˙˙ ˙ e` ˙. ’ e a ¯e e o o . ¯. o a ¯e a . . . .n ho.n 1 ta cˆn thu.c hiˆn O(n2 ) ph´p to´n so. cˆ p. ` ´ hiˆn mˆt mach d ˆ d`i l´ e o . ¯o a o a e e a a . . . . . Do d o, thuˆt to´n xˆy du.ng mˆt mach tu.a cu.c d ai trong G bˇt d` u t`. mˆt mach tu` ´ˆ ¯´ a aa o . ¯. a ¯a u o y . . . . . . . . cˆ p. ´ 3 ´ ¯o ˙ ’ y d `i hoi O(n ) ph´p to´n so a e a Gia su. µ l` mach tu.a cu.c d ai, v` k´ hiˆu S l` tˆp c´c d ınh cua n´. Nˆu S = V ta ´ ˙˙ ’’ a a a ¯˙ ’ ˙ ’o a. . ¯. ay e e . . . .ng: µ l` mach Hamilton. Ngu.o.c lai, ta s˜ chı ra rˇ ng c´ thˆ’ mo. rˆng mach µ dˆ’ nhˆn ˙ ’. ˙ ` e˙ ’ o e ˙o d` u a. a ¯e a .. . . .o.c mˆt mach µ c´ d ˆ d`i l´.n ho.n, v` do d o, theo quy nap, ta s˜ c´ mˆt mach Hamilton. du . ¯ o o ¯o a o a ¯´ eo o . . . . . . (2) Ch´ng ta ch´.ng minh tˆn tai mˆt S −d u.`.ng d i trong G. `. u u o o ¯o ¯ . Bˇ ng phan ch´.ng, gia su. khˆng tˆn tai S −d u.`.ng d i. V` G liˆn thˆng manh, tˆn tai ` `. `. ˙ ’ ˙˙ ’’ a u o o ¯o ¯ ı e o o . ´t mˆt S −bˆ h`nh P m` c´c d ınh d` u cuˆi cua n´ l` v ∈ S. ´ ˙ oa ˙ ¯a ’ ’ ´ nhˆ ıt a o oa aa¯ ˆ o . . -a a a a ¯˙ ’ a a a ¯˙ ’ ˙ ’ Dˇt R l` tˆp c´c d ınh thuˆc P v` kh´c v ; d at T l` tˆp c´c d ınh cua G khˆng thuˆc o aa ¯ˇ o o . . . . . . S ∪ R. Theo gia thiˆt khˆng tˆn tai S −d u.`.ng d i nˆn khˆng tˆn tai d ınh thuˆc R v` kˆ v´.i ´ `. ` . ¯˙ a` o ˙’ ’ e o o ¯o ¯e o o o e . o ¯˙ .’ mˆt d ınh trong S \ {v }. http://www.ebook.edu.vn 144
Do d o v´.i mˆ i d ınh vi ∈ R v` d ınh vj ∈ S \ {v } ta c´ ˜’ ¯´ o o ¯˙ a ¯˙’ o δR (vi ) ≤ 2#R − 2, δR (vj ) = 0, δS (vi ) ≤ 2, δS (vj ) ≤ 2#S − 2. Ho.n n˜.a ta cˆn c´ `o u a δT (vi ) + δT (vj ) ≤ 2#T. (Nˆu khˆng, tˆn tai ´ nhˆ t mˆt d u.`.ng d i d o d`i 2 hoˇc gi˜.a vi v` vj , hoˇc gi˜.a vj v` vi ; ´ ` . ıt a ´ o ¯o e o o ¯ ¯ˆ a a u a a u a . . . . .`.ng d i n`y (c´ mˆt phˆn nˇ m trˆn P ) tao th`nh mˆt S −d u.`.ng d i). ` ` du o ¯ ¯a oo aa e a o ¯o ¯ . . . C´ thˆ’ ch´.ng minh rˇ ng c´c d ınh vi v` vj l` hai d ınh khˆng kˆ nhau sao cho ˙ ` ` a ¯˙ ’ ¯˙’ oeu a a a o e δ (vi ) + δ (vj ) = δS (vi ) + δR (vi ) + δT (vi ) + δS (vj ) + δR (vj ) + δT (vj ) ≤ 2(#R + #S + #T ) − 2 = 2n − 2, mˆu thuˆn v´.i gia thiˆt. ˜ ´ ˙ ’ a ao e (3) V` tˆn tai ´ nhˆ t mˆt S −d u.`.ng d i, ta s˜ t` mˆt S −d u.`.ng d i P xuˆ t ph´t t`. x v` kˆt ı ` . ıt a ´o ´ ´ o ¯o ¯ e ım o ¯o ¯ a au ae . . .`.ng d i con µ(x, y ) t`. x dˆn y trˆn µ l` nho nhˆ t (theo sˆ ´ ´ ´ ¯ˆ a ˙ ¯ ’ ˙ ’a th´c tai y sao cho d o d`i cua d u o u. ¯ u ¯e e a o . c´c cung). a V´.i mˆt d ınh x ∈ S cho tru.´.c, ch´ng ta c´ thˆ’ su. dung thuˆt to´n t` kiˆm theo ˙’ ´ o ¯˙ ’ o e˙. o o u a a ım e . . . d a tr` b`y trong Chu.o.ng 3. Phu.o.ng ph´p n`y d `i hoi O(m) chiˆu rˆng trˆn d` thi G nhu ¯˜ ınh a `o a a ¯o ˙ ’ e. e ¯ˆ .o . cˆ p. Do d ´ thuˆt to´n t` mˆt S −d u.`.ng d i P v´.i t´ chˆ t d oi hoi cˆn nhiˆu ´ ´ ¯` ˙ ` ` ’a ph´p to´n so a e a ¯o a a ım o ¯o ¯ o ınh a e . . . cˆ p. ´ ´ nhˆ t O(mn) ph´p to´n so a a e a a a a ¯˙’ ˙ ’ a a a ¯˙ ’ K´ hiˆu R l` tˆp c´c d ınh trung gian cua P, v` S1 l` tˆp c´c d ınh trung gian trˆn ye a e . . . d u.`.ng d i µ(x, y ) cua µ. ˙ ’ ¯o ¯ Nˆu S1 = ∅ th` thay cung (x, y ) bo.i S −d u.`.ng d i P v` ch´ng ta nhˆn d u.o.c mˆt mach ´ ˙ ’ e ı ¯o ¯ au a¯. o . . . .n ho.n hoˇc bˇ ng (#S + 1). ` µ c´ d o d`i l´ o ¯ˆ a o aa . . (4) Kˆ tiˆp ta gia su. S1 = ∅, v` d at S2 := S \ S1 v` T l` tˆp c´c d ınh cua G khˆng thuˆc ´´ ˙˙ ’’ a a a ¯˙ ’ ˙ ’ ee a ¯ˇ a o o . . . R v` S. a Ch´ng ta xˆy du.ng mˆt d u.`.ng d i so. cˆ p tu.a cu.c d ai Q gi˜.a y v` x m` tˆp c´c d ınh ´ a a a ¯˙ ’ u a o ¯o ¯ a. . ¯. u a . . . .o.ng ph´p lˇp nhu. sau: ` ˙ oa ’ ˙a ’ cua n´ l` S thoa m˜n S ⊂ S v` S2 ⊂ S bˇ ng phu a a aa . 1. Kho.i tao v´.i Q := µ(x, y ), S := S2 , S := S1 . ˙.o ’ 2. T` d ınh s ∈ S sao cho (k, s) ∈ U v` (s, l) ∈ U v´.i hai d ınh k v` l liˆn tiˆp trˆn Q. ´ ım ¯˙ ’ ¯˙ ’ a o a e e e ` ng, d iˆu n`y d `i hoi nhiˆu nhˆ t O(n) ph´p to´n so. cˆ p). Nˆu khˆng tˆn ` ` ´ ´ ´ ` ¯ e a ¯o ˙ ’ (Nhˆn x´t rˇ aea e a e a a e o o . . vˆy (hoˇc l` S = ∅) th` d`.ng: d u.`.ng d i Q l` tu.a cu.c d ai (hoˇc cu.c ¯˙’ tai d ınh s nhu a aa ıu ¯o ¯ a. ¯. a. . . . . . d ai). ¯. http://www.ebook.edu.vn 145
3. Gia su. tˆn tai d ınh s th` ch`n n´ v`o gi˜.a hai d ınh k v` l dˆ’ nhˆn d u.o.c mˆt d u.`.ng ˙ ˙ ˙ ` . ¯˙ ’’o ’ ¯˙’ ı e oa u a ¯e a ¯ . o ¯o . . .i Q c´ d o d`i l´.n ho.n d u.`.ng d i tru.´.c d o mˆt. Thay S bo.i S ∪ {s}, S bo.i ˙ ’ ˙ ’ d i m´ ¯o o ¯ˆ a o ¯o ¯ o ¯´ o . . .i Q v` lˇp lai Bu.´.c 2. ˙ ’ S \ {s}, Q bo aa . o . Ch´ y rˇ ng, sˆ ph´p to´n cˆn thu.c hiˆn trong thuˆt to´n n`y khˆng vu.o.t qu´ O(n3 ). u´ ` ´ a` a oe a e a aa o a . . . . ` ´ e˙ ’ Ta s˜ chı ra rˇ ng, kˆt th´c thuˆt to´n th` S = ∅. a e u a a ı . Thˆt vˆy, gia su. ngu.o.c lai S = ∅. ˙˙ ’’ aa .. .. Theo c´ch xˆy du.ng cua P, c´c d ınh cua R khˆng kˆ v´.i mˆt d ınh cua S1 (v` nˆu `o ´ ˙ ’ a ¯˙ ’ ˙ ’ o ¯˙ ’ ˙ ’ a a o e ıe . . .o.c lai, ta c´ thˆ’ t` mˆt S −d u.`.ng d i m` c´c d ınh d` u cuˆi cua n´ gˆn µ ho.n P ). Do ˙ ım o ´ ˙ o` ˙ ’ ¯ˆ ’ ngu . . oe ¯o ¯ aa¯ a o a . d o, v´.i moi d ınh vi ∈ R v` moi d ınh vj ∈ S1 ta c´ ¯˙’ a . ¯˙ ’ ¯´ o o . δR (vj ) = δS1 (vi ) = 0. Mˇt kh´c, v` µ l` mach tu.a cu.c d ai, d ınh vi thoa m˜n c´c gia thiˆt cua Bˆ’ d` 5.3.19 v´.i ˙e ´’ . ¯ . ¯˙ ’ ˙aa ’ ˙’ e˙ a a ı a. o ¯ˆ o . . .`.ng d i con µ(x, y ) sao cho du o ¯ ¯ δS2 (vi ) ≤ #S2 + 1. Chon vj ∈ S ⊂ S1 . Theo c´ch xˆy du.ng cua Q, ´p dung lai Bˆ’ d` 5.3.19 v´.i d ınh vj v` ˙e ˙ ’ o ¯˙’ a a a . o ¯ˆ a . . . .`.ng d i Q, ta d u.o.c du o ¯ ¯ ¯. δS (vj ) ≤ #S + 1. Mˇt kh´c, ta cˆn c´ (nhu. d ˜ ch´.ng minh trong Phˆn (2)) `o ` a a a ¯a u a . δT (vi ) + δT (vj ) ≤ 2#T (ngu.o.c lai, ta c´ thˆ’ t` mˆt S −d u.`.ng d i m` c´c d ınh d` u cuˆi cua n´ gˆn µ ho.n P ). ˙ o ˙ o` ´’ ¯ a a ¯˙ ¯ˆ ’ o e ım o ¯o a a .. . ´ Cuˆi c`ng, ta luˆn luˆn c´ ou o oo δS (vj ) ≤ 2#S − 2, v` δR (vi ) ≤ 2#R − 2. a Suy ra δ (vi ) + δ (vj ) ≤ 2#R + #S2 + 2#S + #S − 2 v` a #S2 ≤ #S ⇒ δ (vi ) + δ (vj ) ≤ 2n − 2 .i hai d ınh khˆng kˆ nhau v v` v , mˆu thuˆn v´.i gia thiˆt. ˜ ` ´ ¯˙’ ˙ ’ v´ o o e iaj a ao e Vˆy S = ∅ v` t`. d u.`.ng d i Q v´.i S −d u.`.ng d i P ta c´ thˆ’ xˆy du.ng mˆt mach µ c´ ˙ a a u¯o ¯ o ¯o ¯ o ea o o . . . . d o d`i ≥ #S + 1. ¯ˆ a . (5) Trong tˆ t ca c´c tru.`.ng ho.p (tham khao c´c Phˆn (3) v` (4) trˆn) khi #S < n ta c´ ´’ ` a ˙a ˙a ’ o a a e o . ˙ t` (nhiˆu nhˆ t O(mn + n3 ) ph´p to´n so. cˆ p) mˆt mach µ c´ d ˆ d`i l´.n ho.n mach ’ ım ` ´ ´ thˆ e e a e a a o o ¯o a o . . . . http://www.ebook.edu.vn 146