Số đồ thị Hamilton tối đại.

Chia sẻ: Bút Màu | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

77
lượt xem 6
download

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

Số đồ thị Hamilton tối đại. Quan hệ chức năng ấy bao gồm sự trao đổi thông tin và vòng quan hệ phản hồi (feedback) mà kết quả rõ nét của nó là hiện tượng Tự tổ chức ( Humberto Maturana, Varela và Ricardo Uribe phát hiện), Tự sản sinh - autopoiesis ( Francisco phát hiện).

Chủ đề:

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

Lưu

Nội dung Text: Số đồ thị Hamilton tối đại.

. . a ` e e’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.22, S.3 (2006), 221—228 ı . ´ ` ˆ ˆ ´ ˆ SO DO THI HAMILTON TOI DAI . . ˜ INH HOA1 , DO NHU. AN2 VU D` ` ˜ ˆ 1 Khoa Cˆng nghˆ thˆng tin, Tru.`.ng Dai hoc Su. pham H` Nˆi o e o . o . . . a o. 2 Khoa Cˆng nghˆ thˆng tin, Tru.`.ng Dai hoc Nha Trang o e o . o . . Abstract. A graph is called a maximal uniquely Hamiltonian graph if it has the maximum number of edges among the graphs with the same number of vertices and exact one Hamiltonian cycle. In this n−7 paper, we prove the conjecture posed in [5] that for every n ≥ 7 there are exactly 2[ 2 ] maximal uniquely Hamiltonian graphs. T´m t˘t. Mˆt dˆ thi du.o.c goi l` dˆ thi Hamilton tˆi dai nˆu nhu. n´ c´ sˆ canh nhiˆu nhˆ t c´ thˆ o ´ a o o . . ` . ` . a o . ´ o . e ´ ´ o o o . ` e ´ a o e ’ a o ` thi c´ c` ng sˆ dınh v` c´ d´ng mˆt chu tr` Hamilton. Trong b`i n`y, ch´ ng tˆi ch´.ng trong c´c dˆ . o u ´ ’ o a o u o . ınh a a u o u n−7 minh gia thuyˆt du.o.c nˆu trong [5] r˘ ng c´ d´ ng 2[ 2 ] dˆ thi Hamilton tˆi dai n ≥ 7 dınh. ’ ´ e . e ` a o u ` o . ´ o . ’ ’. A 1. MO D` U ˆ Trong b`i b´o n`y, ch´ng ta chı n´i dˆn c´c dˆ thi h˜.u han vˆ hu.´.ng. Mˆt dˆ thi G du.o.c a a a u ´ ’ o e a o . u ` . o o . ` o o . . k´ hiˆu G = (V, E) v´ y e o.i V l` tˆp ho.p dınh v` E l` tˆp ho.p canh cua G. Dˆ thi G = (V , E ) a a ’ a a a ’ ` o . 1 . . . . . . 1 1 .o.c n´i l` dˆ thi con cua dˆ thi G2 = (V2 , E2 ) nˆu nhu. V1 ⊆ V2 v` E1 ⊆ E2 . Dˆ thi con du . o a o ` . ’ o .` e´ a ` . o G1 = (V1 , E1 ) cua dˆ thi G2 = (V2 , E2 ) du.o.c goi l` dˆ thi th`nh phˆn cua G2 nˆu nhu. mˆi ’ o .` . . ` a o . a ` a ’ ´ e ˜ o canh e = (x, y) cua G2 v´.i x, y ∈ V1 c˜ng l` canh cua dˆ thi G1 . Cho tru.´.c dˆ thi G = (V, E) . ’ o u a . ’ o .` o o . ` v` S l` tˆp ho.p con cua V , th` dˆ thi th`nh phˆn cua G v´.i tˆp dınh S du.o.c goi l` dˆ thi a a a. . ’ ` ı o . a `a ’ o a ’ . . . a o .` sinh bo.i S v` du.o.c k´ hiˆu l` G[S]. Ngo`i ra, moi k´ hiˆu v` kh´i niˆm kh´c o. dˆy dˆu du.o.c ’ a . y e a . a . y e a a e . . a ’ a ` e . lˆ y t`. [3]. Cho tru.´.c mˆt dˆ thi do.n vˆ hu.´.ng G, ta goi mˆt chu tr`nh C cua G l` chu tr`nh ´ a u o . ` o o . o o . o . ı ’ a ı ´ e o ´ a ’ a ’ ` ’ o . . ` Hamilton nˆu n´ di qua tˆ t ca c´c dınh cua dˆ thi G. Trong h` 1 ta c´ mˆt dˆ thi 5 dınh ınh o o o . ’ v´o .i hai chu tr` Hamilton kh´c nhau. ınh a ı ` o . ’ H`nh 1. Dˆ thi 5 dınh c´ hai chu tr` Hamilton o ınh Dˆ thi khˆng c´ chu tr` Hamilton v´.i nhiˆu canh nhˆ t, d˜ du.o.c nghiˆn c´.u bo.i Erdos ` o . o o ınh o ` e . a´ a . e u ’ ´ ` .o.c goi l` dˆ ` . ´ [4] v` mˆt sˆ nh` to´n hoc kh´c. Nˆu dˆ thi G c´ chu tr` Hamilton th` n´ du . a o o a a . a e o . o ınh ı o . a o thi Hamilton. Mˆt dˆ thi chı c´ d´ ng mˆt chu tr` Hamilton du.o.c goi l` dˆ thi Hamilton . . ` o o . ’ o u o . ınh . . ` a o . tˆi dai nˆu nhu. n´ c´ nhiˆu canh nhˆ t trong sˆ c´c dˆ thi c`ng sˆ dınh v` c´ d´ng mˆt chu ´ o . e ´ o o `e . ´ a ´ ` o a o . u ´ o ’ a o u o . tr` Hamilton. L´.p c´c dˆ thi n`y du.o.c nhiˆu nh` to´n hoc nghiˆn c´.u ([1, 2, 5, 6]). H` 2 ınh ` o a o . a . ` e a a . e u ınh
222 ˜ INH HOA, DO NHU. AN VU D` ` ˜ ˆ ` ´ ’ l` dˆ thi Hamilton tˆi dai 5 dınh. a o . o . ` ´ H`nh 2. Dˆ thi Hamilton tˆi dai 5 dınh ı o . o . ’ Dˆi v´.i dˆ thi Hamilton tˆi dai, Sheehan [6] d˜ nghiˆn c´.u b`i to´n t` sˆ canh nhiˆu ´ o o o . ` ´ o . a e u a ´ a ım o . `e nhˆ t c´ thˆ cua dˆ thi n dınh v´.i duy nhˆ t mˆt chu tr` Hamilton. Kˆt qua tu.o.ng tu. du.o.c ´ ’ a o e ’ o . ` ’ o ´ o a . ınh ´ e ’ . . Barefoot v` Entringer [1] nghiˆn c´.u cho l´.p dˆ thi c´ duy nhˆ t mˆt chu tr`nh Hamilton v` a e u o o . o ` ´ o a . ı a hai dınh khˆng kˆ nhau bˆ t k` cua n´ du.o.c nˆi v´.i nhau bo.i mˆt du.`.ng Hamilton (du.`.ng ’ o ` e ´ a y ’ o . ´ o o ’ o . o o ch´.a to`n bˆ c´c dınh cua dˆ thi). Ta khˆng xem x´t l´.p dˆ thi d´ o. dˆy. u a o a ’ . ’ o . ` o ` e o o . o ’ a Sheehan [6] ch´.ng minh dinh l´ sau: u . y Dinh l´ 1. [Sheehan] Dˆ thi tˆi dai v´.i n dınh c´ d´ng [ n ] + 1 canh. 2 . y ` o . o . o ´ ’ o u 4 . n−7 Trong [5], ch´ng tˆi d˜ chı ra r˘ ng c´ ´ nhˆ t 2[ 2 ] dˆ thi Hamilton tˆi dai b˘ ng thuˆt u o a ’ ` a o ıt a ´ ` o . o . ` ´ a a . to´n x´c dinh dˆ thi Hamilton tˆi dai n dınh nhu. sau. a a . ` o . ´ o . ’ n−7 Dinh l´ 2. Thuˆt to´n sau dˆy cho ta ´t nhˆ t 2[ 2 ] dˆ thi Hamilton tˆi dai n dınh khˆng . y a . a a ı ´ a ` o . ´ o . ’ o ’ ng cˆ u v´.i nhau. d˘ a ´ o a Xuˆ t ph´t t`. mˆt chu tr` C c´ n dınh. Ta chon dınh x0 t` y y trˆn C v` x´c dinh ´ a a u o . ınh o ’ . ’ u ´ e a a . X1 = {x0 }, Y1 = ∅. Nˆu tˆp dınh Xi v` Yi d˜ du.o.c x´c dinh, th` ta x´c dinh dınh xi ∈ Xi sao cho tˆ n tai x ∈ Xi ´ . e a ’ a a . a . ı a . ’ / ` o . ’ a ınh a a ’ ` o c´ch xi khoang c´ch 2 doc theo chu tr` C , v` yi l` dınh kˆ v´ i a a e .i x v` x trˆn C . Tˆp ho.p e a . . . .o.c x´c dinh theo quy t˘ c sau: Xi+1 v` Yi+1 du . a . a ´ a Xi+1 = Xi ∪ {xi }, Yi+1 = Yi ∪ {yi }, v´.i i = 1, 2, . . . , [ n ]. Dˆ thi G thu du.o.c b˘ ng c´ch bˆ sung v`o C c´c canh nˆi c´c dınh yi o 2 ` o . . ` a a o ’ a a . ´ o a ’ .i tˆ t ca c´c c´c dınh khˆng thuˆc Xi+1 ∪ Yi+1 . Ch˘ng han trong H` 3, ta c´ hai dˆ thi o ´ v´ a ’ a a ’ o o ’ a ınh o ` o . . . ´ ’ ’ Hamilton tˆi dai 9 dınh khˆng d˘ ng cˆ u. o . o a ´ a v1 v1 v2 v9 v2 v9 v3 v8 v3 v8 v4 v7 v4 v7 v5 v6 v5 v6 ` ´ ’ H`nh 3. Hai dˆ thi Hamilton tˆi dai 9 dınh ı o . o .
´ ` ˆ ˆ ´ ˆ SO DO THI HAMILTON TOI DAI 223 . . n−7 B˘ ng thuˆt to´n d˜ nˆu trˆn, ta c´ ´ nhˆt 2[ 2 ] dˆ thi Hamilton tˆi dai n dınh cho mˆi ` a a . a a e e o ıt a ´ ` o . ´ o . ’ ˜ o ’ ´ .o.c du.a ra. gi´ tri n 7. Trong [5], gia thuyˆt sau du . a . e n−7 Gia thuyˆt 1. C´ d´ng 2[ 2 ] dˆ thi Hamilton tˆi dai n ’ ´ e o u ` o . ´ o . ’ 7 dınh. Sau dˆy ta ch´.ng minh r˘ ng gia thuyˆt trˆn l` d´ ng. a u ` a ’ ´ e e a u n−7 Dinh l´ 3. C´ d´ng 2[ . y o u 2 ] ` ´ dˆ thi Hamilton tˆi dai n o . o . ’ 7 dınh. ˆ ´ ´ ˆ ˆ ` ˆ´ ’ . ’ 2. MOT SO KY HIEU VA KET QUA CO BAN . . K´ hiˆu h(n) l` sˆ canh cua dˆ thi Hamilton tˆi dai n dınh. C´c bˆ dˆ du.´.i dˆy d˜ du.o.c y e . ´ a o . ` ’ o . ´ o . ’ a o `’ e o a a . Sheehan [6] ch´ u.ng minh. 2 Bˆ dˆ 1. ( Theorem 1 [6]) h(n) = [ n ] + 1. ’ e o ` 4 X´t mˆt dˆ thi Hamilton tˆi dai G v´.i n dınh. Ta k´ hiˆu c´c dınh cua G liˆn tiˆp nhau e . ` o o . ´ o . o ’ y e a ’ . ’ e ´ e trˆn chu tr` Hamilton C cu e ınh a ˜ . ’ a G l` v1 , v2 , . . . , vn . Mˆi canh e cua G khˆng thuˆc C c`n o ’ o o . o du.o.c goi l` mˆt dˆy cung cua C . Ta c´: . . a o a . ’ o ’ dˆ 2. (Lemma 2 [6]) Hai dˆy cung (vi , vj+1 ), (vi+1 , vj ) khˆng dˆ ng th`.i thuˆc G. Bˆ ` o e a o o` o o . .´.c mˆt dˆy cung e = (vi , vj ), ta goi dˆ d`i cua dˆy cung e l` dˆ d`i cua con du.`.ng Cho tru o o a . . o a ’ a . a o a ’ . o ng˘´n nhˆ t doc theo C nˆi 2 dınh cua e, nhu. vˆy dˆ d`i cua dˆy cung e t`y y luˆn l` mˆt a a´ . ´ o ’ ’ a o a . . ’ a u ´ o a o . sˆ tu. nhiˆn thoa m˜n 1 ´ o . e ’ a n 2 . Ngu.o.c lai, v´.i mˆi sˆ tu. nhiˆn thoa m˜n 1 . . o ˜ ´ o o . e ’ a n 2 , ta k´ hiˆu C(n : ) l` tˆp ho.p c´c dˆy cung c´ dˆ d`i . y e . a a. . a a o o a . Bˆ dˆ 3. (Lemma 3 [6]) V´.i mˆi n, ta c´ |C(n : )| n . ’ e o ` o ˜ o o 2 Ngo`i ra trong [6] c˜ng ch´.ng minh: a u u ’ e o ` ´ ´ ˜ Bˆ dˆ 4. (Lemma 6 [6]) Nˆu n l` sˆ ch˘n, e a o a ´ a o ’ ’ l` sˆ le tho a m˜n 1 a < n 2 th` |C(n : )| < n . ı 2 ’ e o ` ´ e ´ ˜ Bˆ dˆ 5. (Lemma 7 [6]) Nˆu n l` sˆ ch˘ n th` |C(n : n )| n . a o a ı 2 4 Trong dˆ thi Hamilton tˆi dai v´.i d´ng [ 4 ] + 1 canh, th` c´c bˆt d˘ng th´.c du.o.c ch´.ng ` o . ´ o . o u n2 . ´ ’ ı a a a u . u ’ e a o ` e minh trong c´c bˆ dˆ trˆn tro a’. th`nh d˘ ng th´.c, cho nˆn ta c´: a’ u e o Bˆ dˆ 6. Trong dˆ thi Hamilton tˆi dai G v´.i n dınh v` [ n ] + 1 canh, ta c´: 2 ’ e o ` ` o . ´ o . o ’ a 4 . o ´ ´ n−1 n e a o ’ ı a) Nˆu n l` sˆ le th` G c´ 2 dˆy cung dˆ d`i o a o a . 2 . ´ e ´ ˜ b) Nˆu n l` sˆ ch˘n th` G: a o a ı - c´ d´ng n dˆy cung dˆ d`i n ch˘ n, o u 4 a o a 2 a . ˜ n ˜n = n , - c´ d´ng 2 dˆy cung dˆ d`i ch˘ o u a o a . a 2 - c´ d´ng 2 − 1 dˆy cung dˆ d`i le = n . o u n a o a ’ . 2 ’ Dˆ ch´ e u .ng minh Dinh l´ 3, ta nghiˆn c´.u cˆ u tr´ c c´c dˆy cung trong dˆ thi Hamilton tˆi y e u a ´ u a a ` o . o´ . dai G. . ´ ˆ ´ ˆ` 3. CAU TRUC DO THI HAMILTON TOI DAI ˆ´ . . Cho tru.´.c dˆ thi Hamilton tˆi dai G v´.i [ n ] + 1 canh, ta biˆu diˆn dˆ thi G c´ dınh tai 2 o o .` ´ o . o 4 . e’ ˜ o . e ` o ’ . ’ a ` ’ ’ ’ a ` dınh mˆt n gi´c dˆu v` canh cua chu tr` Hamilton C cua G l` c´c canh cua n gi´c dˆu d˜ o . e a . ınh a a . e a cho (H` 4). ınh ’ e o o ` Ta c´ bˆ dˆ sau dˆy: a
224 ˜ INH HOA, DO NHU. AN VU D` ` ˜ ˆ ’ e o ` ˜ ı a ’ ’ a a . ` Bˆ dˆ 7. Khi n ch˘ n th` c´c dınh cua c´c dˆy cung dˆ d`i 2 sinh ra mˆt dˆ thi con dˆy du a o a . o o . ` a ’ o . ` o . ¯ n (l` dˆ thi c´ n dınh v` khˆng c´ canh n`o ca ). K n , c´c dınh c`n lai sinh ra dˆ thi K 2 a o . o 2 ’ a ’ ` a o o . a ’ 2 Ch´.ng minh. Theo Bˆ dˆ 6 th` c´ d´ ng n dˆy cung dˆ d`i 2. Theo Bˆ dˆ 2 th` c´c dˆy u ’ e o ` ı o u 2 a o a . ’ e o ` ı a a cung n`y tao th`nh mˆt da gi´c dˆu 2 canh. Ta d´nh sˆ c´c dınh cua da gi´c dˆu n canh a . a o. a ` e n . a ´ o a ’ ’ a ` 2 . e n`y bo.i A1 , A2 , . . . , A n v` c´c dınh c`n lai cua dˆ thi G l` B1 , B2 , . . . , B n nhu. trong h` 4. a ’ 2 a a ’ o . ’ o . ` a 2 ınh An 2 Bn B1 2 A1 An −1 2 B2 Bn −1 2 A2 a ’ ’ a a ` o . ` H`nh 4. C´c dınh A1 , A2 , ..., An/2 cua c´c dˆy cung dˆ d`i 2 sinh ra dˆ thi dˆy du Kn/2 ı o a . a ’ Bˆy gi`. ta ch´.ng to r˘ ng c´c dˆy dˆ d`i ch˘n chı nˆi c´c dınh cua tˆp {A1 , A2 , . . . , A n } a o u ’ ` a a a o a . ˜ a ´ ’ o a ’ ’ a. 2 v´ o .i nhau. Thˆt vˆy, gia su. ngu.o.c lai l` tˆ n tai mˆt dˆy dˆ d`i ch˘ n nˆi hai dınh Bi v` Bj a a ’ ’ ` a o . o a o a ˜ a ´ o ’ a . . . . . . cua {B1 , B2 , . . . , B n } v´.i nhau. X´t hai tru.`.ng ho.p: ’ 2 o e o . ´ ˜ a) Sˆ ch˘ n = n . o a 2 ’ e o ` ’ a . Theo Bˆ dˆ 2, th` c´c dˆy (Ai−1 , Aj−1 ) v` (Ai , Aj ) khˆng phai l` canh cua dˆ thi G. Suy ı a a a o ’ o . ` rˆng ra, nˆu c´ 0 < x < 2 (x 2 theo Bˆ dˆ 6) dˆy cung dˆ d`i nˆi c´c dınh cua tˆp ho.p o . ´ e o n n ’ e o ` a o a . ´ o a ’ ’ a . . {B1 , B2 , . . . , B 2 o . ı o ıt a ´ a o a ˜ o a ’ n } v´ i nhau, th` c´ ´ nhˆ t x + 1 dˆy cung dˆ d`i ch˘ n c´ hai dınh c` ng thuˆc u o . . {A1 , A2 , . . . , A n } khˆng phai l` canh cua dˆ thi G. T`. d´ suy ra l` c´ khˆng qu´ n − (x + 1) 2 o ’ a . ’ o .` u o a o o a 2 dˆy cung dˆ d`i nˆi hai dınh cua tˆp ho.p {A1 , A2 , . . . , A n }. Khi d´ tˆ ng sˆ dˆy cung dˆ a o a . o´ ’ ’ a . . 2 o o ’ ´ o a o . d`i s˜ khˆng vu . a e o .o.t qu´ x + n − (x + 1) = n − 1 l` diˆu mˆu thuˆ n v´.i Bˆ dˆ 6. Do d´ phai a a ` e a ˜ a o o ` ’ e o ’ 2 2 c´ x = n . L´c n`y chu tr` o 2 u a ınh: C = (B1 A1 A n B n A n −1 . . . A n +2− A n +1− B n +2− B2 A2 B3 A3 . . . B n +1− ) 2 2 2 2 2 2 2 2 2 2 2 l` mˆt chu tr` Hamilton th´. hai cua G, mˆu thuˆ n v´.i gia thiˆt l` C l` chu tr`nh Hamilton a o . ınh u ’ a ˜ a o ’ ´ e a a ı ´ a ’ duy nhˆ t cua G. ´ ˜ b) Sˆ ch˘ n = n . o a 2 ’ e o ` ı a a a o ’ a . ’ o . ` Theo Bˆ dˆ 2, th` c´c dˆy (Ai−1 , Aj−1 ) v` (Ai , Aj ) khˆng phai l` canh cua dˆ thi G. Suy rˆng ra, nˆu c´ 0 < x < 4 (x 4 theo Bˆ dˆ 6) dˆy cung dˆ d`i nˆi c´c dınh cua tˆp ho.p o . ´ e o n n ’ e o ` a o a . ´ o a ’ ’ a. . {B1 , B2 , . . . , B 2 o. ı o ıt a ´ a o a ˜ o a ’ n } v´ i nhau, th` c´ ´ nhˆ t x + 1 dˆy cung dˆ d`i ch˘ n c´ hai dınh c` ng thuˆc u o . . {A1 , A2 , . . . , A n } khˆng phai l` canh cua dˆ thi G. T`. d´ suy ra l` c´ khˆng qu´ n − (x + 1) 2 o ’ a . ’ o .` u o a o o a 4 dˆy cung dˆ d`i nˆi hai dınh cua tˆp ho.p {A1 , A2 , . . . , A n }. Khi d´ tˆ ng sˆ dˆy cung dˆ a o a . ´ o ’ ’ a . . 2 o o’ ´ o a o . d`i s˜ khˆng vu . a e o .o.t qu´ x + n − (x + 1) = n − 1 l` diˆu mˆu thuˆ n v´.i Bˆ dˆ 6. Do d´ phai a a `e a ˜ a o o ` ’ e o ’ 4 4 c´ x = n . L´c n`y chu tr` o 4 u a ınh: C = (B1 A1 A n B n A n −1 . . . A n +2 A n +1 B n +2 B2 A2 B3 A3 . . . B n +1 ) 2 2 2 4 4 4 4
´ ` ˆ ˆ ´ ˆ SO DO THI HAMILTON TOI DAI 225 . . l` mˆt chu tr` Hamilton th´. hai cua G, mˆu thuˆn v´.i gia thiˆt C l` chu tr` Hamilton a o . ınh u ’ a ˜ a o ’ ´ e a ınh ´ a ’ duy nhˆ t cua G. T´m lai, khˆng c´ dˆy cung dˆ d`i ch˘n n`o nˆi hai dınh cua tˆp ho.p {B1 , B2 , . . . , B n } o . o o a o a . ˜ a a o ´ ’ ’ a . . 2 v´o .i nhau. Do d´ c´c dınh cua {B1 , B2 , . . . , B n } sinh ra dˆ thi K n . C´c dˆy cung dˆ d`i o a ’ ’ ` . ¯ o a a o a 2 2 . ch˘ n chı nˆi c´c dınh cua tˆp ho.p A1 , A2 , . . . , A n v´.i nhau. T`. Bˆ dˆ 6 dˆ d`ng suy ra c´c ˜ a ´ ’ o a ’ ’ a . . 2 o u o ` ’ e ˜ a e a n ’ ’ e .o.c ch´.ng minh. ’ ’ 2 a ’ ’ . ` o o . ` a ’ dınh cua A1 , A2 , . . . , A n l` dınh cua mˆt dˆ thi dˆy du 2 dınh. Bˆ dˆ du . o ` u Ta goi mˆt dınh cua G l` dınh dˆy du nˆu n´ du.o.c nˆi v´.i tˆ t ca c´c dınh kh´c cua dˆ . o ’ . ’ a ’ ` a ’ e o ´ ´ . o o a ’ a ’´ a ’ o ` thi. Ta dinh ngh˜ khoa . . ıa ’ ng c´ch gi˜.a hai dınh cua G l` dˆ d`i con du.`.ng ng˘n nhˆ t doc theo a u ’ ’ a o a. o ´ a ´ . a chu tr` Hamilton C nˆi ch´ng v´.i nhau. Nhu. vˆy dˆ d`i cua mˆt dˆy cung ch´ l` khoang ınh o´ u o a o a ’ . . o a . ınh a ’ c´ch gi˜.a hai dınh cua n´. Sau dˆy ta nghiˆn c´.u c´c dˆy cung c´ dˆ d`i 3. a u ’ ’ o a e u a a o o a . A1 A2 An A3 An-1 An-2 H`nh 5. Chu tr` Hamilton m´.i tao bo.i c´c dˆy cung dˆ d`i 3 ı ınh o . ’ a a o a . Hai dˆy cung dˆ d`i 3 du.o.c xem l` c´ch nhau khoang c´ch 2 theo chiˆu kim dˆ ng hˆ a o a . . a a ’ a `e ` o ` o ` .o.c kim dˆ ng hˆ ) nˆu 2 dınh xuˆ t ph´t cua n´ t´ theo chiˆu quy dinh c´ch (ho˘c chiˆu ngu . a e ` o ` ´ o e ’ ´ a a ’ o ınh `e a . . nhau dˆ d`i 2. Ta goi mˆt dınh l` dınh tu. do nˆu n´ khˆng l` dınh cua dˆy cung dˆ d`i 3 o a . . o ’ . a ’ . ´ e o o a ’ ’ a o a . n`o ca, v` mˆt dınh l` dınh dep nˆu t`. n´ c´ hai dˆy cung dˆ d`i 3 xuˆ t ph´t. Ta c´ bˆ dˆ a ’ a o ’ . a ’ . ´ e u o o a o a . a´ a ’ e o o ` ´ tiˆp theo sau dˆy: e a Bˆ dˆ 8. Nˆu sˆ dınh n cua dˆ thi Hamilton tˆi dai G l` sˆ le th` G c´ hai dınh tu. do l` ’ e o ` ´ ´ e o ’ ’ o .` ´ o . ´ a o ’ ı o ’ . a ` ’ u o ’ ’ ´ ´ e o ’ l´ng giˆng cua c`ng mˆt dınh dep trˆn chu tr`nh Hamilton cua G. Nˆu sˆ dınh n cua dˆ thi a e . . e ı ’ o . ` Hamilton tˆi dai G l` sˆ ch˘ n th` G c´ 2 dınh dep c´ khoa ng c´ch le t´.i nhau v` 4 dınh tu. ´ o . ´ ˜ a o a ı o ’ . o ’ a ’ o a ’ . do l` l´ng giˆng cua hai dınh dep n`y o. trˆn chu tr`nh Hamilton. a a `e ’ ’ . a ’ e ı Ch´ u.ng minh. Khi n le th` theo Bˆ dˆ 6 dˆ thi G c´ d´ng n−1 dˆy cung dˆ d`i 3. Theo Bˆ dˆ ’ ı ’ e o ` ` o . o u a o a ’ e o ` 2 . ’ e o ’ 2 ch´ng khˆng thˆ c´ khoang c´ch 1 t´ u o a o.i nhau, mˆi dˆy cung dˆ d`i 3 c´ khoang c´ch 2 t´.i ˜ o a o a o ’ a o . dˆy cung tiˆ a ´p theo m` thˆi. Nˆu b˘t dˆu t`. mˆt dˆy cung dˆ d`i 3 ke c´c dˆy cung dˆ d`i e a o e ´ a ´ a ` u o a . o a . ’ a a o a . 3 tiˆp theo theo quy t˘c c´. dˆy tiˆp theo c´ch dˆy tru.´.c n´ dˆ d`i 3 theo chiˆu ngu.o.c kim ´ e ´ a u a ´ e a a o o o a . ` e . dˆ ng hˆ th` dˆy dˆu tiˆn v` dˆy th´. n−1 c´ dınh chung. Ta dˆ t´ du.o.c l` nˆu dˆy dˆ d`i ` o ` o ı a ` a e a a u 2 o ’ ˜ ınh e ´ . a e a o a . 3 dˆu tiˆn b˘ t dˆu v´.i dınh th´. nhˆ t, th` dˆy th´. n−1 c´ dınh cuˆi l` dınh th´. `a ´ a e a ` o ’ u a ´ ı a u 2 o ’ ´ o a ’ u n−3 (1 + 2 × ) + 3 = 1( mod n) 2 T´.c l` G luˆn c´ mˆt dınh dep v . L´ng giˆng cua dınh dep v n`y theo Bˆ dˆ 2 chı c´ thˆ l` u a o o o ’. . a `e ’ ’ . a ’ e o ` ’ o e a ’
226 ˜ INH HOA, DO NHU. AN VU D` ` ˜ ˆ dınh tu. do, t´.c l` hai l´ng giˆng cua v l` hai dınh tu. do trong G. ’ . u a a ` e ’ a ’ . ´ n ’ ` ´ o ’ a o ’ ı Khi n l` sˆ le th` G c´ 2 − 1 dˆy cung dˆ d`i 3. Ta kh˘ng dinh r˘ ng G c´ ´ nhˆ t mˆt dınh o a o a . a . a o ıt a . dep, v` nˆ . ı e ´u G khˆng c´ dınh dep n`o, th` mˆi dˆy cung c´ dˆ d`i 2 t´.i dˆy cung tiˆp theo v` o o ’ . a ı o ˜ a o o a . o a ´ e a du.o.c bˆ tr´ nhu. trong H` 5, khi d´ dˆ thˆ y c´c canh du.o.c tˆ dˆm tao th`nh mˆt chu tr` . ´ o ı ınh o ˜ a a . e ´ . o a . . a o . ınh Hamilton m´.i (trong H` 5, c´c canh cua ch´ng du.o.c tˆ dˆm n´t): o ınh a . ’ u . o a . e C = (A1 A2 A3 . . . A4k+2 A4k+3 . . . An−2 An−1 An . . . A4k+1 A4k . . . A5 A4 ), mˆu thuˆ n v´.i gia thiˆt C l` chu tr` Hamilton duy nhˆt cua G. Mˆu thuˆn d´ ch´.ng to a ˜ a o ’ ´ e a ınh ´ a ’ a ˜ a o u ’ ` r˘ ng G phai c´ dınh dep v . T´ t` ’ a ’ o ’ ınh u . dınh v n`y theo chiˆu ngu.o.c kim dˆ ng hˆ v` chiˆu kim a ` e ` o ` o a ` e . . dˆ ng hˆ , n − 1 dˆy cung dˆ d`i 3 liˆn tiˆp nhau s˜ c´ch nhau dˆ d`i 2, v` s˜ cho ta mˆt dınh o` ` o 2 a o a . e e ´ e a o a . a e o ’ . dep u th´. hai (xem H` 6). Thˆt vˆy, vi tr´ cua u c´ thˆ t´ du.o.c do.n gian nˆu nhu. d´nh . u ınh a a . . . ı ’ ’ o e ınh . ’ e ´ a ´ c´c dınh cua G l` A1 , A2 , . . . An ngu.o.c chiˆu kim dˆ ng hˆ v` gia su. v = A1 v` c´ k dˆy sˆ a ’ o ’ a . `e ` o o` a ’ ’ a o a cung dˆ d`i 3 liˆn tiˆp nhau theo chiˆu ngu.o.c kim dˆ ng hˆ v` n − 1 − k dˆy cung dˆ d`i o a . e ´ e `e . ` o ` o a 2 a o a . 3 theo chiˆu kim dˆ ng hˆ t´ t`. v . Dınh u s˜ l` dınh th´. 1 + 2(k − 1) + 3 = 2k + 4, d´ `e o` ` o ınh u ’ e a ’ u o c˜ng l` dınh cuˆi cua dˆy th´. n − 1 − k t´ t`. v theo chiˆu kim dˆ ng hˆ theo cˆng th´.c u a ’ ´ o ’ a u 2 ınh u ` e ` o o` o u n − 2(( n − 1 − k) − 1) = 2k + 4 (mod n). L´ c n`y, tu.o.ng tu. nhu. tru.`.ng ho.p n le, c´c l´ng 2 u a . o . ’ a a ` ’ e a a ’ giˆng cua u v` v trˆn C s˜ l` c´c dınh tu e a e . do, v` ch´ng ta dˆ thˆ y l´ng giˆng cua u c´ khoang a u ˜ a a e ´ `e ’ o ’ . a ’ t´.i l´ng giˆng cua v . Bˆ dˆ du.o.c ch´.ng minh. c´ch le o a ` e ’ ’ ` o e . u v = A1 A2 An A3 An-1 An-2 u = A2k+4 ı ’ H`nh 6. Hai dınh dep v v` u khi n ch˘n. . a ˜ a ’ e o ` ` ´ ´ . a o ’ ` a ’ a Bˆ dˆ 9. Dˆ thi Hamilton tˆi dai luˆn c´ duy nhˆ t mˆt dınh dˆy du m` hai l´ng giˆng cua o . o . o o a ` e ’ ı a ’ n´ trˆn chu tr`nh Hamilton l` dınh bˆc 2. o e a. Ch´ u.ng minh. Dˆ thˆ y, nˆu dˆ thi Hamilton tˆi dai c´ 2 dınh dˆy du th` n´ c´ nhiˆu ho.n mˆt ˜ a e ´ ` ´ e o . ´ o . o ’ `a ’ ı o o ` e o. chu tr` Hamilton. Bˆy gi` ınh a o ., ta ch´.ng minh r˘ ng c´c dınh l´ng giˆng A2 v` An cua dınh dep u ` a a ’ a `e a ’ ’ . o a ’ o ˜ a ` e ´ a ’ a ’ ` ’ v = A1 luˆn l` dınh bˆc 2. Khi d´ dˆ thˆ y r˘ ng dınh dep A1 l` dınh dˆy du. Thˆt vˆy, nˆu a . . a a a . . ´ e . a o ’ ` o . ı a ’ c´ mˆt chu tr` Hamilton n`o d´ cua dˆ thi G th` do c´c dınh A2 v` An c´ bˆc l` 2 nˆn o o ınh a o a a . e dınh A1 luˆn l` dınh kˆ v´.i A2 v` An trˆn chu tr` Hamilton n`y, do d´ viˆc bˆ sung canh ’ o a ’ ` o e a e ınh a o e o. ’ . nˆi A1 v´.i tˆt ca c´c dınh kh´c cua G khˆng l`m dˆ thi c´ thˆm chu tr` Hamilton nˆu ban o´ ´ o a ’ a ’ a ’ o a ` o . o e ınh ´ e ` a o ’ o ´ o a . ınh `e . ´ e o . ’ dˆu n´ chı c´ duy nhˆ t mˆt chu tr` Hamilton. Do diˆu kiˆn tˆi dai cua G (dˆ thi nhiˆu ` o . ` e . ´ ` a o . o u ´ o ’ a o a´ o canh nhˆ t trong c´c dˆ thi c´ c`ng sˆ dınh v` c´ duy nhˆ t mˆt chu tr` Hamilton) th` A1 a . ınh ı ’ a ’ ` a ’ ` phai l` dınh dˆy du trong dˆ thi G. o .
´ ` ˆ ˆ ´ ˆ SO DO THI HAMILTON TOI DAI 227 . . Dˆ ch´.ng minh bˆ dˆ, ta gia su. ngo.c lai l` t`. A2 c´ dˆy cung e xuˆ t ph´t. Ta x´t hai ’ e u ’ e o ` ’ ’ . . a u o a a´ a e .`.ng ho.p n ch˘n v` n le v` thu du.o.c mˆt mˆu thuˆn thˆng qua viˆc xˆy du.ng mˆt chu tru o ˜ a a ’ a o a ˜ a o e a o . . . . . . tr` Hamilton th´. hai b˘ ng c´ch su. dung c´c dˆy cung dˆ d`i 3 cua dˆ thi G: ınh u ` a a ’ . a a o a . ’ o . ` a) Tru.`.ng ho.p n l` sˆ le: o . ´ a o ’ Trong h` 7, ta c´ thˆ xˆy du.ng du.o.c c´c chu tr` Hamilton tu.o.ng u.ng v´.i tru.`.ng ho.p ınh o e a’ . . a ınh ´ o o . dˆ d`i cu o a . ’ a e l` le tu.o.ng u.ng h` bˆn tr´i v` tu.o.ng u.ng v´.i dˆ d`i e ch˘ n l` h` bˆn phai a ’ ´ ınh e a a ´ o o a . ˜ a ınh e a ’ ’ cua H` 7.ınh A1 A1 A2 An A2 An An-1 An-2 A2k-1 A2k+4 A2k-1 A2k+4 A2k A2k A2k+1 A2k+1 A2k+2 H` 7. Chu tr` Hamilton du.o.c tao du.ng khi n le ınh ınh . . . ’ v=A1 v=A1 A2 An A2 An A3 An-1 A3 An-1 u = A2k+4 A2k+1 u = A2k+4 A2k+1 H`nh 8. Chu tr` Hamilton du.o.c tao du.ng khi n ch˘n ı ınh . . . ˜ a b) Tru.`.ng ho.p n l` sˆ ch˘n: o . a o a ´ ˜ Theo Bˆ dˆ 7, c´ n dınh khˆng kˆ nhau trˆn chu tr` Hamilton sinh mˆt dˆ thi con dˆy ’ e o ` o 2 ’ o `e e ınh . ` o o . `a n ’ ’ dˆ 8 th` hai dınh dep ’ a o . . ` du v` 2 dınh c`n lai sinh mˆt dˆ thi khˆng c´ canh n`o ca. Theo Bˆ ` o o . o o . a ’ o e ı ’ . ’ ’ ’ e o o a ’ cua G c´ch nhau mˆt khoang c´ch le, nˆn c´ mˆt trong ch´ng l` dınh cua dˆ thi con dˆy du a o . a . u ’ o . ` ` a ’ K n . Khˆng mˆ t tˆ o ´ a o ’ng qu´t gia su. A1 l` dınh cua dˆ thi con dˆy du K n , khi d´ l´ng giˆng A2 a ’ ’ a ’ ’ o ` . ` a ’ o a `e 2 2 ’ a n´ chı c´ thˆ c´ dˆy cung nˆi t´.i dınh c´ chı sˆ le A2x+1 n`o d´ cua dˆ thi dˆy duK n . cu o ’ o e o a ’ o´ o ’ o ´ ’ o ’ a o ` ’ o . ` a ’ 2 Gia su. dınh dep th´. hai l` u = A2k+4 nhu. trong ch´.ng minh cua Bˆ dˆ 8. Trong tru.`.ng ho.p ’ ’ ’ . u a u ’ ’ e o ` o . n`y, ta xˆy du.ng chu tr` Hamilton th´. hai nhu. bˆn tr´i cua H` 8 nˆu dˆy cung e khˆng a a . ınh u e a ’ ınh ´ e a o phˆn c´ch hai dı a a . a e ’ ’ ınh ´ a ’nh dep v` bˆn phai cua H` 8 nˆu dˆy cung e phˆn c´ch hai dınh dep n`y. e a a ’ . a . vˆy trong ca hai tru.`.ng ho.p a) v` b) ta dˆu thu du.o.c mˆt chu tr` Hamilton th´. Nhu a ’ o a ` e o ınh u . . . . hai, diˆu n`y mˆu thuˆ n v´.i gia thiˆt l` G chı c´ duy nhˆ t mˆt chu tr` Hamilton. Mˆu ` e a a ˜ a o ’ ´ e a ’ o ´ o a . ınh a thuˆ n n`y ch´.ng to r˘ ng dınh A2 v` tu.o.ng tu. dınh An khˆng c´ dˆy cung n`o xuˆ t ph´t ca ˜ a a u ’ ` a ’ a . ’ o o a a ´ a a ’ ngo`i c´c canh cua chu tr` Hamilton cua G. Nhu. vˆy c´c dınh n`y c´ bˆc l` 2, v` do d´ a a . ’ ınh ’ a a ’ . a o a a . a o
228 ˜ INH HOA, DO NHU. AN VU D` ` ˜ ˆ ’ a ’ ` ’ dınh A1 l` dınh dˆy du. a ´. 4. CHU NG MINH DINH LY 3 . ´ Ta ch´.ng minh kˆt luˆn manh ho.n cua Dinh l´ 3, r˘ ng mˆ i mˆt dˆ thi Hamilton tˆi dai u e´ a . . ’ . y ` a ˜ o o o . . ` ´ o . ’ .i mˆt dˆ thi du.o.c xˆy du.ng bo.i thuˆt to´n nˆu trong Dinh l´ 2. K´ ’ n 3 dınh d˘ng cˆ u v´ o o . a ´ a o . ` . a . ’ a. a e . y y hiˆu thuˆt to´n n`y l` Φ. Dˆ e e . a . a a a ˜ kiˆ m tra thˆ y kˆt luˆn cua Dinh l´ 3 d´ng cho tru.`.ng ho.p e ’ a´ e ´ a . ’ . y u o . n = 3 v` n = 4. Gia su. kˆt luˆn cua Dinh l´ 3 d´ng cho n ≥ 7 r˘ ng mˆi mˆt dˆ thi Hamilton a ’ ’ e ´ a ’ . . y u ` a ˜ . ` o o o . tˆi dai n ≥ 7 dınh d˘ng cˆ u v´.i mˆt dˆ thi du.o.c xˆy du.ng bo.i thuˆt to´n Φ. Ta ch´.ng minh ´ o . ’ ’ a ´ a o o o . . ` . a . ’ a. a u ´ a . ’ . y u u . ` kˆt luˆn cua dinh l´ c˜ng d´ ng cho moi dˆ thi Hamilton tˆi dai n + 1 dınh. Thˆt vˆy x´t e o . ´ o . ’ a a e . . 2 G l` dˆ thi Hamilton tˆi dai n + 1 dınh. Theo Dinh l´ 1 th` dˆ thi G c´ [ (n+1) ] + 1 canh. a o .` ´ o . ’ . y ı o . ` o 4 . Theo Bˆ dˆ 9, dˆ thi G c´ mˆt dınh dˆy du, k´ hiˆu l` An+1 v´.i hai l´ng giˆng A1 v` An ’ e o ` ` o . o o ’ . ` a ’ y e a . o a `e a c´ bˆc l` 2. Ta d´nh sˆ c´c dınh cua G bo.i A1 , A2 , . . . , An+1 theo chiˆu ngu.c kim dˆ ng hˆ o a a . a ´ o a ’ ’ ’ `e . ` o ` o doc theo chu tr` Hamilton cua n´. Ta x´t dˆ thi m´ . ınh ’ o e o . o ` .i tao th`nh G thu du.o.c t`. G b˘ ng a ` . . u a a ’ c´ch bo di c´c dınh A1 , An , An+1 v` thˆm v`o dınh A1 v` ´c canh nˆi A1 v´ ’ a ’ a e a ’ aa . ´ o o.i dınh A2 v` a dınh An−1 . Dˆ thˆ y r˘ ng dˆ thi thu du.o.c G c˜ ng chı c´ mˆt chu tr` Hamilton duy nhˆ t ’ ˜ a ` e ´ a ` o . . u ’ o o . ınh ´ a C = (A1 A2 . . . An−1 A1 ) m` thˆi. Thˆt vˆy, gia su. ngu.c lai l` G c´ mˆt chu tr`nh Hamilton a o a a . . ’ ’ . . a o o . ı th´. hai C ∗ = (A1 A2 . . . An−1 A1 ), th` dˆ thi G c´ chu tr` Hamilton th´. hai thu t`. C ∗ b˘ ng u ı o .` o ınh u u ` a c´ch thay thˆ a ´ dınh A1 bo.i d˜y dınh A1 An+1 An l` diˆu vˆ l´. M˘t kh´c dˆ thi G c´ d´ng e ’ ’ a ’ ` a e o y a . a o ` . o u (n+1)2 (n−1)2 ` thi Hamilton tˆi dai n − 1 dınh. Theo [ 4 ] + 1 − n = [ 4 ] + 1 canh, nˆn G c˜ng l` dˆ . . e u a o ´ . o ’ gia thiˆt quy nap th` G thu du.o.c b˘ ng c´ch ´p dung thuˆt to´n Φ. Lu.u y r˘ ng, mˆi dˆ thi ’ ´ e . ı . ` a a a . a. a ´ ` a ˜ ` o o . thu du . a.o.c b˘ ng c´ch ´p dung thuˆt to´n Φ dˆu c´ d´ ng hai dınh bˆc 2, l` hai dınh kˆ cua ` a a a a ` o u e ’ a a ’ ` ’ e . . . ’ ` dınh dˆy du du . . a ’ .o.c tao du.ng trong thuˆt to´n. Nhu. vˆy, dˆ thˆ y dˆ thi G thu du.o.c b˘ ng c´ch a a a ˜ a o . e ´ ` ` a a . . . . ´p dung thuˆt to´n Φ v´ a a a o.i dınh dˆy du dˆu tiˆn A ’ ` a ’ ` a e ´p tuc ´p dung thuˆt to´n . . n+1 v` sau d´ tiˆ a o e . a . a . a Φ. Nhu. vˆy kˆt luˆn cua dinh l´ c˜ ng d´ng cho c´c dˆ thi Hamilton tˆi dai n + 1 dınh. Vˆy a e . ´ a ’ . . y u u a o . ` ´ o . ’ a. dinh l´ du.o.c ch´.ng minh. . y . u ` ˆ ’ TAI LIEU THAM KHAO . [1] C. A. Barefoot, R. C. Entringer, Extremal maximal uniquely Hamiltonian, J. Graph The- ory 4 (1980) 93—100. [2] J. A. Bondy, B. Jackson, Vertices of small degree in uniquely Hamiltonian graphs, http://w.w.w.mcs.gold.ac.uk/reports/R971002.html (1997). [3] M. Aigner, Graphentheorie, Teubner, Stuttgart, 1984. [4] P.Erdos, Remark on a paper of p´sa, Publ. Math. Inst. Hungary. Acad. Sci. VII (1962) o 227—229. [5] V˜ D` H`a, Dˆ Nhu. An, Kˆt qua m´.i vˆ dˆ thi Hamilton tˆi dai, Tap ch´ Tin hoc v` u ınh o ˜ o ´ e e ` ’ o ` o . ´ o . . ı . a ` ’n hoc 22 (2006) 117—122. Diˆu khiˆ . e e [6] J. Sheehan, Graphs with exactly one Hamiltonian circuit, J. Graph Theory 1 (1977) 37—43. Nhˆn b`i ng`y 17 - 8 - 2006 a a . a