Đồ thị và các thuật toán – Chương 5: Bài toán Euler và bài toán Hamilton

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

45
lượt xem 3
download

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

Trong chương này người học sẽ tìm hiểu các nội dung cụ thể về: Bài toán Euler, thuật toán tìm dây chuyền Euler, bài toán người đưa thư Trung Hoa, bài toán Hamilton, các điều kiện đủ về sự tồn tại chu trình Hamilton. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

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

Lưu

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

Chu.o.ng 5 B` ai to´ an Euler v` a b` ai to´ an Hamilton L´y thuyˆe´t d¯`oˆ thi. ph´at triˆe˙’n bˇa´t nguˆ u. nh˜ `on t` u.ng b`ai to´an cˆo˙’ d¯iˆe˙’n, trong sˆo´ d¯o´ b`ai to´an Euler v`a b`ai to´an Hamilton t`ım h`anh tr`ınh d¯i qua mˆo˜i ca.nh d¯u ´ng mˆo.t lˆ `an v`a qua mˆo˜i d¯ı˙’nh d¯u ´ng . . `an tu o ng u mˆo.t lˆ . ´ ng d¯o´ng vai tr`o quan tro.ng. u.ng u Hai b`ai to´an n`ay c´o liˆen quan d¯ˆe´n nh˜ ´.ng du.ng: c´ac b`ai to´an t`ım h`anh tr`ınh tˆo´t nhˆa´t (ngu.`o.i d¯u.a thu. Trung Hoa, ngu.`o.i ch`ao h`ang), tu.. d¯ˆo.ng ho´a thiˆe´t kˆe´ bˇ`a ng m´ay t´ınh, lˆa.p li.ch, vˆan vˆan. Mˇa.c d`u hai b`ai to´an n`ay d¯u.o..c ph´at biˆe˙’u rˆa´t giˆo´ng nhau, nhu.ng m´ u.c d¯oˆ. kh´o trong viˆe.c gia˙’i quyˆe´t ch´ ung l`a rˆa´t kh´ac nhau. Ch´ung ta s˜e ch´ u.ng minh rˇa` ng trong d¯`ˆo thi. vˆo hu.´o.ng, tˆ u.c t`ım `on ta.i thuˆa.t to´an d¯a th´ h`anh tr`ınh Euler v`a b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa c´o thˆe˙’ d¯u.a vˆ `e t`ım cˇa.p gh´ep ho`an . . ´ ung xem Phˆan 7.5). C´ac thuˆa.t to´an n`ay s˜e d¯u.o..c tr`ınh ha˙’o c´o tro.ng lu o. ng nho˙’ nhˆa t [30] (c˜ ` b`ay trong c´ac Phˆ `an 5.1 v`a 5.2. Mˇa.t kh´ac, vˆa´n d¯`ˆe tˆ `on ta.i chu tr`ınh hay ma.ch Hamilton l`a nh˜ u.ng b`ai to´an khˆong d¯a th´u.c khˆong d¯u.o..c d¯`ˆe cˆa.p o˙’. d¯ˆay. Ba.n d¯o.c quan tˆam c´o thˆe˙’ xem, chˇa˙’ng ha.n [30]. Ch´ ung ta chı˙’ tr`ınh b`ay trong Phˆ `an 5.3 nh˜ u.ng kˆe´t qua˙’ ch´ınh liˆen quan d¯ˆe´n su.. tˆ `on ta.i cu˙’a c´ac chu tr`ınh hay ma.ch Hamilton. Khi c´o d¯iˆ `eu kiˆe.n, c´ac ch´ u.ng minh c´o t´ınh kiˆe´n thiˆe´t thuˆa.t to´an hoˇa.c c´o thˆe˙’ d¯`ˆe xuˆa´t nh˜. . . u ng phu o ng ph´ap heuristic. 5.1 B` ai to´ an Euler - i.nh ngh˜ıa 5.1.1 Gia˙’ su˙’. G = (V, E) l`a d¯`oˆ thi. vˆo hu.´o.ng (d¯o.n hoˇa.c d¯a d¯`ˆo thi.). Dˆay chuyˆ D `en 127 http://www.ebook.edu.vn
Euler l`a dˆay chuyˆ u.a tˆa´t ca˙’ c´ac ca.nh cu˙’a d¯`oˆ thi., mˆo˜i ca.nh d¯u `en ch´ `an. Chu tr`ınh ´ng mˆo.t lˆ `en Euler m`a d¯ı˙’nh d¯`ˆau tr` Euler l`a dˆay chuyˆ . ung v´o i d¯ı˙’nh cuˆo´i. V´ı du. 5.1.2 (B`ai to´an Euler) C´ach d¯ˆay khoa˙’ng ba trˇam nˇam, nhiˆ `eu ngu.`o.i dˆan th`anh phˆo´ K¨onigsberg cu˙’a nu.´o.c Nga (sau n`ay l`a th`anh phˆo´ Kaliningrat) d¯a˜ t` u.ng thˇa´c mˇa´c vˆa´n d¯`ˆe nhu. sau: Th`anh phˆo´ c´o sˆong Pregel cha˙’y qua, gi˜ u.a sˆong c´o c`u lao Kneiphof, v`a c´o 7 chiˆe´c cˆ `au . bˇa´c qua sˆong nhu trˆen H`ınh 5.1(a); c´o thˆe˙’ d¯i da.o qua khˇa´p c´ac cˆ . `au nhu ng mˆo˜i cˆ `au chı˙’ d¯i mˆo.t lˆ . . `an thˆoi khˆong? Nˆe´u ta coi mˆo˜i khu vu. c a, b, c, d cu˙’a th`anh phˆo´ nhu mˆo.t d¯ı˙’nh, mˆo˜i cˆ `au . . ´ ˙ ’ ˙ ’ ` ´ qua la.i hai khu vu. c nhu mˆo.t ca.nh nˆoi hai d¯ınh, th`ı ban d¯ˆo th`anh phˆo K¨onigsberg l`a mˆo.t d¯`oˆ thi. (H`ınh 5.1(b)). Thˇa´c mˇa´c cu˙’a ngu.`o.i dˆan th`anh phˆo´ ch´ınh l`a: c´o thˆe˙’ v˜e d¯u.o..c d¯`ˆo thi. bˇa` ng mˆo.t n´et b´ut liˆ`en hay khˆong? N´oi c´ach kh´ac: tˆ `on ta.i chu tr`ınh Euler? Nh`a to´an ho.c L. Euler (1707-1783) l`a ngu.`o.i d¯`aˆu tiˆen d¯˜a ch´ u.ng minh b`ai to´an khˆong c´o l`o.i gia˙’i (nˇam 1736, xem [22], [23]), v`a v`ı vˆa.y b`ai to´an thu.`o.ng d¯u.o..c go.i l`a b`ai to´an Euler `e c´ac cˆ vˆ `au o˙’. K¨onigsberg. a ...... ...... ...... ... .. ..... a ... .... ......... ... ... ..... ..... .............. .......... ... .... ..... ................ ................ ... ... ..... ..... ................................................ ................... .... ... ..... ...... ..................................................................................................... ....... ... ... ..... ..... ...... ........ .......... ... ... ... ... ..... ...... ...... .... ... ... ..... ..... ...... ...... ........ ... .. ..... ...... ...... ..................................................... ... ... ..... ..... . . . . . . . . . ..... ...... ... ... ......................................................................... ... ...... ..... ... .. ..... ..... . ... .. ... ... ... ... ... ........................................................................................... . ..... ... ...... b . ... ... . .......................................... .............................................. ..... c ...... .. .. . b . .. .. . ...... . ...... .. ..... c ................................................................... . ....... ..... . .... .... .... .......... ....... ... .... .... ...... ...... .......................................... ... .. ..... ........ ... .... ..... ...... ...... ..... ...... ...... ...... ... .... ..... ........ ....... ...... .... ... .. ...... . .............................. ....... .... .... .... ....................................................... ... ... ... .... ......................................... .. . . ... ..... . ..... ................... ... ... ..... . . .... ......... ............... ... ..... ......... .... ........ ... .... . . . . ..... ... .. .... ... ... ..... ... .. ........ d ... ... ...... ..... ...... ...... d (a) (b) - `ˆo thi. tu.o.ng d¯u.o.ng. H`ınh 5.1: (a) Ba˙’n d¯`ˆo cu˙’a th`anh phˆo´ K¨onigsberg. (b) D - i.nh l´ D y 5.1.3 [Euler] D - a d¯`ˆo thi. vˆo hu.´o.ng liˆen thˆong G = (V, E) c´o dˆay chuyˆ `en Euler nˆe´u `a ng 0 hoˇa.c 2. v`a chı˙’ nˆe´u sˆo´ c´ac d¯ı˙’nh bˆa.c le˙’ bˇ Ch´ u.ng minh. Tru.´o.c hˆe´t ch´ uy u.a dˆay chuyˆ ´ rˇ`a ng d¯`oˆ thi. khˆong liˆen thˆong khˆong thˆe˙’ ch´ `en hoˇa.c chu tr`ınh Euler. Bˆay gi`o. ta ch´ u.ng minh d¯iˆ `eu kiˆe.n cˆ `an. Nˆe´u µ l`a dˆay chuyˆ `en Euler, th`ı chı˙’ c´o hai d¯ı˙’nh d¯`aˆu v`a cuˆo´i c´o bˆa.c le˙’. Nˆe´u ngo`ai ra, hai d¯ı˙’nh n`ay tr` ung nhau (chu tr`ınh Euler) th`ı khˆong c´o d¯ı˙’nh bˆa.c le˙’. 128 http://www.ebook.edu.vn
Kˆe´ tiˆe´p ta ch´ u.ng minh d¯iˆ `eu kiˆe.n d¯u˙’ bˇ`a ng quy na.p theo sˆo´ ca.nh m cu˙’a G. Hiˆe˙’n nhiˆen d¯.inh l´ y d¯u´ng nˆe´u m = 1. Gia˙’ su˙’. d¯.inh l´ ´ng cho mo.i d¯`oˆ thi. liˆen thˆong m ca.nh. Nˆe´u G c´o y d¯u . hai d¯ı˙’nh bˆa.c le˙’, gia˙’ su˙’ c´ac d¯ı˙’nh n`ay l`a a v`a b (nˆe´u tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a G c´o bˆa.c chˇa˜n, cho.n d¯ı˙’nh a bˆa´t k` y v`a lˆa´y b = a). K´ y hiˆe.u µ l`a dˆay chuyˆ `en m`a ta d¯i trˆen d¯`oˆ thi. G xuˆa´t ph´at t` u. a . . theo hu ´o ng tu` yy ´, d¯i qua mˆo˜i ca.nh d¯u ´ng mˆo.t lˆ . . `an. Nˆe´u ta.i th`o i d¯iˆe˙’m n`ao d¯´o ta o˙’ d¯ı˙’nh x 6= b ngh˜ıa l`a ta d¯a˜ su˙’ du.ng mˆo.t sˆo´ le˙’ ca.nh liˆen thuˆo.c v´o.i x nˆen c´o thˆe˙’ d¯i theo ca.nh kh´ac chu.a . d¯u.o..c su˙’. du.ng. Nˆe´u ta khˆong thˆe˙’ d¯i d¯u.o..c n˜ u.a, ngh˜ıa l`a d¯ang o˙’. d¯ı˙’nh b. Nˆe´u tˆa´t ca˙’ c´ac ca.nh d¯a˜ d¯u.o..c su˙’. du.ng, µ l`a mˆo.t dˆay chuyˆ `en Euler v`a d¯.inh l´ ´ng. Trong tru.`o.ng ho..p ngu.o..c y d¯u la.i, d¯`oˆ thi. con G0 d¯u.o..c x´ac d¯.inh bo˙’.i c´ac ca.nh chu.a d¯u.o..c su˙’. du.ng chı˙’ c´o nh˜ u.ng d¯ı˙’nh bˆa.c chˇa˜n. K´ 0 0 0 y hiˆe.u G1 , G2 , . . . , Gp l`a c´ac th`anh phˆ `an liˆen thˆong cu˙’a G ch´ 0 . u a ´ıt nhˆa´t mˆo.t ca.nh. . Khi d¯´o c´ac d¯`ˆo thi. Gi c´o sˆo´ ca.nh ´ıt ho n m v`a do d¯´o theo gia˙’ thiˆe´t quy na.p, ch´ 0 ung ch´ u.a mˆo.t chu tr`ınh Euler µi . V`ı G liˆen thˆong, dˆay chuyˆ . `en µ c´o chung v´o i c´ac d¯`oˆ thi. G1 , G2 , . . . , G0p c´ac 0 0 d¯ı˙’nh theo th´ u. tu.. i1 , i2 , . . . , ip . Khi d¯o´ h`anh tr`ınh: xuˆa´t ph´at t` u. a d¯i trˆen µ d¯ˆe´n d¯ı˙’nh i1 , d¯i do.c theo chu tr`ınh µ1 t` u. i1 vˆ `e i1 , d¯i trˆen µ d¯ˆe´n d¯ı˙’nh i2 d¯i do.c theo chu tr`ınh µ2 t` u. i2 vˆ `e i2 , v`a vˆan vˆan, l`a mˆo.t dˆay chuyˆ `en Euler xuˆa´t ph´at t` . u a v`a kˆe´t th´ uc ta.i b. D - i.nh l´ . . y d¯u o. c ch´ u.ng minh. / - `ˆo thi. thoa˙’ c´ac d¯iˆ D - .inh l´ `eu kiˆe.n cu˙’a D y Euler go.i l`a d¯`ˆo thi. Euler. 5.1.1 Thuˆ a.t to´ an t`ım dˆ `en Euler ay chuyˆ C´ach ch´u.ng minh D y Euler 5.1.3 cho ta mˆo.t thuˆa.t to´an xˆay du..ng dˆay chuyˆ - i.nh l´ `en Euler trong mˆo.t d¯`ˆo thi. Euler. 1. Xˆay du..ng mˆo.t dˆay chuyˆ `en d¯o.n gia˙’n µ xuˆa´t ph´at t` u. s. 2. Nˆe´u tˆa´t ca˙’ c´ac ca.nh cu˙’a G d¯a˜ d¯u.o..c su˙’. du.ng th`ı d` u.ng v`a ta c´o µ l`a dˆay chuyˆ `en Euler. . . . . Ngu o. c la.i sang Bu ´o c 3. 3. K´ `om c´ac ca.nh chu.a d¯u.o..c su˙’. du.ng. Cho.n d¯ı˙’nh c cu˙’a G1 y hiˆe.u G1 l`a d¯`oˆ thi. con cu˙’a G gˆ nˇ`a m trˆen dˆay chuyˆ `en µ. Xˆay du..ng chu tr`ınh d¯o.n gia˙’n µ1 trong d¯`oˆ thi. G1 xuˆa´t ph´at u. d¯ı˙’nh c. t` 4. Mo˙’. rˆo.ng dˆay chuyˆ u.c l`a d˜ay c´ac `en µ bˇa` ng c´ach gˇa´n thˆem chu tr`ınh µ1 ta.i d¯ı˙’nh c (t´ . . ca.nh cu˙’a µ1 d¯u o. c ch`en v`ao d˜ay c´ac ca.nh cu˙’a µ). 5. Thay G bo˙’.i G1 v`a lˇa.p la.i bu.´o.c 2. - `ˆo thi. trong H`ınh 5.2 c´o mˆo.t chu tr`ınh Euler V´ı du. 5.1.4 D (v1 , e1 , v2 , e2 , v3 , e3 , v2 , e4 , v3 , e15 , v4 , e14 , v5 , e13 , v4 , e12 , v6 , e11 , 129 http://www.ebook.edu.vn
e2 .......................................................................... .............. ........... ........... ......... . . . ........... ........ v2 .. ........ ....... ..... e3 .......................................................................................................................................................................................................... .. ....... ....... .... v3 .. .... . ....... ...... ... ......... .... . ........... ...... . .... . . ... . ........... .... .. .. .. . .... ......... ... ............... ........ ..... ..... ........... .............. e4 . . ........... ...... ........................................................................... ............ . . ... ... . . ..... ..... ..... ..... ... . ... . .. . ...... . . . ..... ... ... e1 ...... .......... . ........ .. . .......... . . . . . . . . ..... ..... ..... ..... . ......... ...... . .. . .............. . . .......... . . . . . . . e16 ..... .....e15 ..... ... . . ........ . .... ... . . ..... . . . . . . .... e17 .. .. . . . . . . . . . ..... ..... ..... ..... ..... ....... ......... . . . ..... .... ..... . .. ....... ........ v7 . . . . ..... . . . . . . .... ..... . . . . . . . . ........... .. . e14 .. ... ... .. ... ......... . . .. .. ..... ..... ................ ......... .... v1 .. ..... .. ..... e5 .............................................................................................................................. ................... v5 . . . . ............. . . ........... .. . .... .. .. .......... ..... ............ ........ v4 ... ........ ... ......... .... ............. ... ........ .... .................... .............. ... ...... .... ....... ....... . . ............................................................. ........ ... ... ... ...... ...... ...... ...... .... ... ....... ....... ....... ....... .... ... ... e13 ..... ..... ... ..... ... ... ..... . ... . ....... . . ......... ..... . ....... .... .... .... ..... ..... ..... ..... ..... e6 ..... .... ... ....... e10 ....... ....... .... ... ... ..... ..... ..... ... ..... ..... ..... ..... ..... ..... ..... e8 . . .... ....... .. ......... ....... . . e11 .... ..... ........ e12 ..... ....... ..... e7 ..... ..... ..... ..... ..... .... .... ..... ... ... . . ....... ....... .. ......... ... ... . . .... .. ....... ..... ...... ... .. ....... .... ..... ...... ... ... ....... ... ..... ...... ... ... ....... ... ..... ...... ...... ... ... . ....... ... . . . .. ...... . ...... ... ... ....... ....... .... ......... . ....... ..... ....... .... .. . . .......................................................................................................................................................................................................... v8 e9 v6 `e d¯`ˆo thi. Euler. H`ınh 5.2: Mˆo.t v´ı du. vˆ v5 , e16 , v3 , e17 , v7 , e10 , v6 , e9 , v8 , e8 , v7 , e5 , v1 , e7 , v8 , e6 , v1 ). Mˆo.t dˆay chuyˆ `en hay chu tr`ınh Euler c´o thˆe˙’ d¯u.o..c x´ac d¯i.nh bo˙’.i mˆo.t danh s´ach c´o th´ u. tu.. c´ac d¯ı˙’nh cu˙’a G ch´ u.a trong n´o. Chˇa˙’ng ha.n, ta c´o thˆe˙’ su˙’. du.ng mˆo.t cˆa´u tr´ uc danh s´ach liˆen kˆe´t typedef struct PathNode *PathPtr; struct PathNode { byte Vertex; PathPtr Next; }; d¯ˆe˙’ d¯´anh dˆa´u c´ac d¯ı˙’nh liˆen tiˆe´p trˆen dˆay chuyˆ `en, trong d¯´o V ertex l`a sˆo´ hiˆe.u d¯ı˙’nh trˆen dˆay chuyˆ `en; v`a con tro˙’ N ext chı˙’ n´ ut kˆe´ tiˆe´p ch´. u a sˆo´ hiˆe.u cu˙’a d¯ı˙’nh kˆ `e V ertex trˆen dˆay chuyˆ `en. ˜ ´ ` Dˆe thˆa y rˇa ng, danh s´ach n`ay c´o sˆo n´ ´ ` ut bˇa ng (m + 1). T` u. d¯ˆay vˆ`e sau ta s˜e gia˙’ thiˆe´t G d¯u.o..c cho bo˙’.i ma˙’ng c´ac danh s´ach kˆ `e V out[] (c´o ´ . ˜ tro.ng sˆo), trong d¯´o v´o i mˆoi d¯ı˙’nh vi ∈ V, V out[i] l`a danh s´ach c´ac d¯ı˙’nh liˆen thuˆo.c d¯ı˙’nh vi v`a tru.`o.ng d¯oˆ. d`ai Length o˙’. n´ut th´ u. j (tu.o.ng u´.ng d¯ı˙’nh vj ) l`a sˆo´ ca.nh liˆen thuˆo.c v´o.i d¯ı˙’nh vi . Trong qu´a tr`ınh thu..c hiˆe.n thuˆa.t to´an, mˆo˜i khi d¯i qua ca.nh (vi , vj ) n`ao d¯´o, ta gia˙’m d¯oˆ. 130 http://www.ebook.edu.vn
d`ai Length mˆo.t d¯o.n vi. o˙’. n´ u. j trong danh s´ach V out[i] d¯ˆe˙’ d¯´anh dˆa´u ca.nh d¯˜a d¯u.o..c su˙’. ut th´ du.ng. V`ı mˆo˜i ca.nh cu˙’a d¯`oˆ thi. d¯u.o..c kiˆe˙’m tra nhiˆ `eu nhˆa´t hai lˆ u.c ta.p cu˙’a thuˆa.t `an nˆen d¯oˆ. ph´ to´an l`a O(m). 5.2 B` an ngu.` ai to´ o.i d ¯u.a thu. Trung Hoa X´et d¯`ˆo thi. vˆo hu.´o.ng liˆen thˆong G := (V, E) c´o tro.ng sˆo´ (t´ u.c l`a mˆo˜i ca.nh e ∈ E ta g´an mˆo.t sˆo´ w(e) go.i l`a tro.ng lu.o..ng cu˙’a ca.nh e). B`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa (khˆong d¯u.o..c d¯.inh hu.´o.ng) ph´at biˆe˙’u rˇ`a ng t`ım mˆo.t dˆay chuyˆ `en gi˜u.a hai d¯ı˙’nh cho tru.´o.c a, b ∈ V su˙’. du.ng mˆo˜i ca.nh cu˙’a G ´ıt nhˆa´t mˆo.t lˆ `an v`a c´o d¯oˆ. d`ai nho˙’ nhˆa´t (xem [44]). Nhiˆ`eu b`ai to´an vˆ `e h`anh tr`ınh (ngu.`o.i d¯u.a thu., ngu.`o.i giao s˜ u.a, ngu.`o.i ch`ao h`ang, v.v) c´o thˆe˙’ ph´at biˆe˙’u o˙’. da.ng n`ay. Trong tru.`o.ng ho..p d¯`oˆ thi. c´o hu.´o.ng, trong d¯o´ mˆo˜i cung cu˙’a G `an d¯u.o..c su˙’. du.ng ´ıt nhˆa´t mˆo.t lˆ cˆ `an, b`ai to´an c´o thˆe˙’ d¯u.a vˆ `ong v´o.i chi ph´ı nho˙’ `e b`ai to´an luˆ nhˆa´t (b`ai tˆa.p). T` u. d¯ˆay vˆ `e sau ch´ ung ta chı˙’ x´et d¯`ˆo thi. vˆo hu.´o.ng. Khˆong mˆa´t t´ınh tˆo˙’ng qu´at c´o thˆe˙’ gia˙’ thiˆe´t d¯ı˙’nh xuˆa´t ph´at a v`a d¯ı˙’nh kˆe´t th´ uc b trˆen dˆay chuyˆ ung nhau. Trong tru.`o.ng `en l`a tr` ho..p ngu.o..c la.i, ta chı˙’ cˆ `an thˆem mˆo.t ca.nh (a, b) v´o.i d¯oˆ. d`ai bˇ`a ng khˆong. V´o.i mˆo˜i chu tr`ınh c´o d¯oˆ. d`ai nho˙’ nhˆa´t trˆen d¯`oˆ thi. m´o.i n`ay, tˆ `on ta.i mˆo.t dˆay chuyˆ `en trˆen G c´o c`ung d¯oˆ. d`ai v`a do d¯o´ l`a nho˙’ nhˆa´t. Nˆe´u G l`a d¯`ˆo thi. Euler th`ı tˆ`on ta.i mˆo.t chu tr`ınh Euler d¯i qua mˆo˜i ca.nh d¯u `an ´ng mˆo.t lˆ . v`a v`ı vˆa.y l`a mˆo.t nghiˆe.m tˆo´i u u cu˙’a b`ai to´an. N´oi chung, G khˆong pha˙’i l`a d¯`oˆ thi. Euler, nˆen tˆ `on ta.i mˆo.t sˆo´ c´ac d¯ı˙’nh bˆa.c le˙’. K´y hiˆe.u `an tu˙’. cu˙’a tˆa.p V1 l`a mˆo.t sˆo´ chˇa˜n. Khi V1 l`a tˆa.p c´ac d¯ı˙’nh cu˙’a G c´o bˆa.c le˙’. Dˆ˜e thˆa´y rˇ`a ng sˆo´ phˆ d¯o´ b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa d¯u.a vˆ `e viˆe.c thˆem mˆo.t sˆo´ ca.nh v`ao G d¯ˆe˙’ tro˙’. th`anh d¯`oˆ thi. Euler v`a c` ung l´ uc, cu..c tiˆe˙’u ho´a tˆo˙’ng c´ac tro.ng lu.o..ng cu˙’a c´ac ca.nh d¯u.o..c thˆem v`ao. Ch´ung ta khˆong thˆem mˆo.t ca.nh e0 = (vi , vj ) tr` u. khi d¯˜a tˆ `on ta.i mˆo.t ca.nh e = (vi , vj ) . . trong G v`a g´an tro.ng lu o. ng cu˙’a ca.nh e l`a w(e ) := w(e). Ca.nh e0 go.i l`a ba˙’n sao cu˙’a e. 0 0 X´et mˆo.t l`o.i gia˙’i tˆo´i u.u cu˙’a b`ai to´an v`a d¯aˇ. t E 0 l`a tˆa.p c´ac ca.nh d¯u.o..c thˆem v`ao G. K´ y hiˆe.u G = (V, E + E ) l`a d¯`ˆo thi. Euler nhˆa.n d¯u o. c. 0 0 . . 131 http://www.ebook.edu.vn
Bˆo˙’ d `e 5.2.1 Gia˙’ su˙’. vi l`a mˆo.t d¯ı˙’nh bˆa.c le˙’ trong G. Khi d¯´o tˆa.p E 0 ch´ ¯ˆ u.a mˆo.t dˆay chuyˆ `en . so cˆ . a´p nˆo´i d¯ı˙’nh vi v´o i mˆo.t d¯ı˙’nh vj 6= vi c´o bˆa.c le˙’ trong G. Ch´ u.ng minh. V´o.i mo.i d¯ı˙’nh vk ∈ V1 ta c´o dG (vk ) ≡ 1 (mod 2) v`a dG0 (vk ) ≡ 0 (mod 2); ngo`ai ra, theo c´ach xˆay du..ng dG0 (vk ) ≥ dG (vk ). Do d¯´o tˆ `on ta.i ´ıt nhˆa´t mˆo.t ca.nh e1 ∈ E 0 liˆen thuˆo.c d¯ı˙’nh vi . y hiˆe.u vi1 l`a d¯ı˙’nh kh´ac vi m`a ca.nh e1 liˆen thuˆo.c. Nˆe´u dG (vi1 ) ≡ 1 (mod 2) th`ı bˆo˙’ d¯`ˆe K´ . . u.ng minh v´o.i vj = vi1 . Ngu.o..c la.i, nˆe´u dG (vi1 ) ≡ 0 (mod 2) th`ı dG0 (vi1 ) ≥ dG (vi1 ) + 2 d¯u o. c ch´ v`a tˆ`on ta.i ca.nh e2 ∈ E 0 , e2 6= e1 , liˆen thuˆo.c d¯ı˙’nh vi1 . K´ y hiˆe.u vi2 l`a d¯ı˙’nh kh´ac vi1 m`a ca.nh ˙ ’ . . e2 liˆen thuˆo.c. Nˆe´u dG (vi2 ) ≡ 1 (mod 2) th`ı bˆo d¯`ˆe d¯u o. c ch´ u.ng minh v´o.i vj = vi2 . Ngu.o..c la.i, `on ta.i ca.nh e3 ∈ E , e3 6= e2 , liˆen thuˆo.c d¯ı˙’nh vi2 , v`a vˆan vˆan. tˆ 0 Do d¯o´ ta xˆay du..ng d¯u.o..c mˆo.t dˆay chuyˆ `en so. cˆa´p d`ai nhˆa´t c´o thˆe˙’ (vi , e1 , vi1 , e2 , vi2 , . . . , ep , vip ). Nˆe´u dG (vip ) ≡ 1 (mod 2) th`ı bˆo˙’ d¯`ˆe d¯u.o..c ch´u.ng minh v´o.i vj = vip . Ngu.o..c la.i, tˆ `on ta.i ca.nh 0 . . . ep+1 ∈ E , ep 6= ep+1 , liˆen thuˆo.c d¯ı˙’nh vip v`a vip+1 . Trong tru `o ng ho. p n`ay, tˆ `on ta.i chı˙’ sˆo´ q, 1 ≤ q ≤ p, sao cho viq ≡ vip+1 v`a ta c´o mˆo.t chu tr`ınh xuˆa´t hiˆe.n. Loa.i bo˙’ tˆa´t ca˙’ c´ac ca.nh trong chu tr`ınh n`ay ta d¯u.o..c mˆo.t d¯`ˆo thi. con G00 cu˙’a G0 sao cho n´o vˆa˜n l`a d¯`ˆo thi. Euler v`a ho.n n˜u.a dG00 (vk ) ≥ dG (vk ), v´o.i mo.i d¯ı˙’nh vk ∈ V. Lˇa.p la.i c´ach xˆay du..ng dˆay chuyˆ u. d¯ı˙’nh viq chı˙’ su˙’. du.ng c´ac ca.nh `en trˆen, xuˆa´t ph´at t` cu˙’a G00 . u.u ha.n, nˆen sau mˆo.t sˆo´ h˜ Do sˆo´ c´ac ca.nh trong E 0 l`a h˜ u.u ha.n bu.´o.c ta d¯u.o..c mˆo.t d¯ı˙’nh vip sao cho dG (vip ) ≡ 1 (mod 2) v`a bˆo˙’ d¯`ˆe d¯u.o..c ch´ u.ng minh v´o.i vj = vip . / Bˆ o˙’ d`e 5.2.2 Gia˙’ su˙’. vi v`a vj l`a hai d¯ı˙’nh thoa˙’ m˜an c´ac d¯iˆ ¯ˆ `eu kiˆe.n cu˙’ a Bˆo˙’ d¯`ˆe 5.2.1 v`a k´y . . `en tu o ng u hiˆe.u dˆay chuyˆ . ´ ng l`a µ0 := {e01 , e02 , . . . , e0p } trong d¯´o e0k ∈ E 0 , k = 1, 2, . . . , p. C´ac ca.nh e01 , e02 , . . . , e0p l`a c´ac ba˙’ n sao cu˙’ a c´ac ca.nh `en µ := {e1 , e2 , . . . , ep } trong G. Khi d¯´o µ l`a dˆay e1 , e2 , . . . , ep trong G v`a x´et dˆay chuyˆ chuyˆ `en (trong G) c´o tro.ng lu.o..ng nho˙’ nhˆa´t nˆo´i d¯ı˙’nh vi v´o.i d¯ı˙’nh vj . u.ng minh. Nˆe´u tˆ Ch´ `on ta.i mˆo.t dˆay chuyˆ `en µ¯ = {¯e1 , e¯2 , . . . , e¯q } nˆo´i d¯ı˙’nh vi v´o.i d¯ı˙’nh vj trong G c´o d¯oˆ. d`ai nho˙’ ho.n th`ı bˇ`a ng c´ach loa.i c´ac ca.nh e01 , e20 , . . . , e0p kho˙’i G0 v`a thˆem c´ac ba˙’n sao 132 http://www.ebook.edu.vn
e¯01 , e¯02 , . . . , e¯0q cu˙’a e¯1 , e¯2 , . . . , e¯q ta nhˆa.n d¯u.o..c mˆo.t d¯`ˆo thi. Euler m´o.i c´o tˆo˙’ng tro.ng lu.o..ng nho˙’ ho.n, mˆau thuˆa˜n. / Bˆay gi`o. x´et d¯`ˆo thi. d¯`aˆy d¯u˙’ K(V1 ) trˆen tˆa.p c´ac d¯ı˙’nh V1 trong d¯o´ c´ac ca.nh thˆem v`ao (vi , vj ) c´o tro.ng lu.o..ng wij bˇ`a ng d¯oˆ. d`ai cu˙’a dˆay chuyˆ `en nho˙’ nhˆa´t trong G gi˜ u.a hai d¯ı˙’nh vi . v`a vj . Khi d¯´o mˆo˜i ca.nh cu˙’a K(V1 ) tu o ng u. . . ´ ng v´o i mˆo.t dˆay chuyˆ `en trong G. V`ı w(e) ≥ 0 v´o.i mo.i ca.nh e ∈ E nˆen wij c´o thˆe˙’ d¯u.o..c x´ac d¯.inh bˇ`a ng thuˆa.t to´an t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t, chˇa˙’ng ha.n Floyd (xem 3.3.2) hay Dantzig [16]. - i.nh l´ D y 5.2.3 Tˆ`on ta.i tu.o.ng u´.ng mˆo.t-mˆo.t gi˜u.a l`o.i gia˙’ i tˆo´i u.u cu˙’ a b`ai to´an ngu.`o.i d¯u.a thu Trung Hoa v´o i mˆo.t cˇa.p gh´ep ho`an ha˙’ o c´o tro.ng lu.o..ng nho˙’ nhˆa´t trong d¯`ˆo thi. K(V1 ). . . Ch´ u.ng minh. X´et mˆo.t l`o.i gia˙’i tˆo´i u.u cu˙’a b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa v`a d¯aˇ. t E 0 l`a tˆa.p c´ac ca.nh thˆem v`ao G. Theo Bˆo˙’ d¯`ˆe 5.2.1 ta c´o thˆe˙’ thiˆe´t lˆa.p tu.o.ng u ´.ng v´o.i mˆo˜i d¯ı˙’nh vi ∈ V1 v´o.i mˆo.t d¯ı˙’nh vj ∈ V1 bˇ`a ng mˆo.t dˆay chuyˆ `en so. cˆa´p µij m`a c´ac ca.nh thuˆo.c E 0 . Theo Bˆo˙’ d¯`ˆe 5.2.2, µij c´o d¯oˆ. d`ai nho˙’ nhˆa´t. Trong d¯`oˆ thi. K(V1 ) c´ac dˆay chuyˆ `en µij tu.o.ng u ´.ng ca.nh (vi , vj ). Do d¯o´ tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a V1 d¯u o. c kˆe´t ho. p, hai v´o i hai, v`a c´ac ca.nh (vi , vj ) tu.o.ng . . . . ´.ng dˆay chuyˆ u `en µij cu˙’a G0 , ta.o th`anh mˆo.t cˇa.p gh´ep ho`an ha˙’o K cu˙’a d¯`oˆ thi. K(V1 ). (Trong d¯`oˆ thi. d¯`aˆy d¯u˙’ v´o.i sˆo´ chˇa˜n d¯ı˙’nh luˆon luˆon tˆ`on ta.i mˆo.t cˇa.p gh´ep ho`an ha˙’o; xem Phˆ `an 7.5). . . . . V`ı tro.ng lu o. ng cu˙’a cˇa.p gh´ep ho`an ha˙’o K bˇ`a ng tˆo˙’ng c´ac tro.ng lu o. ng cu˙’a c´ac ca.nh cu˙’a E 0 nˆen l`o.i gia˙’i cu˙’a b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa l`a tˆo´i u.u nˆe´u v`a chı˙’ nˆe´u K l`a mˆo.t cˇa.p gh´ep ho`an ha˙’o v´o.i tro.ng lu.o..ng nho˙’ nhˆa´t. Ta c´o d¯iˆ `eu pha˙’i ch´u.ng minh. / Do d¯o´ nghiˆe.m cu˙’a b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa d¯u.a vˆ `e b`ai to´an t`ım mˆo.t cˇa.p ’ . . ˙ ’ ´ ˙ ’ ` ` gh´ep ho`an hao c´o tro.ng lu o. ng nho nhˆa t cua d¯ˆo thi. d¯ˆay d¯u Kn . Viˆe.c x´ac d¯.inh nghiˆe.m cu˙’a ˙ ˙ ’ u.c ta.p v`a do d¯o´ s˜e khˆong d¯u.o..c tr`ınh b`ay o˙’. d¯ˆay. Ba.n b`ai to´an sau l`a mˆo.t thuˆa.t to´an kh´a ph´ d¯o.c quan tˆam c´o thˆe˙’ tham kha˙’o c´ac t`ai liˆe.u [14], [30]. Nhˆ a.n x´ et 5.2.4 Nˆe´u tˆ `on ta.i ca.nh e trong G sao cho w(e) < 0 th`ı b`ai to´an khˆong c´o nghiˆe.m . ` tˆo´i u u: Thˆa.t vˆa.y, bˇa ng c´ach thˆem mˆo.t tˆa.p E 0 h˜ u.u ha.n c´ac ba˙’n sao cu˙’a c´ac ca.nh cu˙’a G ta c´o thˆe˙’ thˆem ca.nh e mˆo.t sˆo´ chˇa˜n lˆ `an d¯u˙’ l´o n, v`a do d¯o´ nhˆa.n d¯u.o..c mˆo.t d¯`oˆ thi. Euler v´o.i d¯ˆo. . d`ai nho˙’ tu` yy ´. Vˆa.y gia˙’ thiˆe´t c´ac ca.nh c´o tro.ng lu.o..ng khˆong ˆam l`a khˆong mˆa´t t´ınh tˆo˙’ng u. tru.`o.ng ho..p tˆ qu´at d¯ˆe˙’ loa.i tr` `am thu.`o.ng n`ay. V´ı du. 5.2.5 X´et d¯`ˆo thi. trong H`ınh 5.3 v´o.i c´ac sˆo´ trˆen c´ac ca.nh l`a tro.ng lu.o..ng ca.nh. Ta `an t`ım mˆo.t chu tr`ınh qua mˆo˜i ca.nh ´ıt nhˆa´t mˆo.t lˆ cˆ `an v`a c´o d¯ˆo. d`ai nho˙’ nhˆa´t. Tˆo˙’ng c´ac tro.ng lu.o..ng c´ac ca.nh cu˙’a G bˇ`a ng 31. V`ı G khˆong l`a d¯`oˆ thi. Euler nˆen d¯ˆo. d`ai cu˙’a chu tr`ınh cˆ`an t`ım s˜e l´o.n ho.n 31. 133 http://www.ebook.edu.vn
3 6...m ......................................................................................... m 2... ........ .. .. ..... ... ... ..... ..... .. .. ..... ... ... ..... 4 ... ... 1 ... ... ..... ..... ..... ..... 2 ... ... ..... ... ... ..... ..... ... ... ..... ... ... ..... . 3 2 . ..... 1...m ......................................................................................... m 7... ...................................................... .... 3m .. .. ..... ... ... ..... .. .. . .. ...... ... ... ..... .... ... ... ..... 2 ... ... ... 4 ... ... ... ...... ....... ..... 3 ..... ... ... ..... ... ... ..... ..... .. 7 .. . ... . .. 5m ......................................................................................... m 4 H`ınh 5.3: Tˆa.p c´ac d¯ı˙’nh bˆa.c le˙’ l`a V1 = {1, 2, 3, 4}. Theo thuˆa.t to´an t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t (xem Chu.o.ng 3), ta t`ım tˆa´t ca˙’ c´ac dˆay chuyˆ u.a c´ac cˇa.p d¯ı˙’nh cu˙’a V1 trong `en c´o d¯ˆo. d`ai nho˙’ nhˆa´t gi˜ . . . . G. Ta nhˆa.n d¯u o. c m`a trˆa.n d¯ˆo. d`ai d¯u `o ng d¯i ngˇa´n nhˆa´t: 1 2 3 4   1 0 4 5 7 2 4 0 2 5  . 35 2 0 3 4 7 5 3 0 Tiˆe´p d¯ˆe´n ta xˆay du..ng d¯`oˆ thi. d¯`aˆy d¯u˙’ K(V1 ) trong d¯´o tro.ng lu.o..ng ca.nh (vi , vj ) l`a d¯oˆ. d`ai cu˙’a dˆay chuyˆ `en ngˇa´n nhˆa´t gi˜u.a vi v`a vj (xem H`ınh 5.4). 4 1...m ......................................................................................... m ..... ... .... .... ... 2 ... ..... . ... ..... ..... ... ..... ..... ... .. ..... ..... .. ... ..... ........ . ... ..... .. ... ..... ..... ... ... ..... .... ... ..... ..... ... ..... ..... ... ... ..... ........ ... 7 ... ... ... ..... ....... ......... ..... ........ ..... ... ... ... 2 ... . .... . ..... ... ... ... 5 ..... . . ...... . ..... . ..... ..... ..... ..... 5 ... ... ... ...... ..... ... ... . . .. ..... ... ... ....... ..... ... . . .. .... . 3 ..... ... . 4m ......................................................................................... 3m - `ˆo thi. d¯`ˆay d¯u˙’ K(V1 ). H`ınh 5.4: D Cˇa.p gh´ep ho`an ha˙’o v´o.i tro.ng lu.o..ng nho˙’ nhˆa´t trˆen K(V1 ) gˆ `om c´ac ca.nh (1, 2) v`a (3, 4) . . ` ` . (tro.ng lu o. ng bˇa ng 4 + 3 = 7). C´ac dˆay chuyˆen tu o ng u . . ´ ng l`a {1, 7, 2} v`a {3, 4}. Nghiˆe.m tˆo´i u.u cu˙’a b`ai to´an nhˆa.n d¯u.o..c bˇ`a ng c´ach thˆem v`ao d¯`ˆo thi. ban d¯`ˆau c´ac ca.nh - `ˆo thi. G0 nhˆa.n d¯u.o..c l`a d¯`ˆo thi. Euler (H`ınh 5.5). (1, 7), (7, 2) v`a (3, 4). D 134 http://www.ebook.edu.vn
6...m ......................................................................................... m ... 2 ... ... ... ..... . . . ..... .... ... .... ..... ..... ... ... ... ..... .. .. . .. ..... ... ... ... ..... ..... ... ..... ... ..... ... ... ... ... ..... ..... ... ... ... ..... ... ................................................ .... ... ..... ..... ... ............ ... ... .......... .. ..... .. ................ .......... . .. ..... 1m .. ......................................................................................... 7..m ...................................................... 3m ... ..... .. .... .... ..... ... ... ... ......... ... ... ... ... .. ..... ... ... ... ..... ... ... ....... . . .... ... ... .... ... ..... .... ... ... ..... ..... ... ... ..... ..... .... .... . ....... . .......... .. .. .. .. ..... ....... .... ............. 5m ......................................................................................... m . 4 ........ H`ınh 5.5: D- `ˆo thi. Euler G0 nhˆa.n d¯u.o..c t` u. G bˇ`a ng c´ach thˆem c´ac ca.nh tu.o.ng u ´.ng c´ac dˆay `en nho˙’ nhˆa´t gi˜ chuyˆ u.a 1 v`a 2 v`a gi˜ u.a 3 v`a 4. Cuˆo´i c` `an t`ım mˆo.t chu tr`ınh Euler trong G0 , chˇa˙’ng ha.n ung ta chı˙’ cˆ {6, 2, 3, 7, 2, 7, 1, 7, 4, 5, 1, 6} l`a chu tr`ınh c´o d¯ˆo. d`ai 31 + 7 = 38 l`a nghiˆe.m tˆo´i u.u cˆ `an t`ım. 5.3 B` ai to´ an Hamilton Gia˙’ su˙’. G := (V, E) l`a d¯`oˆ thi. liˆen thˆong (hay liˆen thˆong ma.nh trong tru.`o.ng ho..p c´o hu.´o.ng) c´o n d¯ı˙’nh. D- i.nh ngh˜ıa 5.3.1 Dˆay chuyˆ `en (hay d¯u.`o.ng d¯i) d¯i qua tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a d¯`oˆ thi. G, mˆo˜i `en Hamilton (hay d¯u.`o.ng d¯i Hamilton). `an, go.i l`a dˆay chuyˆ d¯ı˙’nh mˆo.t lˆ `en (hay d¯u.`o.ng d¯i Hamilton) l`a so. cˆa´p, v`a c´o d¯ˆo. d`ai (n − 1). Theo d¯.inh ngh˜ıa, dˆay chuyˆ Chu tr`ınh (hay ma.ch) Hamilton l`a mˆo.t chu tr`ınh (hay ma.ch) d¯i qua tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a d¯`oˆ thi. G, mˆo˜i d¯ı˙’nh d¯u `an. Dˆ˜e thˆa´y rˇ`a ng, chu tr`ınh Hamilton l`a chu tr`ınh so. cˆa´p ´ng mˆo.t lˆ c´o d¯oˆ. d`ai n. Ta n´oi rˇa` ng, G l`a d¯`ˆo thi. Hamilton nˆe´u n´o ch´ u.a mˆo.t chu tr`ınh Hamilton (trong tru.`o.ng ho..p vˆo hu.´o.ng) hoˇa.c mˆo.t ma.ch Hamilton (trong tru.`o.ng ho..p c´o hu.´o.ng). V´ı du. 5.3.2 Nˇam 1859, nh`a to´an ho.c Hamilton (1805-1865) ngu.`o.i Ailen d¯˜a cho b´an mˆo.t d¯`oˆ cho.i d¯oˆ. c d¯´ao, phˆ `an ch´ınh l`a mˆo.t khˆo´i nhi. diˆe.n d¯`ˆeu (khˆo´i d¯a diˆe.n c´o 12 mˇa.t ng˜ u gi´ac d¯`ˆeu . v`a 20 d¯ı˙’nh, mˆo˜i d¯ı˙’nh c´o 3 ca.nh) l`am bˇ`a ng gˆo˜. O mˆo˜i d¯ı˙’nh c´o ghi tˆen mˆo.t th`anh phˆo´ l´o.n: ˙ ’ Beruych, Qua˙’ng chˆau, Deli, Frangfua, v.v... C´ach cho.i l`a t`ım mˆo.t d¯u.`o.ng d¯i do.c theo c´ac 135 http://www.ebook.edu.vn
ca.nh cu˙’a thˆa.p nhi. diˆe.n d¯`ˆeu v`a qua mˆo˜i d¯ı˙’nh (th`anh phˆo´) v` u.a d¯u´ng mˆo.t lˆ`an. Muˆo´n tr`o cho.i . . . . . . d¯u o. c hˆa´p dˆa˜n ho n c´o thˆe˙’ quy d¯.inh tru ´o c tr`ınh tu. qua mˆo.t v`ai th`anh phˆo´ d¯`ˆau tiˆen, v`a d¯ˆe˙’ gi´up nh´o. dˆ˜e d`ang c´ac th`anh phˆo´ d¯a˜ d¯i qua, o˙’. mˆo˜i d¯ı˙’nh cu˙’a khˆo´i thˆa.p nhi. diˆe.n d¯`ˆeu c´o d¯´ong mˆo.t chiˆe´c d¯inh m˜ u to, quanh d¯´o c´o thˆe˙’ quˆa´n so..i dˆay nho˙’ d¯ˆe˙’ chı˙’ d¯oa.n d¯u.`o.ng d¯a˜ d¯i qua. Vˆ `e . sau d¯ˆe˙’ d¯o n gia˙’n, Hamilton d¯˜a thay khˆo´i thˆa.p nhi. diˆe.n d¯`ˆeu bˇ`a ng mˆo.t h`ınh phˇa˙’ng. B`ai to´an d¯u.o..c ph´at biˆe˙’u du.´o.i da.ng d¯`ˆo thi. nhu. sau. Ta biˆe´t rˇ`a ng h`ınh thˆa.p nhi. diˆe.n d¯`ˆeu c´o 12 mˇa.t, 30 ca.nh, 20 d¯ı˙’nh; mˆo˜i mˇa.t l`a mˆo.t ng˜ u gi´ac d¯`ˆeu, mˆo˜i d¯ı˙’nh l`a d¯`aˆu m´ ut cu˙’a 3 ca.nh. C´ac d¯ı˙’nh . v`a c´ac ca.nh cu˙’a h`ınh thˆa.p nhi. diˆe.n d¯`ˆeu lˆa.p th`anh mˆo.t d¯`oˆ thi. nhu H`ınh 5.6. B`ai to´an d¯ˇa.t ra l`a h˜ay t`ım mˆo.t chu tr`ınh Hamilton cu˙’a d¯`ˆo thi. G. • .................................................................................................................................................... ... .... • ... ... ... ... ... .. .. .... .. ..... . . .. ... . ... ... ... ... ... ... ... ... ... ... .. .. ... ... ... . . ... .. ... . .. ... . .. . .. . .. • ... .. . .. . .. ..... .... ... .. . . . .. .... ..... . ..... ..... ........• .... ... ... ... ... .......... ..... . . ..... .... . ..... • . ..... . ... ... ... ... ... . . ... ... .. . .. . ... ... ... .. .. . .. .. . . . .. .. . ... ..... • ...... .... ......... . . ... . ... ... ... ... .. . .. . . . •. . ........ .. ........... ................ ............. ....... ...... ......... .. . ...... ....... .. . .. . • .. ... . ..... ... . ... ... . . .. . .. .. .. . . .. . .. . • ... ... . • . . . . . . . . . . .. . ... .... ... . ... ... ... ... .. .. ... .. ... ... . . ... . ... .. .. .. ... . . .. . .. . ..... ...• .. . .... ..... .......... . ... ... . .. . .. . . ..... •. . .... . . . . .... ............ ... ... ... . .. . .. ............. ............ ...... ........ ...... ...... ...... . ......• .. ... ..... . ..... ..... ..... ... ... ... ... .....• ..... . . . . ..... . ...... ...... .. .. ..... ......... ....... .. ........ .. . . .. ....... ..... • ............... ....... ....... ....... • ...... ...... ...... ...... ...... ......• . . ..... . ... ....... .. . ..• ........ . ... ...... ...... ....... ....... ....... ...... . .. ........ .. ......... ....... ....... ....... ....... • ...... ..... .... ... . ....... ...... ....... ....... . ....... ... ...... ....... . . .. . .. ....... .... ..... ....... ....... ....... ... ....... ....... ... ....... ....... . . ............ ....... .. ....... ....... .. ....... • ........... H`ınh 5.6: H`anh tr`ınh xung quanh thˆe´ gi´o.i (khˆo´i thˆa.p nhi. diˆe.n d¯`ˆeu) cu˙’a Hamilton. V´ı du. 5.3.3 (B`ai to´an ngu.`o.i ch`ao h`ang). Mˆo.t ngu.`o.i ch`ao h`ang viˆe´ng thˇam n kh´ach h`ang v1 , v2 , . . . , vn , xuˆa´t ph´at t` u. th`anh phˆo´ v0 v`a sau d¯o´ tro˙’. vˆ `e vi. tr´ı xuˆa´t ph´at. Anh ta biˆe´t khoa˙’ng c´ach d0j t` . u v0 d¯ˆe´n tˆa´t ca˙’ c´ac kh´ach h`ang vj v`a khoa˙’ng c´ach dij gi˜u.a hai kh´ach h`ang vi v`a vj (d¯ˇa.t dij = dji ). Ngu.`o.i ch`ao h`ang cˆ `an d¯i d¯ˆe´n c´ac kh´ach h`ang cu˙’a m`ınh theo th´ u. tu.. n`ao d¯ˆe˙’ tˆo˙’ng qu˜ang . . d¯u `o ng d¯i l`a nho˙’ nhˆa´t? N´oi c´ach kh´ac cˆ `an t`ım mˆo.t chu tr`ınh Hamilton v´o.i d¯ˆo. d`ai nho˙’ nhˆa´t trˆen d¯`oˆ thi. d¯`ˆay d¯u˙’ c´o tro.ng sˆo´ d¯u.o..c xˆay du..ng t`u. tˆa.p c´ac d¯ı˙’nh v0 , v1 , v2 , . . . , vn , v`a tro.ng . . lu o. ng ca.nh (vi , vj ) l`a dij . Vˆ `e c´ac thuˆa.t to´an gia˙’i b`ai to´an n`ay c´o thˆe˙’ xem, chˇa˙’ng ha.n [30]. Trong tru.`o.ng ho..p d¯ı˙’nh cuˆo´i vn+1 kh´ac d¯ı˙’nh xuˆa´t ph´at v0 , b`ai to´an d¯u.a vˆ `e t`ım dˆay ` chuyˆen Hamilton t` . ´ ˙ ’ ´ ` ´ ˙ ’ u v0 d¯ˆen vn+1 c´o tˆo ng d¯ˆo. d`ai nho˙’ nhˆa t. Bˇa ng c´ach biˆen d¯oˆ i mˆo.t c´ach th´ıch ho..p trˆen d¯`oˆ thi., ta c´o thˆe˙’ d¯u.a vˆ `e b`ai to´an t`ım chu tr`ınh Hamilton c´o tˆo˙’ng d¯ˆo. d`ai nho˙’ nhˆa´t. 136 http://www.ebook.edu.vn
V´ı du. 5.3.4 (B`ai to´an lˆa.p li.ch). Trong mˆo.t sˆo´ b`ai to´an lˆa.p li.ch, ta cˆ `an t`ım mˆo.t th´u. tu.. . . . . . . thu. c hiˆe.n n tiˆe´n tr`ınh cho tru ´o c (hai tiˆe´n tr`ınh khˆong d¯u o. c thu. c hiˆe.n c` uc) v`a thoa˙’ ung mˆo.t l´ m˜an nh˜ . . u ng r`ang buˆo.c nhˆa´t d¯.inh; bˇa` ng c´ach xˆay du. ng d¯`oˆ thi. G trong d¯´o tˆa.p c´ac d¯ı˙’nh cu˙’a . . G tu o ng u ´.ng v´o.i tˆa.p c´ac tiˆe´n tr`ınh v`a mˆo.t cung liˆen thuˆo.c hai d¯ı˙’nh vi v`a vj nˆe´u tiˆe´n tr`ınh i d¯u o. c thu..c hiˆe.n tru.´o.c tiˆe´n tr`ınh j, b`ai to´an d¯u.a vˆ . . `e t`ım mˆo.t d¯u.`o.ng d¯i Hamilton trong G. V´ı du. 5.3.5 (Lˆa.p li.ch v`a b`ai to´an ngu.`o.i ch`ao h`ang trˆen d¯`oˆ thi. c´o hu.´o.ng). Trong thu..c tˆe´ ta thu.`o.ng lˆa.p kˆe´ hoa.ch m`a mˆo˜i cung (vi , vj ), biˆe˙’u diˆ˜en mˆo.t r`ang buˆo.c n`ao d¯o´, gˇa´n v´o.i mˆo.t sˆo´ thu..c tij l`a khoa˙’ng th`o.i gian ´ıt nhˆa´t c´o thˆe˙’ bˇa´t d¯`ˆau thu..c hiˆe.n cˆong viˆe.c th´ u. j khi cˆong viˆe.c th´u. i d¯a˜ tiˆe´n h`anh. Th`o.i gian nho˙’ nhˆa´t d¯ˆe˙’ thu..c hiˆe.n tˆa´t ca˙’ c´ac tiˆe´n tr`ınh d¯u.o..c x´ac d¯i.nh bˇa` ng c´ach t`ım mˆo.t d¯u.`o.ng d¯i Hamilton c´o d¯ˆo. d`ai nho˙’ nhˆa´t trˆen d¯`oˆ thi. c´o hu.´o.ng. D - ˆay ch´ınh l`a b`ai to´an . . . . ngu `o i ch`ao h`ang trˆen d¯`oˆ thi. c´o hu ´o ng. Vˆ `e thuˆa.t to´an gia˙’i b`ai to´an n`ay c´o thˆe˙’ xem, chˇa˙’ng ha.n [30]. B`ai to´an ngu.`o.i ch`ao h`ang trˆen d¯`ˆo thi. vˆo hu.´o.ng hoˇa.c c´o hu.´o.ng thu.`o.ng gˇa.p trong cuˆo.c sˆo´ng v`a c´o nhiˆ ´.ng du.ng: lˆa.p th`o.i kho´a biˆe˙’u, lˆa.p li.ch, lˇa´p d¯aˇ. t hˆe. thˆo´ng d¯iˆe.n, tˆo˙’ng ho..p `eu u c´ac ma.ch logic tuˆ`an tu.., v.v. `eu b`ai to´an c´o thˆe˙’ d¯u.a vˆ Ngo`ai ra, nhiˆ `e b`ai to´an ngu.`o.i ch`ao h`ang: b`ai to´an nhiˆ `eu ngu.`o.i ch`ao h`ang, mˆo.t v`ai b`ai to´an t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t v´o.i d¯iˆ `eu kiˆe.n qua tˆa´t ca˙’ c´ac d¯ı˙’nh (hay ˙ ’ . . ˙ ’ ` cung) cua mˆo.t tˆa.p cho tru ´o c chı mˆo.t lˆan, c´ac chu tr`ınh (hay ma.ch) Euler c´o chi ph´ı nho˙’ nhˆa´t. ung, ta c´o thˆe˙’ chı˙’ ra rˇ`a ng, b`ai to´an ngu.`o.i ch`ao h`ang trˆen d¯`oˆ thi. c´o hu.´o.ng c´o Cuˆo´i c` . `e tru.`o.ng ho..p d¯`ˆo thi. vˆo hu.´o.ng. thˆe˙’ d¯u a vˆ Tr´ai v´o.i b`ai to´an ngu.`o.i d¯u.a thu. Trung Hoa, ngoa.i tr` u. nh˜ u.ng tru.`o.ng ho..p d¯ˇa.c biˆe.t, ngu.`o.i ta chu.a t`ım d¯u.o..c mˆo.t thuˆa.t to´an d¯a th´u.c d¯ˆe˙’ gia˙’i b`ai to´an ngu.`o.i ch`ao h`ang. C´ac . . . thuˆa.t to´an hiˆe.u qua˙’ nhˆa´t su˙’ du.ng c´ac phu o ng ph´ap nh´anh v`a cˆa.n [30]. - i.nh ngh˜ıa 5.3.6 Mˆo.t chu tr`ınh (tu.o.ng u D ´.ng, ma.ch) d¯i qua tˆa´t ca˙’ c´ac d¯ı˙’nh, mˆo˜i d¯ı˙’nh ´ıt nhˆa´t mˆo.t lˆ . . `an, go.i l`a chu tr`ınh (tu o ng u . `en Hamilton. D ´ ng, ma.ch) tiˆ - `ˆo thi. G ch´ u.a mˆo.t chu tr`ınh hay ma.ch nhu. vˆa.y go.i l`a d¯`oˆ thi. tiˆ `en Hamilton. Dˆ˜e thˆa´y rˇ`a ng, d¯iˆ `an v`a d¯u˙’ d¯ˆe˙’ `eu kiˆe.n cˆ ` ` G l`a d¯oˆ thi. tiˆen Hamilton l`a G liˆen thˆong (liˆen thˆong ma.nh). T`ım kiˆe´m mˆo.t chu tr`ınh (hay ma.ch) Hamilton c´o d¯oˆ. d`ai nho˙’ nhˆa´t trˆen d¯`oˆ thi. c´o tro.ng . `e b`ai to´an x´ac d¯i.nh chu tr`ınh (hay ma.ch) trong d¯`oˆ thi. d¯`aˆy d¯u˙’ G0 nhˆa.n d¯u.o..c tˆa.p sˆo´ d¯u a vˆ 137 http://www.ebook.edu.vn
c´ac d¯ı˙’nh cu˙’a G v`a tro.ng lu.o..ng trˆen ca.nh (cung) (vi , vj ) cu˙’a G0 bˇ`a ng d¯ˆo. d`ai cu˙’a dˆay chuyˆ `en . . (d¯u `o ng d¯i) ngˇa´n nhˆa´t t`. u vi d¯ˆe´n vj trong G. `eu da.ng b`ai to´an ngu.`o.i ch`ao h`ang ch´ınh l`a c´ac b`ai to´an tiˆ Nhiˆ `en Hamilton, v`a d¯ˆe˙’ gia˙’i ung tru.´o.c hˆe´t ta cˆ ch´ `an t`ım ma trˆa.n tu.o.ng u ´.ng c´ac dˆay chuyˆ `en (d¯u.`o.ng d¯i) ngˇa´n nhˆa´t. Cuˆo´i c`ung nhˆa.n x´et rˇa` ng, tˆ `on ta.i mˆo.t tru.`o.ng ho..p m`a b`ai to´an chu tr`ınh tiˆ `en Hamilton ˙ ’ . c´o d¯oˆ. d`ai nho˙’ nhˆa´t c´o thˆe d¯u a vˆ . . . . `e b`ai to´an ngu `o i d¯u a thu Trung Hoa; d¯iˆ `eu n`ay xa˙’y ra khi G l`a d¯`ˆo thi. d¯ˆo´i ngˆa˜u1 cu˙’a d¯o.n d¯`oˆ thi. vˆo hu.´o.ng G∗ n`ao d¯´o v`a khi d¯ˆo. d`ai cu˙’a c´ac ca.nh (vi , vj ) c´o da.ng ai + aj . Trong tru.`o.ng ho..p n`ay, b`ai to´an t`ım chu tr`ınh tiˆ `en Hamilton trong G ch´ınh . . . . . l`a b`ai to´an ngu `o i d¯u a thu Trung Hoa trong G v´o i d¯oˆ. d`ai ca.nh e∗i cu˙’a G∗ l`a ai . ∗ Nhˆa.n x´et tu.o.ng tu.. cho b`ai to´an t`ım ma.ch tiˆ `en Hamilton c´o d¯ˆo. d`ai nho˙’ nhˆa´t trong tru `o ng ho. p d¯`ˆo thi. c´o hu ´o ng G l`a d¯`ˆo thi. d¯ˆo´i ngˆau cu˙’a d¯a d¯`oˆ thi. c´o hu.´o.ng n`ao d¯´o. . . . . . ˜ 5.3.1 C´ ac d `eu kiˆ ¯iˆ `an d e.n cˆ ¯ˆe˙’ tˆ `on ta.i chu tr`ınh Hamilton Hiˆe˙’n nhiˆen rˇa` ng, mˆo.t d¯iˆ `an d¯ˆe˙’ tˆ `eu kiˆe.n cˆ `on ta.i chu tr`ınh Hamilton l`a G 2-liˆen thˆong. Tuy ˙ ’ ` nhiˆen, d¯ˆay khˆong phai d¯iˆeu kiˆe.n d¯u. ˙ ’ H`ınh 5.7 l`a mˆo.t v´ı du. d¯`ˆo thi. 2-liˆen thˆong khˆong ch´ u.a chu tr`ınh Hamilton (ho.n n˜ u.a, c´o thˆe˙’ chı˙’ ra rˇ`a ng, d¯´o l`a d¯`ˆo thi. c´o sˆo´ d¯ı˙’nh ´ıt nhˆa´t thoa˙’ m˜an t´ınh chˆa´t n`ay). ...... • .......... ...... ........... ...... ...... ...... .. . . . ...... ...... . ...... ...... ...... . .. . ...... . ...... . . . . ..... ...... ...... . ... . .... ...... .. .. ..... ...... ...... . .. . .... . ...... ..... . ...... ... ...... .. ....... ...... ...... ........ . ...... .... .... • . .... ...... ...... ...... • .................................................................................................................................................................................................................................... ...... • . ...... ...... .. .... ...... ...... ...... ........... ...... . ...... ...... ...... ...... ...... ...... ...... ...... ...... . .. . ....... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... . .......... ...... . ...... ........... • ..... - `ˆo thi. 2-liˆen thˆong c´o sˆo´ d¯ı˙’nh ´ıt nhˆa´t khˆong c´o chu tr`ınh Hamilton. H`ınh 5.7: D - `ˆo thi. vˆo hu.´o.ng Petersen (H`ınh 5.8) l`a v´ı du. kh´ac khˆong c´o chu tr`ınh Hamilton. D D - ˆay l`a d¯`ˆo thi. ch´ınh quy 3-liˆen thˆong nho˙’ nhˆa´t c´o tˆa´t ca˙’ c´ac d¯ı˙’nh bˆa.c ba. Nhiˆ `eu pha˙’n v´ı du. vˆ`e . . . b`ai to´an Hamilton d¯u o. c xˆay du. ng t` . ` u d¯ˆo thi. Petersen. Dˆo thi. vˆo hu.´o.ng G∗ l`a d¯`ˆo thi. d¯ˆo´i ngˆa˜u cu˙’a G = (V, E) nˆe´u mˆo˜i d¯ı˙’nh cu˙’a G∗ tu.o.ng u 1- ` ´.ng v´o.i mˆo.t ca.nh e ∈ E v`a hai d¯ı˙’nh trong G kˆ ∗ . `e nhau nˆe´u hai ca.nh tu o ng u. . ´ ng kˆ `e nhau. D . . - `ˆo thi. c´o hu ´o ng G∗ l`a d¯`ˆo thi. d¯ˆo´i ngˆa˜u cu˙’a G = (V, E) nˆe´u mˆo˜i d¯ı˙’nh e cu˙’a G tu o ng u ∗ ∗ . . . . ´ ng v´o i mˆo.t cung e ∈ E v`a tˆ `on ta.i cung (e∗1 , e∗2 ) trong ∗ ´ G nˆeu d¯ı˙’nh ngo.n cu˙’a cung e1 l`a d¯ı˙’nh gˆo´c cu˙’a cung e2 . 138 http://www.ebook.edu.vn
• ........... ...... .. ...... ...... .... ........... ...... ... ...... ........... ... ...... . ...... ...... ... ...... .. .. ....... . . ...... ...... ......... . . . ...... ........ . .. . ...... ...... . ... .... .... ...... ...... . ...... ... . . ... . . .... . ...... . . .. ...... . . • .. . ..... . ... .. ...... ...... ...... ...... ...... ..... . . .... ...... • . ... ... . .............. ... ............. ............. .. . .. . . . ... ... . ... ...... . .. ... ... . •. ........ .............. ... .......... .. . . ...... .. . ... .................................................................................... .. ... ... ... • .......... . .. ... .. ........... .. ....... .... .. .. . . .. .. . . ..... .. .. . . . ... .. ... ... ...... • ...... ... ... . . ... ....... ....... .... ... ....... ... ........ ... ........... .. .. ... ...... . ... ... . . .. . ... ... ............ ....... ..... ... ... ... ... ....... ............ ... ... ... ........ ... ... ... ... .. ............ ............ ... . .. . ... ....... .. ... ... ... ......... ....... ... . ... ............ ......... ... ... ... ... .. • .. ..... • ....... ... . ... . . .. .. ... ... ... ... ... ... ... .. ... ... .... ... ... ... .. ... .... ... ... ... .. . •................................................................................................................... • - `ˆo thi. Petersen. H`ınh 5.8: D C´o nhiˆ`eu d¯iˆ `an kh´ac (xem [30], [14]) nhu.ng khˆong c´o mˆo.t d¯iˆ `eu kiˆe.n cˆ `eu kiˆe.n cˆ `an v`a d¯u˙’ vˆ . `e su. tˆ`on ta.i chu tr`ınh (ma.ch) Hamiton. Do d¯o´ ch´ `eu kiˆe.n d¯u˙’ dˆa˜n d¯ˆe´n c´ac phu.o.ng ph´ap c´o t´ınh ung ta s˜e tˆa.p trung mˆo.t sˆo´ d¯iˆ . xˆay du. ng chu tr`ınh Hamilton. 5.3.2 C´ ac d `eu kiˆ ¯iˆ e.n d `e su.. tˆ ¯u˙’ vˆ `on ta.i chu tr`ınh Hamilton Mˆ e.nh d`e 5.3.7 Kn l`a d¯`ˆo thi. Hamilton. ¯ˆ u.ng minh. Hiˆe˙’n nhiˆen. Ch´ / X´et d¯`oˆ thi. vˆo hu.´o.ng n d¯ı˙’nh G := (V, E). Gia˙’ su˙’. s v`a t l`a hai d¯ı˙’nh khˆong kˆ `e nhau sao cho dG (s) + dG (t) ≥ n. y hiˆe.u G + (s, t) l`a d¯`ˆo thi. nhˆa.n d¯u.o..c t` K´ u. G bˇ`a ng c´ach thˆem ca.nh (s, t). Khi d¯o´ Mˆ e.nh d `e 5.3.8 Nˆe´u G + (s, t) l`a d¯`ˆo thi. Hamilton th`ı G l`a d¯`ˆo thi. Hamilton. Ta n´oi t´ınh ¯ˆ chˆa´t n`ay l`a ˆo˙’n d¯.inh Hamilton qua ph´ep biˆe´n d¯ˆo˙’i G → G + (s, t). Ch´ u.ng minh. Gia˙’ su˙’. G + (s, t) ch´u.a chu tr`ınh Hamilton µ := (v1 , v2 , . . . , vn ). Nˆe´u µ khˆong d¯i qua ca.nh (s, t) th`ı G l`a Hamilton. Ngu.o..c la.i, G ch´ u.a mˆo.t dˆay chuyˆ `en Hamilton µ \ (s, t) ˙ ’ ˙ ’ nˆo´i s v`a t. (Khˆong mˆa´t t´ınh tˆo ng qu´at, c´o thˆe gia˙’ thiˆe´t s = v1 , t = vn ). 139 http://www.ebook.edu.vn
u.ng minh rˇ`a ng tˆ Ta ch´ `e v´o.i vi v`a t kˆ `on ta.i ´ıt nhˆa´t mˆo.t chı˙’ sˆo´ i, 3 ≤ i ≤ n, sao cho s kˆ `e . v´o i vi−1 . Thˆa.t vˆa.y, x´et c´ac tˆa.p con cu˙’a tˆa.p Y := {v3 , v4 , . . . , vn−1 } : A = {vi | (s, vi ) ∈ E v`a 3 ≤ i ≤ n − 1}, B = {vi | (t, vi−1 ) ∈ E v`a 3 ≤ i ≤ n − 1}. `e nhau trong G nˆen V`ı s v`a t khˆong kˆ #A + #B = dG (s) + dG (t) − 2 ≥ n − 2 v`a nhˆa.n x´et rˇ`a ng #Y = n − 3 suy ra tˆ `on ta.i vi ∈ A ∩ B (3 ≤ i ≤ n − 1). Do d¯´o, thˆem c´ac ca.nh (s, vi ) v`a (t, vi−1 ) v`a xo´a ca.nh (vi , vi−1 ) ta d¯u.o..c mˆo.t chu tr`ınh Hamilton trong G (xem H`ınh 5.9), v`a mˆe.nh d¯`ˆe d¯u.o..c ch´ u.ng minh. / v2 v3 v2 v3 • ..... • ............................................. ..... ..... ..... • ..... ..... • ............................................. ..... ..... . ........ ..... . ........ ..... .... ..... .... ..... . .. ..... ... ..... ....... ..... . ...... ..... . .... ..... . .... ..... s = v1 • .. ......... .. .. ..... .... .... • v1 • .. ......... .. ..... ..... ..... .... ... .... • ..... .. .... ..... ... ..... .. ..... .. .... .. −→ ..... ..... ..... ..... ..... ... ... ..... ... • vi−1 • vi−1 .. t = vn • .......... ....... ....... ............ ....... ....... ....... ....... ........... ..... ..... .. ....... .. .. ... .. . t = vn • ..... ..... ..... .................................................................................................................. ..... ..... ....... ..... .... ..... ..... ..... ..... ..... ..... .... .. ..... ..... ..... ..... ..... ..... .. ..... ..... ..... .. ..... ..... ..... . .. ...... ..... ..... ..... ..... ..... .. .... • ..... • ........................................ • ..... • .. .. .......................................... vi vi H`ınh 5.9: Gia˙’ su˙’. G l`a d¯o.n d¯`ˆo thi. n d¯ı˙’nh v`a k l`a sˆo´ nguyˆen thoa˙’ 1 ≤ k ≤ n. X´et thu˙’ tu.c d¯ˆe. quy sau: Xuˆa´t ph´at t` u. G, thˆem c´ac ca.nh nˆo´i c´ac d¯ı˙’nh khˆong kˆ `e nhau m`a tˆo˙’ng c´ac bˆa.c cu˙’a ch´ ung l´o n ho n hoˇa.c bˇa ng k. (Sˆo ph´ep to´an d¯`oi hoi trong thu tu.c n`ay tı˙’ lˆe. v´o.i n4 ). V`ı c´ac . . ` ´ ˙ ’ ˙ ’ bˆa.c khˆong gia˙’m, d¯`oˆ thi. nhˆa.n d¯u.o..c khˆong phu. thuˆo.c v`ao th´ u. tu.. c´ac ca.nh d¯u.o..c thˆem. D - `ˆo thi. n`ay (ch´ . u a G) go.i l`a k−bao d¯o´ng cu˙’a G v`a k´ . y hiˆe.u l`a [G]k . V´o i k = n, t` . u Mˆe.nh d¯`ˆe 5.3.8 suy ra - .inh l´ D y 5.3.9 [8] G l`a d¯`ˆo thi. Hamilton nˆe´u v`a chı˙’ nˆe´u [G]n l`a d¯`ˆo thi. Hamilton. Trong tru.`o.ng ho..p tˆo˙’ng qu´at, t`ım chu tr`ınh Hamilton trong [G]n khˆong pha˙’i l´ uc n`ao ung dˆ˜e ho.n trong G. Tuy nhiˆen, v´o.i nh˜ c˜ u.ng tru.`o.ng ho..p d¯aˇ. c biˆe.t, chˇa˙’ng ha.n khi [G]n l`a d¯`ˆo thi. d¯`aˆy d¯u˙’ Kn ta c´o thˆe˙’ dˆ˜e d`ang xˆay du..ng chu tr`ınh Hamilton trong [G]n : 140 http://www.ebook.edu.vn
- .inh l´ D - iˆ y 5.3.10 D `eu kiˆe.n d¯u˙’ d¯ˆe˙’ G l`a d¯`ˆo thi. Hamilton l`a [G]n = Kn . C´o thˆe˙’ chı˙’ ra rˇ`a ng hˆ `eu kiˆe.n d¯u˙’ d¯˜a biˆe´t (d¯u.o..c liˆe.t kˆe du.´o.i d¯aˆy) liˆen quan `au hˆe´t c´ac d¯iˆ d¯ˆe´n bˆa.c cu˙’a G suy ra [G]n = Kn v`a do d¯´o l`a c´ac hˆe. qua˙’ cu˙’a D - i.nh l´ y 5.3.10. Gia˙’ su˙’. G l`a d¯o.n d¯`ˆo thi. liˆen thˆong n d¯ı˙’nh. e. qua˙’ 5.3.11 [Ore] [47] Nˆe´u dG (vi ) + dG (vj ) ≥ n v´o.i mo.i (vi , vj ) ∈ Hˆ / E th`ı G l`a d¯`oˆ thi. Hamilton. e. qua˙’ 5.3.12 [Dirac] [17] Nˆe´u dG (vi ) ≥ Hˆ n 2 v´o.i mo.i d¯ı˙’nh vi ∈ V th`ı G l`a d¯`ˆo thi. Hamilton. e. qua˙’ 5.3.13 [P´osa] [51] Nˆe´u c´ac d¯ı˙’nh cu˙’ a G d¯u.o..c d¯´anh sˆo´ thu.. tu.. sao cho Hˆ dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ) a nˆe´u v` n ∀k : 1 ≤ k < ⇒ dG (vk ) > k, 2 a d¯`ˆo thi. Hamilton. th`ı G l` e. qua˙’ 5.3.14 [Bondy] [7] Gia˙’ su˙’. c´ac d¯ı˙’nh cu˙’ a G d¯u.o..c d¯´anh sˆo´ thu.. tu.. sao cho Hˆ dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ). Nˆe´u d¯iˆ `eu kiˆe.n sau d¯u ´ng: p < q, dG (vp ) ≤ p, dG (vq ) ≤ q − 1 ⇒ dG (vp ) + dG (vq ) ≥ n, a d¯`ˆo thi. Hamilton. th`ı G l` e. qua˙’ 5.3.15 [Chv´atal] [13] Nˆe´u c´ac d¯ı˙’nh cu˙’ a G d¯u.o..c d¯´anh sˆo´ thu.. tu.. sao cho Hˆ dG (v1 ) ≤ dG (v2 ) ≤ · · · ≤ dG (vn ) a nˆe´u v` n dG (vk ) ≤ k < ⇒ dG (vn−k ) ≥ n − k 2 a d¯`ˆo thi. Hamilton. th`ı G l` 141 http://www.ebook.edu.vn
Hˆe. qua˙’ 5.3.16 [Las Vergnas] [42] [30] Nˆe´u c´ac d¯ı˙’nh cu˙’ a G d¯u.o..c d¯´anh sˆo´ thu.. tu.. v1 , v2 , . . . , vn sao cho  j < k, k ≥ n − j   (vj , vk ) ∈ /E ⇒ dG (vj ) + dG (vk ) ≥ n   dG (vj ) ≤ j, dG (vk ) ≤ k − 1 a d¯`ˆo thi. Hamilton. th`ı G l` C´ac ch´ u.ng minh. Ch´ u.ng minh cu˙’a Hˆe. qua˙’ 5.3.11 suy tru..c tiˆe´p t`u. c´ach xˆay du..ng [G]n : tˆa´t / E c´o thˆe˙’ d¯u o. c thˆem v`a do d¯´o ta c´o [G]n = Kn . Hˆe. qua˙’ 5.3.12 suy tru..c ca˙’ c´ac ca.nh (vi , vj ) ∈ . . tiˆe´p t`u. Hˆe. qua˙’ 5.3.11. Ho.n n˜u.a, dˆ˜e d`ang thˆa´y rˇ`a ng, d¯`ˆo thi. thoa˙’ m˜an c´ac d¯iˆ `eu kiˆe.n cu˙’a Hˆe. qua˙’ 5.3.13, 5.3.14 ung thoa˙’ m˜an c´ac gia˙’ thiˆe´t cu˙’a Hˆe. qua˙’ 5.3.16. hay 5.3.15 c˜ D u.ng minh Hˆe. qua˙’ 5.3.16, ta s˜e su˙’. du.ng kˆe´t qua˙’ sau cho d¯iˆ - ˆe˙’ ch´ `eu kiˆe.n d¯u˙’ d¯ˆe˙’ [G]n = Kn . y 5.3.17 [8] Nˆe´u c´ac d¯ı˙’nh cu˙’ a G d¯u.o..c d¯´anh sˆo´ thu.. tu.. v1 , v2 , . . . , vn sao cho - i.nh l´ D  i
• .................. ....... ... .. ....... ....... .. ..... .............. ....... ..... ... ....... ............ . .. . ... ....... .. ....... ....... ... ... ....... ............. ..... ... . ....... ....... . ..... . .. ... ....... ... . .. .... . . . . . . ..... . ... .... ....... ....... ..... • . .... ... . .... . .. . .. ... . ... .... .... .... ....... ..... .... • ... .... .... ... ... .... .... ... ... .... .... ... ... .... .... ... ... . ... .... ... .... .... .... ..... .. ... . .... ... ... .... .... ... ... ... . .. ... ... .... ... . ... ... .... ... . .... . ... ... ..... .... .... ... .... ... ... ... .... ... .. ... ... .. .. • ........... ....... ....... ....... . ........... ....... ... ..... • ....... ....... ....... . .... ... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... .. ........... ....... ... ....... ............. • ... H`ınh 5.10: V´o.i d¯`ˆo thi. n`ay, [G]6 = K6 nhu.ng khˆong thˆe˙’ ´ap du.ng Hˆe. qua˙’ 5.3.16. y 5.3.18 [Meyniel, 1973] Gia˙’ su˙’. G = (V, E) l`a d¯`ˆo thi. c´o hu.´o.ng n d¯ı˙’nh liˆen thˆong - i.nh l´ D ma.nh khˆong khuyˆen sao cho (vi , vj ) ∈ / E v`a (vj , vi ) ∈ / E ⇒ dG (vi ) + dG (vj ) ≥ 2n − 1. Khi d¯´ u.a mˆo.t ma.ch Hamilton. o G ch´ Ch´ ung ta s˜e d¯u.a ra ch´ u.ng minh c´o t´ınh kiˆe´n thiˆe´t d¯.inh l´ y n`ay (theo Minoux, 1977) . 4 ˙ ’ u c ta.p O(n ) d¯ˆe t`ım ma.ch Hamilton. Ch´ v`a mˆo.t thuˆa.t to´an c´o d¯oˆ. ph´ u.ng minh du..a trˆen . . . . phu o ng ph´ap (khˆong kiˆe´n thiˆe´t) cu˙’a Bondy v`a Thmassen (1977). Tru ´o c hˆe´t, ch´ ung ta cˆ `an mˆo.t sˆo´ kh´ai niˆe.m. Gia˙’ su˙’. S ⊂ V. V´o.i mˆo˜i vi ∈ V (c´o thˆe˙’ vi ∈ S), k´ y hiˆe.u δS (i) l`a sˆo´ c´ac cung nˆo´i (theo . . hu ´o ng bˆa´t k` . y) d¯ı˙’nh vi v´o i tˆa.p con S. V`ı G khˆong c´o khuyˆen nˆen ta luˆon luˆon c´o vi ∈ S ⇒ δS (i) ≤ 2#S − 2. V´o.i S l`a tˆa.p con thu..c su.. cu˙’a V ta go.i S−bˆo. h`anh l`a mˆo.t d¯u.`o.ng d¯i m`a c´ac d¯ı˙’nh d¯`ˆau v`a cuˆo´i (khˆong nhˆa´t thiˆe´t phˆan biˆe.t) thuˆo.c S v`a c´ac d¯ı˙’nh trung gian l`a phˆan biˆe.t v`a ta.o th`anh mˆo.t tˆa.p con kh´ac trˆo´ng cu˙’a tˆa.p V \ S. Mˆo.t S−d¯u.`o.ng d¯i l`a mˆo.t S−bˆo. h`anh m`a c´ac d¯iˆe˙’m d¯`aˆu v`a cuˆo´i kh´ac nhau. Ta c´o bˆo˙’ d¯`ˆe sau: Bˆo˙’ d`e 5.3.19 Gia˙’ su˙’. µ = (v0 , v1 , . . . , vp ) l`a d¯u.`o.ng d¯i so. cˆa´p cu˙’ a G, S l`a tˆa.p c´ac d¯ı˙’nh cu˙’ a ¯ˆ n´o v`a d¯ˇa.t v ∈ V \ S. Nˆe´u khˆong tˆ `on ta.i hai d¯ı˙’nh liˆen tiˆe´p vk v`a vk+1 (0 ≤ k ≤ p − 1) cu˙’ a µ sao cho (vk , v) ∈ E v`a (v, vk+1 ) ∈ E th`ı δS (v) ≤ #S + 1. 143 http://www.ebook.edu.vn
u.ng minh. X´et c´ac tˆa.p con cu˙’a S \ {vp } : Ch´ A := {vi ∈ S \ {vp } | (vi , v) ∈ E} v`a A := {vi ∈ S \ {vp } | (v, vi+1 ) ∈ E}. Theo gia˙’ thiˆe´t, A ∩ B = ∅ v`a #(A ∪ B) ≤ #S − 1 (do vp ∈ / A, vp ∈ / B). Vˆa.y δS (v) ≤ #A + #B + 2 = #(A ∪ B) − #(A ∩ B) + 2 ≤ #S + 1, d¯iˆ u.ng minh. `eu pha˙’i ch´ / Bˆay gi`o. ch´ u.ng minh D ung ta ch´ - i.nh l´ y 5.3.18. u.ng minh cu˙’a D Ch´ - .inh l´ y 5.3.18. X´et d¯`oˆ thi. G thoa˙’ m˜an c´ac d¯iˆ `eu kiˆe.n cu˙’a d¯.inh l´ y. `on ta.i mˆo.t ma.ch d¯ˆo. d`ai ´ıt nhˆa´t hai. (1) V`ı G liˆen thˆong ma.nh nˆen tˆ Ta n´oi ma.ch µ trong G l`a tu..a cu..c d¯a.i nˆe´u v´o.i mo.i d¯ı˙’nh v ∈ `on ta.i hai d¯ı˙’nh / µ khˆong tˆ vk v`a vk+1 liˆen tiˆe´p trˆen ma.ch µ sao cho (vk , v) ∈ U v`a (vk+1 , v) ∈ U. Hiˆe˙’n nhiˆen rˇ`a ng d¯ˆe˙’ kiˆe˙’m tra mˆo.t ma.ch c´o pha˙’i tu..a cu..c d¯a.i hay khˆong, hoˇa.c d¯ˆe˙’ ph´at hiˆe.n mˆo.t ma.ch d¯ˆo. d`ai l´o.n ho.n 1 ta cˆ `an thu..c hiˆe.n O(n2 ) ph´ep to´an so. cˆa´p. Do d¯o´, thuˆa.t to´an xˆay du..ng mˆo.t ma.ch tu..a cu..c d¯a.i trong G bˇa´t d¯`aˆu t` u. mˆo.t ma.ch tu` y y 3 . ´ d¯`oi ho˙’i O(n ) ph´ep to´an so cˆa´p. Gia˙’ su˙’. µ l`a ma.ch tu..a cu..c d¯a.i, v`a k´ y hiˆe.u S l`a tˆa.p c´ac d¯ı˙’nh cu˙’a n´o. Nˆe´u S = V ta d`u ng: µ l`a ma.ch Hamilton. Ngu o. c la.i, ta s˜e chı˙’ ra rˇ`a ng c´o thˆe˙’ mo˙’. rˆo.ng ma.ch µ d¯ˆe˙’ nhˆa.n . . . d¯u.o..c mˆo.t ma.ch µ0 c´o d¯ˆo. d`ai l´o.n ho.n, v`a do d¯o´, theo quy na.p, ta s˜e c´o mˆo.t ma.ch Hamilton. (2) Ch´ u.ng minh tˆ ung ta ch´ `on ta.i mˆo.t S−d¯u.`o.ng d¯i trong G. u.ng, gia˙’ su˙’. khˆong tˆ Bˇ`a ng pha˙’n ch´ `on ta.i S−d¯u.`o.ng d¯i. V`ı G liˆen thˆong ma.nh, tˆ `on ta.i ´ ˙ ’ ` ´ ˙ ’ ´ıt nhˆa t mˆo.t S−bˆo. h`anh P m`a c´ac d¯ınh d¯aˆu cuˆoi cua n´o l`a v ∈ S. - ˇa.t R l`a tˆa.p c´ac d¯ı˙’nh thuˆo.c P v`a kh´ac v; d¯aˇ. t T l`a tˆa.p c´ac d¯ı˙’nh cu˙’a G khˆong thuˆo.c D S ∪ R. `on ta.i S−d¯u.`o.ng d¯i nˆen khˆong tˆ Theo gia˙’ thiˆe´t khˆong tˆ `e v´o.i `on ta.i d¯ı˙’nh thuˆo.c R v`a kˆ mˆo.t d¯ı˙’nh trong S \ {v}. 144 http://www.ebook.edu.vn
Do d¯o´ v´o.i mˆo˜i d¯ı˙’nh vi ∈ R v`a d¯ı˙’nh vj ∈ S \ {v} ta c´o δR (vi ) ≤ 2#R − 2, δR (vj ) = 0, δS (vi ) ≤ 2, δS (vj ) ≤ 2#S − 2. Ho.n n˜ u.a ta cˆ `an c´o δT (vi ) + δT (vj ) ≤ 2#T. (Nˆe´u khˆong, tˆ `on ta.i ´ıt nhˆa´t mˆo.t d¯u.`o.ng d¯i d¯oˆ. d`ai 2 hoˇa.c gi˜ u.a vi v`a vj , hoˇa.c gi˜ u.a vj v`a vi ; d¯u.`o.ng d¯i n`ay (c´o mˆo.t phˆ`an nˇa` m trˆen P ) ta.o th`anh mˆo.t S−d¯u.`o.ng d¯i). u.ng minh rˇa` ng c´ac d¯ı˙’nh vi v`a vj l`a hai d¯ı˙’nh khˆong kˆ C´o thˆe˙’ ch´ `e nhau sao cho δ(vi ) + δ(vj ) = δS (vi ) + δR (vi ) + δT (vi ) + δS (vj ) + δR (vj ) + δT (vj ) ≤ 2(#R + #S + #T ) − 2 = 2n − 2, mˆau thuˆa˜n v´o.i gia˙’ thiˆe´t. `on ta.i ´ıt nhˆa´t mˆo.t S−d¯u.`o.ng d¯i, ta s˜e t`ım mˆo.t S−d¯u.`o.ng d¯i P xuˆa´t ph´at t` (3) V`ı tˆ u. x v`a kˆe´t th´uc ta.i y sao cho d¯oˆ. d`ai cu˙’a d¯u.`o.ng d¯i con µ(x, y) t` u. x d¯ˆe´n y trˆen µ l`a nho˙’ nhˆa´t (theo sˆo´ c´ac cung). V´o.i mˆo.t d¯ı˙’nh x ∈ S cho tru.´o.c, ch´ ung ta c´o thˆe˙’ su˙’. du.ng thuˆa.t to´an t`ım kiˆe´m theo `eu rˆo.ng trˆen d¯`ˆo thi. G nhu. d¯a˜ tr`ınh b`ay trong Chu.o.ng 3. Phu.o.ng ph´ap n`ay d¯`oi ho˙’i O(m) chiˆ ph´ep to´an so. cˆa´p. Do d¯´o thuˆa.t to´an t`ım mˆo.t S−d¯u.`o.ng d¯i P v´o.i t´ınh chˆa´t d¯o`i ho˙’i cˆ `an nhiˆ `eu . nhˆa´t O(mn) ph´ep to´an so cˆa´p. K´y hiˆe.u R l`a tˆa.p c´ac d¯ı˙’nh trung gian cu˙’a P, v`a S1 l`a tˆa.p c´ac d¯ı˙’nh trung gian trˆen d¯u.`o.ng d¯i µ(x, y) cu˙’a µ. Nˆe´u S1 = ∅ th`ı thay cung (x, y) bo˙’.i S−d¯u.`o.ng d¯i P v`a ch´ ung ta nhˆa.n d¯u.o..c mˆo.t ma.ch µ0 c´o d¯oˆ. d`ai l´o.n ho.n hoˇa.c bˇ`a ng (#S + 1). (4) Kˆe´ tiˆe´p ta gia˙’ su˙’. S1 6= ∅, v`a d¯aˇ. t S2 := S \ S1 v`a T l`a tˆa.p c´ac d¯ı˙’nh cu˙’a G khˆong thuˆo.c R v`a S. Ch´ ung ta xˆay du..ng mˆo.t d¯u.`o.ng d¯i so. cˆa´p tu..a cu..c d¯a.i Q gi˜ u.a y v`a x m`a tˆa.p c´ac d¯ı˙’nh cu˙’a n´o l`a S 0 thoa˙’ m˜an S 0 ⊂ S v`a S2 ⊂ S 0 bˇa` ng phu.o.ng ph´ap lˇa.p nhu. sau: 1. Kho˙’.i ta.o v´o.i Q := µ(x, y), S 0 := S2 , S 00 := S1 . 2. T`ım d¯ı˙’nh s ∈ S 00 sao cho (k, s) ∈ U v`a (s, l) ∈ U v´o.i hai d¯ı˙’nh k v`a l liˆen tiˆe´p trˆen Q. (Nhˆa.n x´et rˇ`a ng, d¯iˆ `eu nhˆa´t O(n) ph´ep to´an so. cˆa´p). Nˆe´u khˆong tˆ `eu n`ay d¯`oi ho˙’i nhiˆ `on . 00 ta.i d¯ı˙’nh s nhu vˆa.y (hoˇa.c l`a S = ∅) th`ı d` u ng: d¯u `o ng d¯i Q l`a tu. a cu. c d¯a.i (hoˇa.c cu..c . . . . . d¯a.i). 145 http://www.ebook.edu.vn
3. Gia˙’ su˙’. tˆ u.a hai d¯ı˙’nh k v`a l d¯ˆe˙’ nhˆa.n d¯u.o..c mˆo.t d¯u.`o.ng `on ta.i d¯ı˙’nh s th`ı ch`en n´o v`ao gi˜ d¯i m´o i Q c´o d¯oˆ. d`ai l´o n ho n d¯u `o ng d¯i tru.´o.c d¯o´ mˆo.t. Thay S 0 bo˙’.i S 0 ∪ {s}, S 00 bo˙’.i . 0 . . . . S 00 \ {s}, Q bo˙’.i Q0 v`a lˇa.p la.i Bu.´o.c 2. Ch´ uy `an thu..c hiˆe.n trong thuˆa.t to´an n`ay khˆong vu.o..t qu´a O(n3 ). ´ rˇ`a ng, sˆo´ ph´ep to´an cˆ Ta s˜e chı˙’ ra rˇ`a ng, kˆe´t th´ uc thuˆa.t to´an th`ı S 00 = ∅. Thˆa.t vˆa.y, gia˙’ su˙’. ngu.o..c la.i S 00 6= ∅. Theo c´ach xˆay du..ng cu˙’a P, c´ac d¯ı˙’nh cu˙’a R khˆong kˆ `e v´o.i mˆo.t d¯ı˙’nh cu˙’a S1 (v`ı nˆe´u . . . . ngu o. c la.i, ta c´o thˆe˙’ t`ım mˆo.t S−d¯u `o ng d¯i m`a c´ac d¯ı˙’nh d¯`ˆau cuˆo´i cu˙’a n´o gˆ `an µ ho.n P ). Do d¯o´, v´o.i mo.i d¯ı˙’nh vi ∈ R v`a mo.i d¯ı˙’nh vj ∈ S1 ta c´o δR (vj ) = δS1 (vi ) = 0. Mˇa.t kh´ac, v`ı µ l`a ma.ch tu..a cu..c d¯a.i, d¯ı˙’nh vi thoa˙’ m˜an c´ac gia˙’ thiˆe´t cu˙’a Bˆo˙’ d¯`ˆe 5.3.19 v´o.i d¯u.`o.ng d¯i con µ(x, y) sao cho δS2 (vi ) ≤ #S2 + 1. Cho.n vj ∈ S 00 ⊂ S1 . Theo c´ach xˆay du..ng cu˙’a Q, ´ap du.ng la.i Bˆo˙’ d¯`ˆe 5.3.19 v´o.i d¯ı˙’nh vj v`a d¯u.`o.ng d¯i Q, ta d¯u.o..c δS 0 (vj ) ≤ #S 0 + 1. Mˇa.t kh´ac, ta cˆ`an c´o (nhu. d¯˜a ch´ u.ng minh trong Phˆ `an (2)) δT (vi ) + δT (vj ) ≤ 2#T (ngu.o..c la.i, ta c´o thˆe˙’ t`ım mˆo.t S−d¯u.`o.ng d¯i m`a c´ac d¯ı˙’nh d¯`ˆau cuˆo´i cu˙’a n´o gˆ `an µ ho.n P ). Cuˆo´i c` ung, ta luˆon luˆon c´o δS 00 (vj ) ≤ 2#S 00 − 2, v`a δR (vi ) ≤ 2#R − 2. Suy ra δ(vi ) + δ(vj ) ≤ 2#R + #S2 + 2#S 00 + #S 0 − 2 v`a #S2 ≤ #S 0 ⇒ δ(vi ) + δ(vj ) ≤ 2n − 2 v´o.i hai d¯ı˙’nh khˆong kˆ `e nhau vi v`a vj , mˆau thuˆa˜n v´o.i gia˙’ thiˆe´t. u. d¯u.`o.ng d¯i Q v´o.i S−d¯u.`o.ng d¯i P ta c´o thˆe˙’ xˆay du..ng mˆo.t ma.ch µ0 c´o Vˆa.y S 00 = ∅ v`a t` d¯oˆ. d`ai ≥ #S + 1. (5) Trong tˆa´t ca˙’ c´ac tru.`o.ng ho..p (tham kha˙’o c´ac Phˆ `an (3) v`a (4) trˆen) khi #S < n ta c´o ˙ ’ `eu nhˆa´t O(mn + n ) ph´ep to´an so cˆa´p) mˆo.t ma.ch µ0 c´o d¯ˆo. d`ai l´o.n ho.n ma.ch thˆe t`ım (nhiˆ 3 . 146 http://www.ebook.edu.vn