Lí thuyết đồ thị part 7

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

Thêm vào BST

Báo xấu

78
lượt xem 11
download

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

Đồ thị được biểu diễn đồ họa bằng cách vẽ một điểm cho mỗi đỉnh và vẽ một cung giữa hai đỉnh nếu chúng được nối bởi một cạnh. Nếu đồ thị là có hướng thì hướng được chỉ bởi một mũi tên. Không nên lẫn lộn giữa một đồ hình của đồ thị với bản thân đồ thị (một cấu trúc trừu tượng, không đồ họa) bởi có nhiều cách xây dựng đồ hình. Toàn bộ vấn đề nằm ở chỗ đỉnh nào được nối với đỉnh nào, và bằng bao nhiêu cạnh. Trong thực hành, thường rất khó để...

Chủ đề:

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

Lưu

Nội dung Text: Lí thuyết đồ thị part 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 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 . 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 . 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 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. thˆ’ d u ` ˙ 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 . . . 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˙ . 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´ ´ e ¯ˆe e a ¯ˆ . o ı a ¯ˆ . o o ınh . 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 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 . 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 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. 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 }. 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). ¯. 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 . . . . 146
cu 1. Tru.´.c khi lˇp lai thuˆt to´n, ta cˆn kiˆ’m tra µ c´ phai l` mach tu.a cu.c d ai. (Nˆu ˙ ` ´ ˙a. ’ ˜ o a. a a a e o . ¯. e . . . .ng mˆt mach tu.a cu.c d ai µ tu. µ -d `i hoi nhiˆu nhˆ t O(n3 ) ph´p to´n ` ´ ˙ ’a ¯o ˙ ’ khˆng phai, xˆy du o o . ¯. ` e a e a . . . . . cˆ p). ´ so a Sau nhiˆu nhˆ t (n − 1) lˆn lˇp mo. rˆng mach, thuˆt to´n cho ch´ng ta mˆt mach ` ´ `a ˙o ’. e a a. a a u o . . . . Hamilton cua d` thi G. Dinh l´ 5.3.18 d u.o.c ch´.ng minh bˇ ng thuˆt to´n kiˆn thiˆt c´ch -. ` ´ ´ ˙ ¯o . ’ˆ y ¯. u a a a e ea . xˆy du.ng mach Hamilton v´.i d o ph´.c tap thuˆt to´n l` O(n4 ). a o ¯ˆ u . a aa . . . . 147
148
Chu.o.ng 6 -ˆ . ˙ ’ D` thi phˇ ng o a Ch´ng ta d a nghiˆn c´.u c´c t´ chˆ t cua c´c d` thi con, chˇng han, c´c dˆy chuyˆn, chu ˙ ’ ´’ ` e u a ınh a ˙ a ¯ˆ . u ¯˜ o a aa e . .o.ng n`y, ch´ng ta s˜ nghiˆn tr` v` c´c cˆy bao tr`m trong mˆt d` thi d ˜ cho. Trong chu ınh a a a u o ¯o . ¯a .ˆ a u e e .u to`n bˆ d` thi G v´.i cˆu hoi sau: khi n`o G l` phˇng? ˙ ’ ˙ ’ c´ u a o ¯o . .ˆ oa a aa Chu.o.ng n`y bˇt d` u v´.i hai v´ du vˆ d` thi Kuratowski d ´ng vai tr` trung tˆm trong ´ˆ ı . ` ¯ˆ . a a ¯a o eo ¯o o a ˙m tra t´ phˇng cua d` thi. Kˆ tiˆp l` c´c t´ chˆ t cua d` thi phˇng, chˇng han ’ ˙ ’ ˙ ’ ˙ ’ ´´ ´’ˆ ˙ ¯ˆ . e e a a ınh a ˙ ¯o . a ’o viˆc kiˆ e e ınh a a . . d .nh l´ Euler v` gia thuyˆt bˆn m`u nˆ’i tiˆng “moi d` thi phˇng l` 4−sˇc” (ph´t biˆ’u nˇm ˙´ ˙ ˙ ’ ´ ´´ a˙ ’ ¯i y eo aoe ¯o . a ˆ a a aea . 1850 v` d u.o.c ch´.ng minh nˇm 1976). Ch´ng ta c˜ng t` hiˆ’u tiˆu chuˆ’n cˆn v` d u dˆ’ d` ˙e ˙ a a ¯ ˙ ¯e ¯o ’ ˙ˆ a` a¯ . u a u u ım e -. ˙ ng-Dinh l´ Kuratowski. Cuˆi c`ng l` d ˆi ngˆ u h` hoc cua d` thi phˇng. ’ ˜ ınh . ˙ ¯o . a ˙ ’ ´u ´ ’ˆ thi l` phˇ .a a y o a ¯o a -. 6.1 Dinh ngh˜ v` c´c v´ du ıa a a ı . Nhˇc lai rˇ ng d` thi G d u.o.c goi l` phˇng nˆu tˆn tai mˆt ph´p biˆ’u diˆn G lˆn mˆt mˇt ˙ a.` ´ ˙ ’ ˜ e`. ´o a ¯o . ˆ ¯. .a a o e e e e o a . . . . tai d ınh cua ch´ng. C´c ˙ ’ ´ phˇng sao cho hai canh bˆ t k` cua d` thi khˆng cˇt nhau ngoai tr` . ¯˙ ´ a y ˙ ¯ˆ . o ’o ’ ˙ ’ a a u u a . . d` thi m` c´ thˆ’ biˆn d o’i cho tr`ng nhau bˇ ng ph´p biˆn dang co d˜n liˆn tuc trˆn mˇt ˙´ ˙ ` ´ ¯o . a o e e ¯ˆ ˆ u a e e ae. e a . . phˇng th` khˆng coi l` nh˜.ng d` thi phˇng kh´c nhau. Theo d inh ngh˜ d` thi trong H` ˙ ’ ˙ ’ a ıo au ¯ˆ . a o a ¯. ıa, ¯o . ˆ ınh ˙ ’ 6.1 l` phˇng. aa V´ du 6.1.1 (B`i to´n ba biˆt thu. v` ba nh` m´y). C´ ba biˆt thu. a, b, c v` ba nh` m´y: ı. aa e .a aa o e a aa . . . .´.c d, mˆt nh` m´y ho.i d ot e v` mˆt nh` m´y d iˆn f. Mˆi biˆt thu. nˆi v´.i ˜e ´ ´ mˆt nh` m´y nu o o aa o aa ¯ˆ ao a a ¯e o .oo . . . . . .ng ˆng dˆ n nu.´.c, ˆng dˆ n ho.i v` d u.`.ng dˆy d iˆn. Vˆy c´ thˆ’ v˜ ˙ ` ˜ ˜ ´ ´ c´c nh` m´y bˇ ng nh˜ o a aaa u a oo a a¯o a ¯e a o ee . . ˙ ng ba biˆt thu. v` ba nh` m´y v` tˆ t ca c´c d u.`.ng vˆn chuyˆ’n sao cho khˆng ˙ ’ ´ ˙ a ¯o a a aa ’ trˆn mˇt phˇ e a a e .a a e o . . . c´ hai d u.`.ng n`o cˇt nhau o. mˆt d iˆ’m kh´c c´c d` u m´t cua ch´ng hay khˆng? Ta c´ mˆ ˙ ´ ˙ o ¯e ’. u˙ ’ o ¯o aa a a ¯a ˆ u o oo h` ho´ bo.i d` thi hai phˆn K3,3 : C´c d ınh cua d` thi tu.o.ng u.ng c´c nh` v` c´c nh` m´y ` ınh a ˙ ¯o .’ˆ a ¯˙ ’ ˙ ¯o . ’ˆ a ´ a aaa aa 149
.......................... ......................... ..... ..... a .... .... .... .... ... ... ... ... ... ... ... ... ... ... . • ... ... ... ... ... .... . ........... . . .. .. ............ .. .. .. . .. . . .. .. ... . . .... ... .. .. ..... .. .. .. .. . . . . .. ... ... ... .. .. ... .. .. . .. ... . . ... .. . .. . ... .. .. ... . . ... ... . . .. .. . . .. .. ... . . ... .. ... ... . . . . . ... .. ...... ...... ... . . . ... ... .. ...... . . . . . .. . .. ... . . . .. ...... ... . . . . . ... .. ... . ..... . . ...... . ... . . ... . . e• . •b . .... ... ... . ... . . .. . . . . . .. . . . . .. . . . .. . . . .. . . . .. . . . . .. . . . . .. . . . .. . . . . . . . . . . . . . . .. . . . . . .. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. .. .. . . .. . .. .. .. . .. . . .. .. . .. .. .. . .. . . . . .. .. .. . .. .. .. . • • .. . . ....................................................... ...................................................... ... . . . ... . . ...... ...... . . ...... . .... c .... .. d .... .. .... .... .. .... .. ..... ... ..... ... ...... .... ...... .... ......... ........... ...................... .................. ˙ ’ H` 6.1: V´ du vˆ d` thi phˇng. ı . ` ¯o . a ınh eˆ (xem H` 6.2); mˆt canh liˆn thuˆc hai d ınh tu.o.ng u.ng v´.i mˆt nh` v` mˆt nh` m´y. B`i ¯˙ ’ ınh o. e o ´ oo aa o aa a . . . . .a vˆ kiˆ’m tra t´ phˇng cua d` thi Kuratowski K . Bˇ ng thu.c nghiˆm c´ thˆ’ chı e˙ ˙’ ˙ ’ ` to´n d u ` e ˙ ¯ˆ . ’o oe˙ a¯ ınh a a e . . 3,3 ` ˙’ ra rˇ ng d` thi n`y khˆng phˇng. a ¯ˆ . a o o a a c b •................................ • • .. .. .... .... . . .. . .. . ...... ..... . . ... . ... ... . ... . .... ... . .... ... . . . ... . ... . ... . ..... .... .. . . .... ... . . .... ....... . ... ..... . . ... . ..... ... .... .. . . .... ... . ... ... ..... ... ... . . . .... .... ... .... ..... .... . . . ... ... . . . ... .... .... ... ... . ... . . . . ... ... ... . . .... . .. .... .... ... .... ... .. . . . ... ... ... . . . .... ... ... .... .... ... .... ... . . . ... ... . . . ......... .... ... . ... ..... .... ... ... . . . ... ... . . . ... .... . . . .... . . . .. .. . ..... ... .... ..... . . . ... ... .... ..... ... .. ...... . . . . . . .. . . . ... ... ... . . . .... ... ... ... . ....... .... . . . .... ... ... . . ... ... . .... . ..... ... ... ... .... . . . .... . .. ... .... . . . . ...... ......... ..... ....... . . .. .. .... . . ..... ....... .... ...... ... . . .. . . . . ... ... ... ... . . .... . ...... ... .... ... .... .... . ....... . . . . .. . . . ... ... . . . .... ... ... .... ... ... . . . ... .... .... ... . . . ......... . .... .... ... ..... ... ........ . . . ... ... . . . ... . . . . . . .. ... ......... . . . .... .... .......... ... ... .... ..... ... . . . . . . .. . . . ... ... ... . . . .... ... ... ... .... .... .... . . . ... ... . . . . . ... .. . ... ... ... .... .... . . . .... ... ... .... ... . . . ... . . . ... .... .... .... ..... .. . . . ... ....... ... . . . ... ... ... ....... ... . . . .... ... . . . . .... ... ... . .... ... . .... . . . . .... .. .... .. . .... ...... .... ... . .... ... . ... . .. . ... .. . ... . ... . . . .......... ...... . .... .. . ... . ... ... . ... ....... . .. . .. • • • .. ...... ...... ..... .... .... . . . . . e f d -ˆ . H` 6.2: D` thi Kuratowski K3,3 . ınh o V´ du 6.1.2 C˜ng bˇ ng thu.c nghiˆm, c´ thˆ’ ch´.ng to d` thi d` y d u K5 (xem H` 6.3) ˙ ` ˙ ¯o . ¯ˆ ¯ ˙ ’ˆ ’ ı. u a e oeu a ınh . . ˙ ’ l` khˆng phˇng. ao a Vˆ t´ khˆng phˇng cua c´c d` thi K3,3 v` K5 s˜ d u.o.c giai th´ trong nh˜.ng phˆn ˙ ’ ` ınh o ` ˙ a ¯o . ’ ˙ ’ e a ˆ a e¯ . ıch u a .ng t´ chˆ t: ` sau. Ch´ y rˇ ng c´c d` thi K5 v` K3,3 c´ nh˜ ´ u´ a a ¯o . ˆ a ou ınh a ˙ ’ ˙ ’ 1. Ca hai l` khˆng phˇng; ao a 2. Nˆu xo´ mˆt canh hoˇc mˆt d ınh cua d` thi th` s˜ nhˆn d u.o.c mˆt d` thi phˇng. ˙ ’ ´ o ¯˙ .’ ˙ ¯o . ı e a ¯ . ’ˆ e ao. a o ¯o . a .ˆ . . . 150
d • ..... ...... ... .. ... ... .. . ... ... . . ... ... .. . ... ... . . ...... ... . .. ...... . ... ... . .. ... ... .. ... ... . ... . ... ... ... . . ... . . ... ... ... . .. ... ... . ... . ... . . ... . ... . .. . . . ... ... ... . . ... . . .. . . ... ... . ... . ... . . ... . ... . .. . . ... . ... ... . ... . . . .. . . ... ... . ... . ... . . e• •c ... . ... . ................................................................................... .................................................................................. . .. .. . .. .. . . .... .. .... . . . ... . . . .. . ... . . . . ... . . . .. ... . . . ... . . .. . . . ... . . .. . . . ... . ... . . ... . . ... . . . . . ... . . . . ... . . ... ... . . . . ... . . . . .. . ... . . . . ... . . ... ... . . . . ... . . . . . ..... ... . ..... . . . . . . ... .. ... . . . . ... . . ..... ... . . .. . . .. . . .. . ... ... . . .. . . . ... .... . . ... .. . .. . . . . . ..... ... .. . . ... .. . ..... . . . ... . . ... . . ... . . . . ... . ... . . ... . . ... . . . . ... ..... . ... . . . . ... ..... . . . . . . . . . . ..... . . . . ... .. . . . . .... . . . . . . . ... ..... . ... ..... . . . . . . . . . ... . . ... . . . ... . ... . . . ... . . . ... . . . . ... . ... . . ... . . ... . . . . ... . ... . . . ... . . .. . . . . ... . ... . .. . . ... ... . . .. .. ... .. ... . . ..... ... .. . .. . . ..... ... .. . . ... .. . . . .. . . ... ... . . . . .. . . .. ... . . ... . . . ... .... • • .. .... ....................................................... ........................................................ ... .. .. a b -ˆ . H` 6.3: D` thi Kuratowski K5 . ınh o ˙ ’ ˙ ’ 3. K5 l` d` thi khˆng phˇng c´ sˆ d ınh ´ nhˆ t; K3,3 l` d` thi khˆng phˇng c´ sˆ canh ´ ´’ ´ ´ o o ¯˙ ıt a a ¯o . o ˆ a a ¯ˆ . o o a oo. ıt ´ nhˆ t. a C´c biˆ’u diˆn kh´c nhau cua mˆt d` thi phˇ ng ˙ ˜ ˙ ’ ˙ ’ 6.2 a e e a o ¯ˆ . o a . Tru.´.c hˆt ta c´ kˆt qua sau. ´ ´ ˙ ’ oe oe Dinh l´ 6.2.1 [Fary] Moi d o.n d` thi phˇ ng c´ thˆ’ biˆ’u diˆn trˆn mˆt mˇt phˇ ng sao cho -. ˙˙ ˙ ’ ˜ ˙ ’ y .¯ ¯ˆ . a o oee e e oa a . . ˙ ’ ´ c´c canh l` c´c d oan thˇ ng v` ch´ng chı’ cˇt nhau tai c´c d ı’nh chung. ˙a . a ¯˙ a. a a ¯. a au Ch´.nh minh. Ch´.ng minh cua d .nh l´ n`y kh´ ph´.c tap v` khˆng d ´ng g´p nhiˆu trong ` ˙ ¯i ’ u u ya au. a o ¯o o e ˙u t´ phˇng cua d` thi. Ban d oc quan tˆm c´ thˆ’ xem [24]. Chˇng han, d` thi ’ ınh a ˙ ˙ ’ ˙ ’ ˙ ¯o . ’ viˆc hiˆ e e ˆ . ¯. a oe a . ¯ˆ . o . trong H` 6.1 c´ thˆ’ v˜ lai chı su. dung c´c d oan thˇng nhu. trong H` 6.4. Trong d inh ˙ ˙ ’ ˙˙ . ’’ ınh o ee. a ¯. a ınh ¯. .n v` c´c khuyˆn hoˇc mˆt trong hai canh song song khˆng thˆ’ v˜ ˙ l´ n`y, d` thi cˆn phai d o ı a y a ¯o . ` ˙¯ ’ ˆ a e a o o ee . . . ˙.i c´c d oan thˇng. ˙ ’ ’ a ¯. bo a Diˆn e . K´ hiˆu R(G) l` d` thi phˇng G d u.o.c biˆ’u diˆn trˆn mˇt phˇng. C´c v`ng liˆn thˆng (theo ˙ ˙ ’ ˜ ˙ ’ ye a ¯o . a ˆ ¯. e e e a a au e o . . ˙ ng R2 ) cua tˆp R2 \ R(G) goi l` c´c diˆn. Mˆt diˆn l` mˆt v`ng cua mˇt ’ oo˙ ’ ˙a ’. ˙ ’ tˆ pˆ cua mˇt phˇ a a .aa e o eaou a . . . . . . phˇng d u.o.c gi´.i han bo.i c´c canh goi l` biˆn; hai diˆn goi l` kˆ nhau nˆu c´c d u.`.ng biˆn ˙ ’ e . a` ´ ˙a. ’ a ¯. o. ae e e a ¯o e . . ´o. ˙’ cua ch´ng c´ ´ nhˆ t mˆt canh chung. u o ıt a . 151
c • . .. .... . ..... .. . .. . .. . . . . ... . .. . ... . .. . .. ... .. . .. .. . .. . . .. .. . . .. a . . .. .. . . .. . .. . .. .. . • .. . .... .. .. . . .. ... .. .. ... . .. . .. .. .. . .. . .. .. .. . . .. .. . .. .. .. . ... .. .. .. . .. . .. .. .. . .. . .. .. . .. .. .. .. . .. .. . .. . .. .. . .. .. . .. .. .. .. . .. . .. . .. . . .. .. .. ... . .. . .. . .. . .. .. . .. ... .. .. .. . .. .. .. . .. .. . .. .. .. ... . • . .. . .. . . .. .. ....... .. .. .. .. ........ . .. . . .. .. .. .. . .. . ... .. .. .. . ... .... ... .. . . e ... ... ... .. .. . .. ... .. ... .. .. .. . ... .. . ... .... .. ... .. .. ... .. . .. ... ... .. . ... ... . ... ... .. . . ... ..... ....... .. ... .. ... ...... ..... ... ..... . ... ... . .... ..... . ... .. .. ... ... ... ..... .... ..... ... ... . ... ... .. ... .... ... .. ...... ....... ..... ... .. .. ... .. . .. ......................................................................... • • .... ......................................................................... ... ... .. .. b d H` 6.4: ınh N´i chung, biˆn cua diˆn gˆm c´c chu tr` d o.n gian v´.i c´c canh r`.i nhau, c´c canh e` e˙ ’ ˙ oa. ’ o .o a ınh ¯ o a. ´ o o ¯˙ ’ treo (canh c´ mˆt d ınh bˆc mˆt), hoˇc c´c canh nˆi hai chu tr` a o aa. o ınh. Diˆn ph´ ngo`i, goi e ıa a . . . . . . . .`.ng biˆn ch´.a bˆn trong n´ c´c canh o`. l` diˆn vˆ han, luˆn luˆn tˆn tai mˆt chu tr` l` d u o ae o. o o o ınh a ¯ e ue oa . . . ´˙ ’ kh´c; d ´ l` chu tuyˆn cua diˆn vˆ han. a ¯o a e e o. . ˙ ’ V´ du 6.2.2 Ban d` d .a l´ l` d` thi tˆ pˆ phˇng khˆng c´ cˆu; d` thi d ´ c´ t´ chˆ t d ac o ` ¯o . ¯o o ınh a ¯ˇ ´. ˙ ¯o ¯i y a ¯ˆ . o o a ’ˆ ı. o o a ˆ ˙ a mˆi d ınh ≥ 3. Mˆt diˆn c´ thˆ’ kˆ v´.i diˆn kh´c o. nhiˆu canh. Trˆn H` ˙` o ˜ ¯˙ ` ’ ’ ˙’ biˆt l`: bˆc cu eaa o o e o ee e a e. e ınh . . . . . ` ` o o ¯˙ ’ 6.5 ta ch´ y rˇ ng c´c diˆn d v` g khˆng kˆ nhau mˇc d` ch´ng c´ mˆt d ınh chung; a l` diˆn u´ a a e a o e auu ae . . . . vˆ han. o. .................... .................. .......... ......... ...... ..... ...... ...... .... .... ..... ..... ... ... .... .... ..... ...... .... .... ..... .. ..... ... .. . ... .... .... ... . . . . .. . .... ... .... ... .. .. ... ... .. .. .. . ... .. ... .. .. ... .. .. ... .. .. .. .. .. .. ... ... .. .. ... .. ... . .. .. ... ... .. .. a .. .. .. b .. .. .. .. .. .. .. .. . .. .. .. .. .. . .. .. .. .. .. . .. c .. .. .. . . .. .. .. .. .. . .. .. . .. . . . .. .. . . . . . .. . . .. . . . . .. . . .. . . ..... ... . ... . .. ........... ... .. ........... . . .. . . ... ... . . .. ...... .. . . .. ...... ... . . ... . . ...... .. ...... .. . ... . .. ... . . ...... ...... . . . .. .. e .. .. . .. ....... .... . . ... ... . .. .......... ...... ...... . .. . ... .. ... . . ...... .. ...... ... ...... . .. . ... .. . .... .. ... . ...... .... ...... ..... . ..... .. ... .. . ... ...... ...... . ..... .. ... . ... ... .. . .. ...... .. .. .. . ...... ... .. ... .. ... ........................ ... ....................... .. . .... . ... .. .. ... ........ . ....... ... .. .. . ... . ......... ... . ......... .. . . ... .. ... . . .. . . .... . . . .. .. h d ... .. . . . ... .... .... . .. . . . .... .. . . .. . .. ... ... .. . . . ... ... ... . . . .. . . . .. .. . ... .. f . .. . . . . ... ... . . . . .. . .... .. . . . . .. . ... .. . . . ... ... . ... .. . . . .. . . . . g .. . .. . .. . . ... . . ... .. . ... ... ... ... . . . . .. . .. . . .. . ... . . . .... .... . ....... .. . . . . .... . .. . ... . . .. . ... .. .. . ....................................................................................................... . . .. .. ...................................................................................................... . ... . ... . H` 6.5: ınh 152