intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Đồ 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

98
lượt xem
18
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ủ đề:
Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. • .... ... ... . ... ... . ... ... . ...... ... . ...... . ... . ... . ... ... ... . ... . ... . ... ... ... . ... . ... .. . . ... . ... ... ... . .. . . ... ... ... . ... ... . ... .. . . ... ... . ... ... . .. . . ... ... ... ... . . ... ... .. . . ... . ... ... ... . . .. . ... . ... ... ... . ... . • ... .. . . ... ... ... . ... .. .. ... . ... ... ... . ... . .. ... ... .. . . .. ... . ... ... ... .. .. . ... ... . .. .. ... • • ... .. .. .. ... . ... . ...... . .. . ........ . ..... . . ..... . . . .. ....... . ..... ... . .. ........ ..... .. . . . . ... ..... .. . ..... . . ..... ..... .. . . . ..... .. . . . . • • ....................................................................... ..................................... ......................... . . .. .. . .. . .. . .... .... .... ... . .. . .. . . . .. .... .... . .... .... . . .. . . . . ...... .. .... .... . . .. . ..... .. . . .... . .... . . .. .. .... .. .... .. .. .... .... . .. .. .. .. . .... . .. .. .... .. . .. . ..... . .... .. .... ...... . .... ...... .. . .. . . . . . .. . .... .. ......... . .. . . . . .... ...... . . .. .... . .. .. . . ...... . . .... . . .... . .. .. . .. .... . .. . ... . . .... . . ... ...... .. . .... .. ..... ...... .. .. ... • • ... ... ... .. . .. .. . .. .. .. .. .. . .. . .. .. .. .. .. . . .. .. .. . .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .... .. • • ... ....................................................... ...................................................... . -ˆ . 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
  14. 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
  15. -. -` 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
  16. 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
  17. •.... .. . ..... ..... ..... ..... .... . .. ....... .... . ... ....... .... ... .... ... .... .. .... . .. .... .. .... .... .... .... .. .. . .. .... .... ... ... .. .. .. .... .... .... .... .. .. .... .... .... .... .. .. .. .... .. .... . .. .... .... .. .. .... .. .... .. . .. .... .... .. .... .. .... .. .. . • .... • .. .... .... .... .. .. .. .. . . .. . . .. .. . .. . . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. .. . . .. . . .. . . .. . .. . .. . . . .. . . .. .. . .. . . . .. . .. .. . . .. . . . .. . .. .. . . .. . . . .. . . ... .. . . .. .. . . . .. . . .. . . .. .. . . .. . .. . . . .. ... . .. . .. . . ... • • . . . .. .. . .... ... . .. . . .... .... .... .... .. . .... .... .... .... .... .... .. . .... .... .... .... ... . .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....... .... ....... •.... ... 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2