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

[Giáo trình Toán rời rạc] - Chương4 - Đồ thị Euler & Hamilton

Chia sẻ: Trần Bá Trung5 | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST
Báo xấu
190
lượt xem 41
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu " [Giáo trình Toán rời rạc] - Chương4 - Đồ thị Euler & Hamilton " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.

Chủ đề:

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

Lưu

Nội dung Text: [Giáo trình Toán rời rạc] - Chương4 - Đồ thị Euler & Hamilton

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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