Xem mẫu
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
CHƯƠNG IV
ð TH EULER VÀ ð TH HAMILTON
4.1. ðƯ NG ðI EULER VÀ ð TH EULER.
Có th coi năm 1736 là năm khai sinh lý thuy t ñ th , v i vi c công b l i gi i
“bài toán v các c u Konigsberg” c a nhà toán h c l i l c Euler (1707-1783). Thành
ph Konigsberg thu c Ph (nay g i là Kaliningrad thu c Nga) ñư c chia thành b n
vùng b ng các nhánh sông Pregel, các vùng này g m hai vùng bên b sông, ñ o
Kneiphof và m t mi n n m gi a hai nhánh c a sông Pregel. Vào th k 18, ngư i ta xây
b y chi c c u n i các vùng này v i nhau.
B
B
D A
D A
C
C G
Dân thành ph t ng th c m c: “Có th nào ñi d o qua t t c b y c u, m i c u ch
m t l n thôi không?”. N u ta coi m i khu v c A, B, C, D như m t ñ nh và m i c u qua
l i hai khu v c là m t c nh n i hai ñ nh thì ta có sơ ñ c a Konigsberg là m t ña ñ th
G như hình trên.
Bài toán tìm ñư ng ñi qua t t c các c u, m i c u ch qua m t l n có th ñư c
phát bi u l i b ng mô hình này như sau: Có t n t i chu trình ñơn trong ña ñ th G ch a
t t c các c nh?
4.1.1. ð nh nghĩa: Chu trình (t.ư. ñư ng ñi) ñơn ch a t t c các c nh (ho c cung) c a
ñ th (vô hư ng ho c có hư ng) G ñư c g i là chu trình (t.ư. ñư ng ñi) Euler. M t ñ
th liên thông (liên thông y u ñ i v i ñ th có hư ng) có ch a m t chu trình (t.ư. ñư ng
ñi) Euler ñư c g i là ñ th Euler (t.ư. n a Euler).
Thí d 1:
ð th Euler
ð th không n a Euler
ð th n a Euler
54
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
ð th Euler ð th n a Euler
ði u ki n c n và ñ ñ m t ñ th là ñ th Euler ñư c Euler tìm ra vào năm 1736
khi ông gi i quy t bài toán hóc búa n i ti ng th i ñó v b y cái c u Konigsberg và ñây
là ñ nh lý ñ u tiên c a lý thuy t ñ th .
4.1.2. ð nh lý: ð th (vô hư ng) liên thông G là ñ th Euler khi và ch khi m i ñ nh
c a G ñ u có b c ch n.
Ch ng minh:
ði u ki n c n: Gi s G là ñ th Euler, t c là t n t i chu trình Euler P trong G. Khi ñó
c m i l n chu trình P ñi qua m t ñ nh nào ñó c a G thì b c c a ñ nh ñó tăng lên 2. M t
khác, m i c nh c a ñ th xu t hi n trong P ñúng m t l n. Do ñó m i ñ nh c a ñ th
ñ u có b c ch n.
4.1.3. B ñ : N u b c c a m i ñ nh c a ñ th G không nh hơn 2 thì G ch a chu trình
ñơn.
Ch ng minh: N u G có c nh b i ho c có khuyên thì kh ng ñ nh c a b ñ là hi n
nhiên. Vì v y gi s G là m t ñơn ñ th . G i v là m t ñ nh nào ñó c a G. Ta s xây
d ng theo quy n p ñư ng ñi
v v1 v2 ......
trong ñó v1 là ñ nh k v i v, còn v i i ≥ 1, ch n vi+1 là ñ nh k v i vi và vi+1 ≠ vi-1 (có th
ch n như v y vì deg(vi) ≥ 2), v0 = v. Do t p ñ nh c a G là h u h n, nên sau m t s h u
h n bư c ta ph i quay l i m t ñ nh ñã xu t hi n trư c ñó. G i k là s nguyên dương ñ u
tiên ñ vk=vi (0≤i
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
ph n trong H có ít nh t m t ñ nh chung v i chu trình C. Vì v y, ta có th xây d ng chu
trình Euler trong G như sau:
C
B t ñ u t m t ñ nh nào ñó c a chu trình C, ñi theo các c nh c a C ch ng nào chưa g p
ph i ñ nh không cô l p c a H. N u g p ph i ñ nh như v y thì ta ñi theo chu trình Euler
c a thành ph n liên thông c a H ch a ñ nh ñó. Sau ñó l i ti p t c ñi theo c nh c a C cho
ñ n khi g p ph i ñ nh không cô l p c a H thì l i theo chu trình Euler c a thành ph n liên
thông tương ng trong H, ... Quá trình s k t thúc khi ta tr v ñ nh xu t phát, t c là thu
ñư c chu trình ñi qua m i c nh c a ñ th ñúng m t l n.
4.1.4. H qu : ð th liên thông G là n a Euler (mà không là Euler) khi và ch khi có
ñúng hai ñ nh b c l trong G.
Ch ng minh: N u G là n a Euler thì t n t i m t ñư ng ñi Euler trong G t ñ nh u ñ n
ñ nh v. G i G’ là ñ th thu ñư c t G b ng cách thêm vào c nh (u,v). Khi ñó G’ là ñ
th Euler nên m i ñ nh trong G’ ñ u có b c ch n (k c u và v). Vì v y u và v là hai ñ nh
duy nh t trong G có b c l .
ð o l i, n u có ñúng hai ñ nh b c l là u và v thì g i G’ là ñ th thu ñư c t G
b ng cách thêm vào c nh (u,v). Khi ñó m i ñ nh c a G’ ñ u có b c ch n hay G’ là ñ th
Euler. B c nh (u,v) ñã thêm vào ra kh i chu trình Euler trong G’ ta có ñư c ñư ng ñi
Euler t u ñ n v trong G hay G là n a Euler.
4.1.5. Chú ý: Ta có th v ch ñư c m t chu trình Euler trong ñ th liên thông G có b c
c a m i ñ nh là ch n theo thu t toán Fleury sau ñây.
Xu t phát t m t ñ nh b t kỳ c a G và tuân theo hai quy t c sau:
1. M i khi ñi qua m t c nh nào thì xoá nó ñi; sau ñó xoá ñ nh cô l p (n u có);
2. Không bao gi ñi qua m t c u, tr phi không còn cách ñi nào khác.
u v w s
t x y z
56
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Xu t phát t u, ta có th ñi theo c nh (u,v) ho c (u,x), gi s là (u,v) (xoá (u,v)).
T v có th ñi qua m t trong các c nh (v,w), (v,x), (v,t), gi s (v,w) (xoá (v,w)). Ti p
t c, có th ñi theo m t trong các c nh (w,s), (w,y), (w,z), gi s (w,s) (xoá (w,s)). ði
theo c nh (s,y) (xoá (s,y) và s). Vì (y,x) là c u nên có th ñi theo m t trong hai c nh
(y,w), (y,z), gi s (y,w) (xoá (y,w)). ði theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá
(z,y) và z). Ti p t c ñi theo c nh (y,x) (xoá (y,x) và y). Vì (x,u) là c u nên ñi theo c nh
(x,v) ho c (x,t), gi s (x,v) (xoá (x,v)). Ti p t c ñi theo c nh (v,t) (xoá (v,t) và v), theo
c nh (t,x) (xoá c nh (t,x) và t), cu i cung ñi theo c nh (x,u) (xoá (x,u), x và u).
4.1.6. Bài toán ngư i phát thư Trung Hoa:
M t nhân viên ñi t S Bưu ði n, qua m t s ñư ng ph ñ phát thư, r i quay v
S . Ngư i y ph i ñi qua các ñư ng theo trình t nào ñ ñư ng ñi là ng n nh t?
Bài toán ñư c nhà toán h c Trung Hoa Guan nêu lên ñ u tiên (1960), vì v y
thư ng ñư c g i là “bài toán ngư i phát thư Trung Hoa”. Ta xét bài toán m t d ng
ñơn gi n như sau.
Cho ñ th liên thông G. M t chu trình qua m i c nh c a G g i là m t hành trình
trong G. Trong các hành trình ñó, hãy tìm hành trình ng n nh t, t c là qua ít c nh nh t.
Rõ ràng r ng n u G là ñ th Euler (m i ñ nh ñ u có b c ch n) thì chu trình Euler
trong G (qua m i c nh c a G ñúng m t l n) là hành trình ng n nh t c n tìm.
Ch còn ph i xét trư ng h p G có m t s ñ nh b c l (s ñ nh b c l là m t s
ch n). Khi ñó, m i hành trình trong G ph i ñi qua ít nh t hai l n m t s c nh nào ñó.
D th y r ng m t hành trình qua m t c nh (u,v) nào ñó quá hai l n thì không ph i
là hành trình ng n nh t trong G. Vì v y, ta ch c n xét nh ng hành trình T ñi qua hai l n
m t s c nh nào ñó c a G.
Ta quy ư c xem m i hành trình T trong G là m t hành trình trong ñ th Euler
GT, có ñư c t G b ng cách v thêm m t c nh song song ñ i v i nh ng c nh mà T ñi
qua hai l n. Bài toán ñ t ra ñư c ñưa v bài toán sau:
Trong các ñ th Euler GT, tìm ñ th có s c nh ít nh t (khi ñó chu trình Euler
trong ñ th này là hành trình ng n nh t).
ð nh lý (Gooodman và Hedetniemi, 1973). N u G là m t ñ th liên thông có q
c nh thì hành trình ng n nh t trong G có chi u dài
q + m(G),
trong ñó m(G) là s c nh mà hành trình ñi qua hai l n và ñư c xác ñ nh như sau:
G i V0(G) là t p h p các ñ nh b c l (2k ñ nh) c a G. Ta phân 2k ph n t c a G
thành k c p, m i t p h p k c p g i là m t phân ho ch c p c a V0(G).
Ta g i ñ dài ñư ng ñi ng n nh t t u ñ n v là kho ng cách d(u,v). ð i v i m i
phân ho ch c p Pi, ta tính kho ng cách gi a hai ñ nh trong t ng c p, r i tính t ng d(Pi).
S m(G) b ng c c ti u c a các d(Pi):
57
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
m(G)=min d(Pi).
Thí d 2: Gi i bài toán ngư i phát thư Trung Hoa cho trong ñ th sau:
D
C E
B J K F
A I H G
G GT
T p h p các ñ nh b c l VO(G)={B, G, H, K} và t p h p các phân ho ch c p là
P={P1, P2, P3}, trong ñó
P1 = {(B, G), (H, K)} → d(P1) = d(B, G)+d(H, K) = 4+1 = 5,
P2 = {(B, H), (G, K)} → d(P2) = d(B, H)+d(G, K) = 2+1 = 3,
P3 = {(B, K), (G, H)} → d(P3) = d(B, K)+d(G, H) = 3+2 = 5.
m(G) = min(d(P1), d(P2), d(P3)) = 3.
Do ñó GT có ñư c t G b ng cách thêm vào 3 c nh: (B, I), (I, H), (G, K) và GT là
ñ th Euler. V y hành trình ng n nh t c n tìm là ñi theo chu trình Euler trong GT:
A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.
4.1.7. ð nh lý: ð th có hư ng liên thông y u G là ñ th Euler khi và ch khi m i
ñ nh c a G ñ u có b c vào b ng b c ra.
Ch ng minh: Ch ng minh tương t như ch ng minh c a ð nh lý 4.1.2 và ñi u ki n ñ
cũng c n có b ñ dư i ñây tương t như B ñ 4.1.3.
4.1.8. B ñ : N u b c vào và b c ra c a m i ñ nh c a ñ th có hư ng G không nh
hơn 1 thì G ch a chu trình ñơn.
4.1.9. H qu : ð th có hư ng liên thông y u G là n a Euler (mà không là Euler) khi
và ch khi t n t i hai ñ nh x và y sao cho:
dego(x) = degt(x)+1, degt(y) = dego(y)+1, degt(v) = dego(v), ∀v∈V, v ≠ x, v ≠ y.
Ch ng minh: Ch ng minh tương t như H qu 4.1.4.
4.2. ðƯ NG ðI HAMILTON VÀ ð TH HAMILTON.
Năm 1857, nhà toán h c ngư i Ailen là Hamilton(1805-1865) ñưa ra trò chơi “ñi
vòng quanh th gi i” như sau.
Cho m t hình th p nh di n ñ u (ña di n ñ u có 12 m t, 20 ñ nh và 30 c nh), m i
ñ nh c a hình mang tên m t thành ph n i ti ng, m i c nh c a hình (n i hai ñ nh) là
ñư ng ñi l i gi a hai thành ph tương ng. Xu t phát t m t thành ph , hãy tìm ñư ng
ñi thăm t t c các thành ph khác, m i thành ph ch m t l n, r i tr v ch cũ.
58
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Trư c Hamilton, có th là t th i Euler, ngư i ta ñã bi t ñ n m t câu ñ hóc búa
v “ñư ng ñi c a con mã trên bàn c ”. Trên bàn c , con mã ch có th ñi theo ñư ng
chéo c a hình ch nh t 2 x 3 ho c 3 x 2 ô vuông. Gi s bàn c có 8 x 8 ô vuông. Hãy
tìm ñư ng ñi c a con mã qua ñư c t t c các ô c a bàn c , m i ô ch m t l n r i tr l i
ô xu t phát.
Bài toán này ñư c nhi u nhà toán h c chú ý, ñ c bi t là Euler, De Moivre,
Vandermonde, ...
Hi n nay ñã có nhi u l i gi i và phương pháp gi i cũng có r t nhi u, trong ñó có
quy t c: m i l n b trí con mã ta ch n v trí mà t i v trí này s ô chưa dùng t i do nó
kh ng ch là ít nh t.
M t phương pháp khác d a trên tính ñ i x ng c a hai n a bàn c . Ta tìm hành
trình c a con mã trên m t n a bàn c , r i l y ñ i x ng cho n a bàn c còn l i, sau ñó
n i hành trình c a hai n a ñã tìm l i v i nhau.
Trò chơi và câu ñ trên d n t i vi c kh o sát m t l p ñ th ñ c bi t, ñó là ñ th
Hamilton.
4.2.1. ð nh nghĩa: Chu trình (t.ư. ñư ng ñi) sơ c p ch a t t c các ñ nh c a ñ th (vô
hư ng ho c có hư ng) G ñư c g i là chu trình (t.ư. ñư ng ñi) Hamilton. M t ñ th có
ch a m t chu trình (t.ư. ñư ng ñi) Hamilton ñư c g i là ñ th Hamilton (t.ư. n a
Hamilton).
Thí d 3: 1) C
J
K I
B D
L O P H
N Q
M R G
T S F
A E
ð th Hamilton (hình th p nh di n ñ u bi u di n trong m t ph ng) v i chu trình
Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (ñư ng tô ñ m).
2) Trong m t ñ t thi ñ u bóng bàn có n (n ≥ 2) ñ u th tham gia. M i ñ u th g p t ng
ñ u th khác ñúng m t l n. Trong thi ñ u bóng bàn ch có kh năng th ng ho c thua.
59
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Ch ng minh r ng sau ñ t thi ñ u có th x p t t c các ñ u th ñ ng thành m t hàng d c,
ñ ngư i ñ ng sau th ng ngư i ñ ng ngay trư c anh (ch ) ta.
Xét ñ th có hư ng G g m n ñ nh sao cho m i ñ nh ng v i m t ñ u th và có
m t cung n i t ñ nh u ñ n ñ nh v n u ñ u th ng v i u th ng ñ u th ng v i v. Như
v y, ñ th G có tính ch t là v i hai ñ nh phân bi t b t kỳ u và v, có m t và ch m t
trong hai cung (u,v) ho c (v,u), ñ th như th ñư c g i là ñ th có hư ng ñ y ñ . T
M nh ñ 4.2.2 dư i ñây, G là m t ñ th n a Hamilton. Khi ñó ñư ng ñi Hamilton trong
G cho ta s s p x p c n tìm.
3) M t l i gi i v hành trình c a con mã trên bàn c 8 x 8:
D
T
ðư ng ñi Hamilton tương t ñư ng ñi Euler trong cách phát bi u: ðư ng ñi
Euler qua m i c nh (cung) c a ñ th ñúng m t l n, ñư ng ñi Hamilton qua m i ñ nh
c a ñ th ñúng m t l n. Tuy nhiên, n u như bài toán tìm ñư ng ñi Euler trong m t ñ
th ñã ñư c gi i quy t tr n v n, d u hi u nh n bi t m t ñ th Euler là khá ñơn gi n và
d s d ng, thì các bài toán v tìm ñư ng ñi Hamilton và xác ñ nh ñ th Hamilton l i
khó hơn r t nhi u. ðư ng ñi Hamilton và ñ th Hamilton có nhi u ý nghĩa th c ti n và
ñã ñư c nghiên c u nhi u, nhưng v n còn nh ng khó khăn l n chưa ai vư t qua ñư c.
Ngư i ta ch m i tìm ñư c m t vài ñi u ki n ñ ñ nh n bi t m t l p r t nh các
ñ th Hamilton và ñ th n a Hamilton. Sau ñây là m t vài k t qu .
4.2.2. ð nh lý (Rédei): N u G là m t ñ th có hư ng ñ y ñ thì G là ñ th n a
Hamilton.
60
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Ch ng minh: Gi s G=(V,E) là ñ th có hư ng ñ y ñ và α=(v1,v2, ..., vk-1, vk) là
ñư ng ñi sơ c p b t kỳ trong ñ th G.
-- N u α ñã ñi qua t t c các ñ nh c a G thì nó là m t ñư ng ñi Hamilton c a G.
-- N u trong G còn có ñ nh n m ngoài α, thì ta có th b sung d n các ñ nh này vào α và
cu i cùng nh n ñư c ñư ng ñi Hamilton.
Th t v y, gi s v là ñ nh tuỳ ý không n m trên α.
a) N u có cung n i v v i v1 thì b sung v vào ñ u c a ñư ng ñi α ñ ñư c α1=(v, v1, v2,
..., vk-1, vk).
b) N u t n t i ch s i (1 ≤ i ≤ k-1) mà t vi có cung n i t i v và t v có cung n i t i vi+1
thì ta chen v vào gi a vi và vi+1 ñ ñư c ñư ng ñi sơ c p α2=(v1, v2, ..., vi, v, vi+1, ..., vk).
c) N u c hai kh năng trên ñ u không x y ra nghĩa là v i m i i (1 ≤ i ≤ k) vi ñ u có
cung ñi t i v. Khi ñó b sung v vào cu i c a ñư ng ñi α và ñư c ñư ng ñi α3=(v1, v2,
..., vk-1, vk, v).
N u ñ th G có n ñ nh thì sau n-k b sung ta s nh n ñư c ñư ng ñi Hamilton.
4.2.3. ð nh lý (Dirac, 1952): N u G là m t ñơn ñ th có n ñ nh và m i ñ nh c a G
n
ñ u có b c không nh hơn thì G là m t ñ th Hamilton.
2
Ch ng minh: ð nh lý ñư c ch ng minh b ng ph n ch ng. Gi s G không có chu trình
Hamilton. Ta thêm vào G m t s ñ nh m i và n i m i ñ nh m i này v i m i ñ nh c a G,
ta ñư c ñ th G’. Gi s k (>0) là s t i thi u các ñ nh c n thi t ñ G’ ch a m t chu
trình Hamilton. Như v y, G’ có n+k ñ nh.
y
b
a
a'
b’
G i P là chu trình Hamilton ayb ...a trong G’, trong ñó a và b là các ñ nh c a G,
còn y là m t trong các ñ nh m i. Khi ñó b không k v i a, vì n u trái l i thì ta có th b
ñ nh y và ñư c chu trình ab ...a, mâu thu n v i gi thi t v tính ch t nh nh t c a k.
Ngoài ra, n u a’ là m t ñ nh k nào ñó c a a (khác v i y) và b’ là ñ nh n i ti p
ngay a’ trong chu trình P thì b’ không th là ñ nh k v i b, vì n u trái l i thì ta có th
thay P b i chu trình aa’ ...bb’ ... a, trong ñó không có y, mâu thu n v i gi thi t v tính
ch t nh nh t c a k.
Như v y, v i m i ñ nh k v i a, ta có m t ñ nh không k v i b, t c là s ñ nh
n
không k v i b không th ít hơn s ñ nh k v i a (s ñ nh k v i a không nh hơn +k).
2
61
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
n
M t khác, theo gi thi t s ñ nh k v i b cũng không nh hơn +k. Vì không có ñ nh
2
nào v a k v i b l i v a không k v i b, nên s ñ nh c a G’ không ít hơn
n
2( +k)=n+2k, mâu thu n v i gi thi t là s ñ nh c a G’ b ng n+k (k>0). ð nh lý ñư c
2
ch ng minh.
4.2.4. H qu : N u G là ñơn ñ th có n ñ nh và m i ñ nh c a G ñ u có b c không nh
n −1
hơn thì G là ñ th n a Hamilton.
2
Ch ng minh: Thêm vào G m t ñ nh x và n i x v i m i ñ nh c a G thì ta nh n ñư c
n +1
ñơn ñ th G’ có n+1 ñ nh và m i ñ nh có b c không nh hơn . Do ñó theo ð nh lý
2
4.2.3, trong G’ có m t chu trình Hamilton. B x ra kh i chu trình này, ta nh n ñư c
ñư ng ñi Hamilton trong G.
4.2.5. ð nh lý (Ore, 1960): N u G là m t ñơn ñ th có n ñ nh và b t kỳ hai ñ nh nào
không k nhau cũng có t ng s b c không nh hơn n thì G là m t ñ th Hamilton.
4.2.6. ð nh lý: N u G là ñ th phân ñôi v i hai t p ñ nh là V1, V2 có s ñ nh cùng
n
b ng n (n ≥ 2) và b c c a m i ñ nh l n hơn thì G là m t ñ th Hamilton.
2
Thí d 4: e d
a
f e
a b c d a b c
g f
h g
ð th G này có 8 ñ nh, ñ nh nào cũng ð th G’ này có 5 ñ nh b c 4 và 2 ñ nh
có b c 4, nên theo ð nh lý 4.2.3, G là b c 2 k nhau nên t ng s b c c a hai ñ nh
ñ th Hamilton. không k nhau b t kỳ b ng 7 ho c 8, nên
theo ð nh lý 4.2.5, G’ là ñ th Hamilton.
a b b
ð th phân ñôi này có b c c a m i ñ nh b ng 2
ho c 3 (> 3/2), nên theo ð nh lý 4.2.6, nó là ñ
d e f th Hamilton.
62
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
4.2.7. Bài toán s p x p ch ng i:
Có n ñ i bi u t n nư c ñ n d h i ngh qu c t . M i ngày h p m t l n ng i
quanh m t bàn tròn. H i ph i b trí bao nhiêu ngày và b trí như th nào sao cho trong
m i ngày, m i ngư i có hai ngư i k bên là b n m i. Lưu ý r ng n ngư i ñ u mu n làm
quen v i nhau.
Xét ñ th g m n ñ nh, m i ñ nh ng v i m i ngư i d h i ngh , hai ñ nh k nhau
khi hai ñ i bi u tương ng mu n làm quen v i nhau. Như v y, ta có ñ th ñ y ñ Kn.
ð th này là Hamilton và rõ ràng m i chu trình Hamilton là m t cách s p x p như yêu
c u c a bài toán. Bái toán tr thành tìm các chu trình Hamilton phân bi t c a ñ th ñ y
ñ Kn (hai chu trình Hamilton g i là phân bi t n u chúng không có c nh chung).
n −1
ð nh lý: ð th ñ y ñ Kn v i n l và n ≥ 3 có ñúng chu trình Hamilton phân bi t.
2
n(n − 1)
Ch ng minh: Kn có c nh và m i chu trình Hamilton có n c nh, nên s chu
2
n −1
trình Hamilton phân bi t nhi u nh t là .
2
5
3
2 1 n
4
Gi s các ñ nh c a Kn là 1, 2, ..., n. ð t ñ nh 1 t i tâm c a m t ñư ng tròn và các ñ nh
2, ..., n ñ t cách ñ u nhau trên ñư ng tròn (m i cung là 3600/(n-1) sao cho ñ nh l n m
n a ñư ng tròn trên và ñ nh ch n n m n a ñư ng tròn dư i. Ta có ngay chu trình
Hamilton ñ u tiên là 1,2, ..., n,1. Các ñ nh ñư c gi c ñ nh, xoay khung theo chi u kim
ñ ng h v i các góc quay:
360 0 360 0 360 0 n − 3 360 0
, 2. , 3. , ..., . ,
n −1 n −1 n −1 2 n −1
n−3 n −1
ta nh n ñư c khung phân bi t v i khung ñ u tiên. Do ñó ta có chu trình
2 2
Hamilton phân bi t.
Thí d 5: Gi i bài toán s p x p ch ng i v i n=11.
Có (11−1)/2=5 cách s p x p ch ng i phân bi t như sau:
1 2 3 4 5 6 7 8 9 10 11 1
1 3 5 2 7 4 9 6 11 8 10 1
1 5 7 3 9 2 11 4 10 6 8 1
1 7 9 5 11 3 10 2 8 4 6 1
63
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
1 9 11 7 10 5 8 3 6 2 4 1
5 7 5 7 5 7
3 9 3 9 3 9
2 1 1 2 1 1 2 1 1
4 1 4 1 4 1
6 8 6 8 6 8
5 7 5 7
3 9 3 9
2 1 1 2 1 1
4 1 4 1
6 8 6 8
BÀI T P CHƯƠNG IV:
1. V i giá tr nào c a n các ñ th sau ñây có chu trình Euler ?
a) Kn, b) Cn, c) Wn, d) Qn.
2. V i giá tr nào c a m và n các ñ th phân ñôi ñ y ñ Km,n có:
a) chu trình Euler ? b) ñư ng ñi Euler ?
3. V i giá tr nào c a m và n các ñ th phân ñôi ñ y ñ Km,n có chu trình Hamilton ?
4. Ch ng minh r ng ñ th l p phương Qn là m t ñ th Hamilton. V cây li t kê t t c
các chu trình Hamilton c a ñ th l p phương Q3.
5. Trong m t cu c h p có 15 ngư i m i ngày ng i v i nhau quanh m t bàn tròn m t
l n. H i có bao nhiêu cách s p x p sao cho m i l n ng i h p, m i ngư i có hai ngư i
bên c nh là b n m i, và s p x p như th nào ?
6. Hi u trư ng m i 2n (n ≥ 2) sinh viên gi i ñ n d ti c. M i sinh viên gi i quen ít nh t
n sinh viên gi i khác ñ n d ti c. Ch ng minh r ng luôn luôn có th x p t t c các sinh
viên gi i ng i xung quanh m t bàn tròn, ñ m i ngư i ng i gi a hai ngư i mà sinh viên
ñó quen.
7. M t ông vua ñã xây d ng m t lâu ñài ñ c t báu v t. Ngư i ta tìm th y sơ ñ c a lâu
ñài (hình sau) v i l i d n: mu n tìm báu v t, ch c n t m t trong các phòng bên ngoài
cùng (s 1, 2, 6, 10, ...), ñi qua t t c các c a phòng, m i c a ch m t l n; báu v t ñư c
gi u sau c a cu i cùng.
Hãy tìm nơi gi u báu v t
64
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
1 2
3 4 5 6
7 8 9 10
11 12 13 14
15
16 17 18
20 21 19
8. ð th cho trong hình sau g i là ñ th Peterson P.
a
a) Tìm m t ñư ng ñi Hamilton trong P.
b) Ch ng minh r ng P \ {v}, v i v là m t
e g b
ñ nh b t kỳ c a P, là m t ñ th Hamilton.
f h
k i
d c
9. Gi i bài toán ngư i phát thư Trung Hoa v i ñ th cho trong hình sau:
s
10. Ch ng minh r ng ñ th G cho trong d
r
hình sau có ñư ng ñi Hamilton (t s ñ n r) c
nhưng không có chu trình Hamilton. e
g
b
f
a h
65
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
11. Cho thí d v :
1) ð th có m t chu trình v a là chu trình Euler v a là chu trình Hamilton;
2) ð th có m t chu trình Euler và m t chu trình Hamilton, nhưng hai chu trình ñó
không trùng nhau;
3) ð th có 6 ñ nh, là ñ th Hamilton, nhưng không ph i là ñ th Euler;
4) ð th có 6 ñ nh, là ñ th Euler, nhưng không ph i là ñ th Hamilton.
12. Ch ng minh r ng con mã không th ñi qua t t c các ô c a m t bàn c có 4 x 4 ho c
5 x 5 ô vuông, m i ô ch m t l n, r i tr v ch cũ.
66
nguon tai.lieu . vn
