[Giáo trình Toán rời rạc] - Chương7 - Tô màu Đồ thị

Tài liệu " [Giáo trình Toán rời rạc] - Chương7 - Tô màu Đồ thị " 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ương7 - Tô màu Đồ thị http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG VII ð TH PH NG VÀ TÔ MÀU ð TH T xa xưa ñã lưu truy n m t bài toán c “Ba nhà, ba gi ng”: Có ba nhà g n bacái gi ng, nhưng không có ñư ng n i th ng các nhà v i nhau cũng như không có ñư ngn i th ng các gi ng v i nhau. Có l n b t hoà v i nhau, h tìm cách làm N1 N2 N3các ñư ng khác ñ n gi ng sao cho các ñư ng nàyñôi m t không giao nhau. H có th c hi n ñư c ýñ nh ñó không? G1 G2 G3 Bài toán này có th ñư c mô hình b ng ñ th phân ñôi ñ y ñ K3,3. Câu h i banñ u có th di n ñ t như sau: Có th v K3,3 trên m t m t ph ng sao cho không có haic nh nào c t nhau? Trong chương này chúng ta s nghiên c u bài toán: có th v m t ñth trên m t m t ph ng không có các c nh nào c t nhau không. ð c bi t chúng ta s trl i bài toán ba nhà ba gi ng. Thư ng có nhi u cách bi u di n ñ th . Khi nào có th tìmñư c ít nh t m t cách bi u di n ñ th không có c nh c t nhau?7.1. ð TH PH NG.7.1.1. ð nh nghĩa: M t ñ th ñư c g i là ph ng n u nó có th v ñư c trên m t m tph ng mà không có các c nh nào c t nhau ( m t ñi m không ph i là ñi m mút c a cácc nh). Hình v như th g i là m t bi u di n ph ng c a ñ th . M t ñ th có th là ph ng ngay c khi nó thư ng ñư c v v i nh ng c nh c tnhau, vì có th v nó b ng cách khác không có các c nh c t nhau.Thí d 1: 1) M t cây, m t chu trình ñơn là m t ñ th ph ng.2) K4 là ñ th ph ng b i vì có th v l i như hình bên không có ñư ng c t nhau a b a b c d c d ð th K4 K4 v không có ñư ng c t nhau3) Xét ñ th G như trong hình a dư i ñây. Có th bi u di n G m t cách khác như tronghình b, trong ñó b t kỳ hai c nh nào cũng không c t nhau. b b d e a a e d c c 104http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p4) ð th ñ y ñ K5 là m t thí d v ñ th không ph ng (xem ð nh lý 7.2.2).7.1.2. ð nh nghĩa: Cho G là m t ñ th ph ng. M i ph n m t ph ng gi i h n b i m tchu trình ñơn không ch a bên trong nó m t chu trình ñơn khác, g i là m t mi n (h uh n) c a ñ th G. Chu trình gi i h n mi n là biên c a mi n. M i ñ th ph ng liênthông có m t mi n vô h n duy nh t (là ph n m t ph ng bên ngoài t t c các mi n h uh n). S c nh ít nh t t o thành biên g i là ñai c a G; trư ng h p n u G không có chutrình thì ñai chính là s c nh c a G.Thí d 2: 1) M t cây ch có m t mi n, ñó là mi n vô h n. c2) ð th ph ng hình bên có 5 mi n, M5 blà mi n vô h n, mi n M1 có biên abgfa, d M2mi n M2 có biên là bcdhgb, … Chu a M1trình ñơn abcdhgfa không gi i h n m t g h M4 M5mi n vì ch a bên trong nó chu trình ñơn M3 fkhác là abgfa. e7.1.3. ð nh lý (Euler, 1752): N u m t ñ th ph ng liên thông có n ñ nh, p c nh và dmi n thì ta có h th c: n − p + d = 2.Ch ng minh: Cho G là ñ th ph ng liên thông có n ñ nh, p c nh và d mi n. Ta b m t s c nh c a G ñ ñư c m t cây khung c a G. M i l n ta b m t c nh(p gi m 1) thì s mi n c a G cũng gi m 1 (d gi m 1), còn s ñ nh c a G không thay ñ i(n không ñ i). Như v y, giá tr c a bi u th c n − p + d không thay ñ i trong su t quátrình ta b b t c nh c a G ñ ñư c m t cây. Cây này có n ñ nh, do ñó có n − 1 c nh vàcây ch có m t mi n, vì v y: n − p + d = n − (n −1) + 1 = 2. H th c n − p + d = 2 thư ng g i là “h th c Euler cho hình ña di n”, vì ñư cEuler ch ng minh ñ u tiên cho hình ña di n có n ñ nh, p c nh và d m t. M i hình ñadi n có th coi là m t ñ th ph ng. Ch ng h n hình t di n ABCD và hình h pABCDA’B’C’D’ có th bi u di n b ng các ñ th dư i ñây. A B C A D D B C A’ D’ B’ C’7.1.4. H qu : Trong m t ñ th ph ng liên thông ...