Giáo trình toán rời rạc - Chương 4

- Đ ƯỜ NG ĐI EULER VÀ Đ TH EULER.
- 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? ứ ấ ả ạ.
- Đ 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.
- Đ 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.
- 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.
- Vì v y gi s G là m t đ n đ th .
- Ta s xây ậ ả ử ộ ơ ồ ị ọ ộ ỉ ủ ẽ d ng theo quy n p đ ự ạ ườ ng đi.
- Khi đó, đ ườ ng đi v i , v i+1.
- v i ) là m t chu ộ trình đ n c n tìm.
- T đó theo B đ 4.1.3, G ph i ch a m t ẵ ỗ ỉ ậ ỏ ơ ừ ổ ề ả ứ ộ chu trình đ n C.
- N u C đi qua t t c các c nh c a G thì nó chính là chu trình Euler.
- Theo gi thi t quy n p, trong ỗ ỉ ủ ẫ ậ ẵ ả ế ạ m i thành ph n liên thông c a H đ u tìm đ ỗ ầ ủ ề ượ c chu trình Euler.
- m i thành 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: ự ư.
- 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.
- 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.
- Khi đó G’ là đ ằ ạ ồ th Euler nên m i đ nh trong G’ đ u có b c ch n (k c u và 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.
- 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.
- 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”.
- M t chu trình qua m i c nh c a G g i là m t hành trình ồ ị ộ ọ ạ ủ ọ ộ trong G.
- 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).
- 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 ạ ắ ấ ề.
- Ta g i đ dài đ ọ ộ ườ ng đi ng n nh t t u đ n v là kho ng cách d(u,v).
- Do đó G T có đ ượ ừ c t G b ng cách thêm vào 3 c nh: (B, I), (I, H), (G, K) và G ằ ạ T 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 G ồ ị ậ ắ ấ ầ T.
- 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.
- Đ ƯỜ NG ĐI HAMILTON VÀ Đ TH HAMILTON.
- 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.
- đ ườ 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ũ..
- 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.
- 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.
- đ ư ườ 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.
- 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.
- 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.
- Đ ườ 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..
- Đ nh lý (Rédei): ị N u G là m t đ th có h ế ộ ồ ị ướ ng đ y đ thì G là đ th n a ầ ủ ồ ị ử Hamilton..
- Ch ng minh: ứ Gi s G=(V,E) là đ th có h ả ử ồ ị ướ ng đ y đ và ầ ủ α=(v 1 ,v 2.
- v k-1 , v k ) 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..
- a) N u có cung n i v v i v ế ố ớ 1 thì b sung v vào đ u c a đ ổ ầ ủ ườ ng đi α đ đ ể ượ c α 1 =(v, v 1 , v 2.
- b) N u t n t i ch s i (1 ế ồ ạ ỉ ố ≤ i ≤ k-1) mà t v ừ i có cung n i t i v và t v có cung n i t i ố ớ ừ ố ớ v i+1 thì ta chen v vào gi a v ữ i và v i+1 đ đ ể ượ c đ ườ ng đi s c p ơ ấ α 2 =(v 1 , v 2.
- Khi đó b sung v vào cu i c a đ ớ ổ ố ủ ườ ng đi α và đ ượ c đ ườ ng đi α 3 =(v 1 , v 2.
- N u đ th G có n đ nh thì sau n-k b sung ta s nh n đ ế ồ ị ỉ ổ ẽ ậ ượ c đ ườ ng đi Hamilton..
- Đ nh lý (Dirac, 1952): ị N u G là m t đ n đ th có n đ nh và m i đ nh c a G ế ộ ơ ồ ị ỉ ọ ỉ ủ đ u có b c không nh h n ề ậ ỏ ơ.
- n thì G là m t đ th Hamilton.
- Gi s G không có chu ứ ằ ả ứ ả ử trình Hamilton.
- 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.
- 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.
- 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 h n ỏ ơ.
- n thì G là đ th n a Hamilton.
- Do đó theo Đ nh lý ị 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..
- Đ 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.
- Đ nh lý: ị N u G là đ th phân đôi v i hai t p đ nh là V ế ồ ị ớ ậ ỉ 1 , V 2 có s đ nh cùng ố ỉ b ng n (n ằ ≥ 2) và b c c a m i đ nh l n h n ậ ủ ỗ ỉ ớ ơ.
- Đ 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 đ K ồ ị ầ ủ n (hai chu trình Hamilton g i là phân bi t n u chúng không có c nh ọ ệ ế ạ chung)..
- n chu trình Hamilton phân bi t.
- n c nh và m i chu trình Hamilton có n c nh, nên s chu ạ ỗ ạ ố.
- Đ 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à 360 ỗ 0 /(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.
- 3/2), nên theo Đ nh lý 4.2.6, nó là đ th ặ ị ồ ị Hamilton..
- V i giá tr nào c a n các đ th sau đây có chu trình Euler ? ớ ị ủ ồ ị a) K n , b) C n , c) W n , d) Q n.
- a) chu trình Euler ? b) đ ườ ng đi Euler.
- 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 Q n 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 Q 3.
- 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..
- a) Tìm m t đ ộ ườ ng đi Hamilton trong P..
- b) Ch ng minh r ng P \ {v}, v i v là m t đ nh ứ ằ ớ ộ ỉ b t kỳ c a P, là m t đ th Hamilton.
- Ch ng minh r ng đ th G cho trong ứ ằ ồ ị hình sau có đ ườ ng đi Hamilton (t s đ n r) ừ ế nh ng không có chu trình Hamilton.
- 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;.
- ồ ị ỉ ồ ị ư ả ồ ị 4) Đ th có 6 đ nh, là đ th Euler, nh ng không ph i là đ th Hamilton

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt