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

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.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương4 - Đồ thị Euler & Hamilton 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 HAMILTON4.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ànhph Konigsberg thu c Ph (nay g i là Kaliningrad thu c Nga) ñư c chia thành b nvù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, ñ oKneiphof 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âyb 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 chm 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 qual 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 ñ thG 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 ñư cphá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 at 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 54http://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 1736khi ô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à ñâylà ñ 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 ñ nhc 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 tkhá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 nnhiê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âyd 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ó thch 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 uh 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 ñ utiên ñ vk=vi (0≤ihttp://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pph 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 chutrình Euler trong G như sau: CB 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 pph 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 Eulerc 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ênthô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 ñ nhduy 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 Gb 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à ñ thEuler. B c nh (u,v) ñã thêm vào ra kh i chu trình Euler trong G’ ta có ñư c ñư ng ñiEuler 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 cc a m i ñ nh là ch n theo thu t toán Fleury sau ñây. X ...