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ương7 - Tô màu Đồ thị

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

Thêm vào BST
Báo xấu
142
lượt xem 35
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ươ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.

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ương7 - Tô màu Đồ thị

  1. 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 ba cá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ó ñư ng n 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 N3 cá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ó hai c 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 tr l 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 t ph 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ác c 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 t nhau, 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 nhau 3) 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ư trong hì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 104
  2. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 4) ð 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 t chu 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 u h 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ên thô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 u h 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ó chu trì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. c 2) ð th ph ng hình bên có 5 mi n, M5 b là mi n vô h n, mi n M1 có biên abgfa, d M2 mi n M2 có biên là bcdhgb, … Chu a M1 trình ñơn abcdhgfa không gi i h n m t g h M4 M5 mi n vì ch a bên trong nó chu trình ñơn M3 f khác là abgfa. e 7.1.3. ð nh lý (Euler, 1752): N u m t ñ th ph ng liên thông có n ñ nh, p c nh và d mi 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ì ñư c Euler 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 ña di n có th coi là m t ñ th ph ng. Ch ng h n hình t di n ABCD và hình h p ABCDA’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 tuỳ ý, luôn t n t i ít nh t m t ñ nh có b c không vư t quá 5. 105
  3. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Ch ng minh: Trong ñ th ph ng m i mi n ñư c bao b ng ít nh t 3 c nh. M t khác, m i c nh có th n m trên biên c a t i ña hai mi n, nên ta có 3d ≤ 2p. N u trong ñ th ph ng mà t t c các ñ nh ñ u có b c không nh hơn 6 thì do m i ñ nh c a ñ th ph i là ñ u mút c a ít nh t 6 c nh mà m i c nh l i có hai ñ u mút nên ta có 6n ≤ 2p hay 3n ≤ p. T ñó suy ra 3d+3n ≤ 2p+p hay d+n ≤ p, trái v i h th c Euler d+n=p+2. 7.2. ð TH KHÔNG PH NG. 7.2.1. ð nh lý: ð th phân ñôi ñ y ñ K3,3 là m t ñ th không ph ng. Ch ng minh: Gi s K3,3 là ñ th ph ng. Khi ñó ta có m t ñ th ph ng v i 6 ñ nh (n=6) và 9 c nh (p=9), nên theo ð nh lý Euler ñ th có s mi n là d=p−n+2=5. ñây, mõi c nh chung cho hai mi n, mà m i mi n có ít nh t 4 c nh. Do ñó 4d≤2p, t c là 4x5≤2x9, vô lý. Như v y ñ nh lý này cho ta l i gi i c a bài toán “Ba nhà ba gi ng”, nghĩa là không th th c hi n ñư c vi c làm các ñư ng khác ñ n gi ng sao cho các ñư ng này ñôi m t không giao nhau. 7.2.2. ð nh lý: ð th ñ y ñ K5 là m t ñ th không ph ng. Ch ng minh: Gi s K5 là ñ th ph ng. Khi ñó ta có m t ñ th ph ng v i 5 ñ nh (n=5) và 10 c nh (p=10), nên theo ð nh lý Euler ñ th có s mi n là d=p−n+2=7. Trong K5, m i mi n có ít nh t 3c nh, m i c nh chung cho hai mi n, vì v y 3d≤2n, t c là 3x7≤2x10, vô lý. 7.2.3. Chú ý: Ta ñã th y K3,3 và K5 là không ph ng. Rõ ràng, m t ñ th là không ph ng n u nó ch a m t trong hai ñ th này như là ñ th con. Hơn n a, t t c các ñ th không ph ng c n ph i ch a ñ th con nh n ñư c t K3,3 ho c K5 b ng m t s phép toán cho phép nào ñó. Cho ñ th G, có c nh (u,v). N u ta xoá c nh (u,v), r i thêm ñ nh w cùng v i hai c nh (u,w) và (w,v) thì ta nói r ng ta ñã thêm ñ nh m i w (b c 2) ñ t trên c nh (u,v) c a G. ð th G’ ñư c g i là ñ ng phôi v i ñ th G n u G’ có ñư c t G b ng cách thêm các ñ nh m i (b c 2) ñ t trên các c nh c a G. Thí d 3: a a u v u w v d b c b c G G’ 106
  4. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ð th G là ñ ng phôi v i ñ th G’. Nhà toán h c Ba Lan, Kuratowski, ñã thi t l p ñ nh lý sau ñây vào năm 1930. ð nh lý này ñã bi u th ñ c ñi m c a các ñ th ph ng nh khái ni m ñ th ñ ng phôi. 7.2.4. ð nh lý (Kuratowski): ð th là không ph ng khi và ch khi nó ch a m t ñ th con ñ ng phôi v i K3,3 ho c K5. Thí d 4: b b a b a c f c a c d f d e e e d f Hình 1 Hình 2 Hình 3 ð th trong hình 1 và 2 là ñ th ph ng. Các ñ th này có 6 ñ nh, nhưng không ch a ñ th con K3,3 ñư c vì có ñ nh b c 2, trong khi t t c các ñ nh c a K3,3 ñ u có b c 3; cũng không th ch a ñ th con K5 ñư c vì có nh ng ñ nh b c nh hơn 4, trong khi t t c các ñ nh c a K5 ñ u có b c 4. ð th trong hình 3 là ñ th không ph ng vì n u xoá ñ nh b cùng các c nh (b,a), (b,c), (b,f) ta ñư c ñ th con là K5. 7.3. TÔ MÀU ð TH . 7.3.1. Tô màu b n ñ : M i b n ñ có th coi là m t ñ th ph ng. Trong m t b n ñ , ta coi hai mi n có chung nhau m t ñư ng biên là hai mi n k nhau (hai mi n ch có chung nhau m t ñi m biên không ñư c coi là k nhau). M t b n ñ thư ng ñư c tô màu, sao cho hai mi n k nhau ñư c tô hai màu khác nhau. Ta g i m t cách tô màu b n ñ như v y là m t cách tô màu ñúng. ð ñ m b o ch c ch n hai mi n k nhau không bao gi có màu trùng nhau, chúng ta tô m i mi n b ng m t màu khác nhau. Tuy nhiên vi c làm ñó nói chung là không h p lý. N u b n ñ có nhi u mi n thì s r t khó phân bi t nh ng màu g n gi ng nhau. Do v y ngư i ta ch dùng m t s màu c n thi t ñ tô b n ñ . M t bài toán ñư c ñ t ra là: xác ñ nh s màu t i thi u c n có ñ tô màu ñúng m t b n ñ . Thí d 5: B n ñ trong hình bên có 6 mi n, nhưng ch c n có 3 màu (vàng, ñ , xanh) M3 ñ tô ñúng b n ñ này. Ch ng h n, màu vàng M1 M2 M4 ñư c tô cho M1 và M4, màu ñ ñư c tô cho M2 M6 M5 và M6, màu xanh ñư c tô cho M3 và M5. 107
  5. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 7.3.2. Tô màu ñ th : M i b n ñ trên m t ph ng có th bi u di n b ng m t ñ th , trong ñó m i mi n c a b n ñ ñư c bi u di n b ng m t ñ nh; các c nh n i hai ñ nh, n u các mi n ñư c bi u di n b ng hai ñ nh này là k nhau. ð th nh n ñư c b ng cách này g i là ñ th ñ i ng u c a b n ñ ñang xét. Rõ ràng m i b n ñ trên m t ph ng ñ u có ñ th ñ i ng u ph ng. Bài toán tô màu các mi n c a b n ñ là tương ñương v i bài toán tô màu các ñ nh c a ñ th ñ i ng u sao cho không có hai ñ nh li n k nhau có cùng m t màu, mà ta g i là tô màu ñúng các ñ nh c a ñ th . S màu ít nh t c n dùng ñ tô màu ñúng ñ th G ñư c g i là s c s c a ñ th G và ký hi u là χ(G). Thí d 6: a b c d e f g h Ta th y r ng 4 ñ nh b, d, g, e ñôi m t k nhau nên ph i ñư c tô b ng 4 màu khác nhau. Do ñó χ(G) ≥ 4. Ngoài ra, có th dùng 4 màu ñánh s 1, 2, 3, 4 ñ tô màu G như sau: 3 1 2 2 4 4 3 1 Như v y χ(G) = 4. 7.3.3. M nh ñ : N u ñ th G ch a m t ñ th con ñ ng phôi v i ñ th ñ y ñ Kn thì χ(G) ≥ n. Ch ng minh: G i H là ñ th con c a G ñ ng phôi v i Kn thì χ(H) ≥ n. Do ñó χ(G) ≥ n. 7.3.4. M nh ñ : N u ñơn ñ th G không ch a chu trình ñ dài l thì χ(G) =2. Ch ng minh: Không m t tính ch t t ng quát có th gi s G liên thông. C ñ nh ñ nh u c a G và tô nó b ng màu 0 trong hai màu 0 và 1. V i m i ñ nh v c a G, t n t i m t ñư ng ñi t u ñ n v, n u ñư ng này có ñ dài ch n thì tô màu 0 cho v, n u ñư ng này có ñ dài l thì tô màu 1 cho v. N u có hai ñư ng ñi mang tính ch n l khác nhau cùng n i 108
  6. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p u v i v thì d th y r ng G ph i ch a ít nh t m t chu trình ñ dài l . ði u mâu thu n này cho bi t hai màu 0 và 1 tô ñúng ñ th G. 7.3.5. M nh ñ : V i m i s nguyên dương n, t n t i m t ñ th không ch a K3 và có s c s b ng n. Ch ng minh: Ta ch ng minh m nh ñ b ng quy n p theo n. Trư ng h p n=1 là hi n nhiên. Gi s ta có ñ th Gn v i kn ñ nh, không ch a K3 và có s c s là n. Ta xây d ng ñ th Gn+1 g m n b n sao c a Gn và thêm knn ñ nh m i theo cách sau: m i b th t (v1, v2, …, vn), v i vi thu c b n sao Gn th i, s tương ng v i m t ñ nh m i, ñ nh m i này ñư c n i b ng n c nh m i ñ n các ñ nh v1, v2, …, vn. D th y r ng Gn+1 không ch a K3 và có s c s là n+1. 7.3.6. ð nh lý (ð nh lý 5 màu c a Kempe-Heawood): M i ñ th ph ng ñ u có th tô ñúng b ng 5 màu. Ch ng minh: Cho G là m t ñ th ph ng. Không m t tính ch t t ng quát có th xem G là liên thông và có s ñ nh n ≥ 5. Ta ch ng minh G ñư c tô ñúng b i 5 màu b ng quy n p theo n. Trư ng h p n=5 là hi n nhiên. Gi s ñ nh lý ñúng cho t t c các ñ th ph ng có s ñ nh nh hơn n. Xét G là ñ th ph ng liên thông có n ñ nh. Theo H qu 7.1.4, trong G t n t i ñ nh a v i deg(a) ≤ 5. Xoá ñ nh a và các c nh liên thu c v i nó, ta nh n ñư c ñ th ph ng G’ có n−1 ñ nh. Theo gi thi t quy n p, có th tô ñúng các ñ nh c a G’ b ng 5 màu. Sau khi tô ñúng G’ r i, ta tìm cách tô ñ nh a b ng m t màu khác v i màu c a các ñ nh k nó, nhưng v n là m t trong 5 màu ñã dùng. ði u này luôn th c hi n ñư c khi deg(a) < 5 ho c khi deg(a)=5 nhưng 5 ñ nh k a ñã ñư c tô b ng 4 màu tr xu ng. Ch còn ph i xét trư ng h p deg(a)=5 mà 5 ñ nh k a là b, c, d, e ,f ñã ñư c tô b ng 5 màu r i. Khi ñó trong 5 ñ nh b, c, d, e ,f ph i có 2 ñ nh không k nhau, vì n u 5 ñ nh ñó ñôi m t k nhau thì b c d e f là ñ th ñ y ñ K5 và ñây là m t ñ th không ph ng, do ñó G không ph ng, trái v i gi thi t. Gi s b và d không k nhau (Hình 1). f (5) f f (5) a (1) a a e (2) e e (2) b (1) b d d (1) c c (2) c (2) m n (3) m n (4) m n Hình 1 Hình 2 Hình 3 109
  7. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Xoá 2 ñ nh b và d và cho k a nh ng ñ nh trư c ñó k b ho c k d mà không k a (Hình 2), ta ñư c ñ th m i G’’ có n−2 ñ nh. Theo gi thi t quy n p, ta có th tô ñúng G’’ b ng 5 màu. Sau khi các ñ nh c a G’’ ñư c tô ñúng r i (Hình 2), ta d ng l i 2 ñ nh b và d, r i tô b và d b ng màu ñã tô cho a (màu 1, Hình 3), còn a thì ñư c tô l i b ng màu khác v i màu c a b, c, d, e, f. Vì b và d không k nhau ñã ñư c tô b ng cùng màu 1, nên v i 5 ñ nh này ch m i dùng h t nhi u l m 4 màu.. Do ñó G ñư c tô ñúng b ng 5 màu. 7.3.7. ð nh lý (ð nh lý 4 màu c a Appel-Haken): M i ñ th ph ng ñ u có th tô ñúng b ng 4 màu. ð nh lý B n màu ñ u tiên ñư c ñưa ra như m t ph ng ñoán vào năm 1850 b i m t sinh viên ngư i Anh tên là F. Guthrie và cu i cùng ñã ñư c hai nhà toán h c M là Kenneth Appel và Wolfgang Haken ch ng minh vào năm 1976. Trư c năm 1976 cũng ñã có nhi u ch ng minh sai, mà thông thư ng r t khó tìm th y ch sai, ñã ñư c công b . Hơn th n a ñã có nhi u c g ng m t cách vô ích ñ tìm ph n thí d b ng cách c v b n ñ c n hơn b n màu ñ tô nó. Có l m t trong nh ng ch ng minh sai n i ti ng nh t trong toán h c là ch ng minh sai “bài toán b n màu” ñư c công b năm 1879 b i lu t sư, nhà toán h c nghi p dư Luân ðôn tên là Alfred Kempe. Nh công b l i gi i c a “bài toán b n màu”, Kempe ñư c công nh n là h i viên H i Khoa h c Hoàng gia Anh. Các nhà toán h c ch p nh n cách ch ng minh c a ông ta cho t i 1890, khi Percy Heawood phát hi n ra sai l m trong ch ng minh c a Kempe. M t khác, dùng phương pháp c a Kempe, Heawood ñã ch ng minh ñư c “bài toán năm màu” (t c là m i b n ñ có th tô ñúng b ng 5 màu). Như v y, Heawood m i gi i ñư c “bài toán năm màu”, còn “bài toán b n màu” v n còn ñó và là m t thách ñ ñ i v i các nhà toán h c trong su t g n m t th k . Vi c tìm l i gi i c a “bài toán b n màu” ñã nh hư ng ñ n s phát tri n theo chi u hư ng khác nhau c a lý thuy t ñ th . Mãi ñ n năm 1976, khai thác phương pháp c a Kempe và nh công c máy tính ñi n t , Appel và Haken ñã tìm ra l i gi i c a “bài toán b n màu”. Ch ng minh c a h d a trên s phân tích t ng trư ng h p m t cách c n th n nh máy tính. H ñã ch ra r ng n u “bài toán b n màu” là sai thì s có m t ph n thí d thu c m t trong g n 2000 lo i khác nhau và ñã ch ra không có lo i nào d n t i ph n thí d c . Trong ch ng minh c a mình h ñã dùng hơn 1000 gi máy. Cách ch ng minh này ñã gây ra nhi u cu c tranh cãi vì máy tính ñã ñóng vai trò quan tr ng bi t bao. Ch ng h n, li u có th có sai l m trong chương trình và ñi u ñó d n t i k t qu sai không? Lý lu n c a h có th c s là m t ch ng minh hay không, n u nó ph thu c vào thông tin ra t m t máy tính không ñáng tin c y? 110
  8. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 7.3.8. Nh ng ng d ng c a bài toán tô màu ñ th : 1) L p l ch thi: Hãy l p l ch thi trong trư ng ñ i h c sao cho không có sinh viên nào có hai môn thi cùng m t lúc. Có th gi i bài toán l p l ch thi b ng mô hình ñ th , v i các ñ nh là các môn thi, có m t c nh n i hai ñ nh n u có sinh viên ph i thi c hai môn ñư c bi u di n b ng hai ñ nh này. Th i gian thi c a m i môn ñư c bi u th b ng các màu khác nhau. Như v y vi c l p l ch thi s tương ng v i vi c tô màu ñ th này. Ch ng h n, có 7 môn thi c n x p l ch. Gi s các môn h c ñu c ñánh s t 1 t i 7 và các c p môn thi sau có chung sinh viên: 1 và 2, 1 và 3, 1 và 4, 1 và 7, 2 và 3, 2 và 4, 2 và 5, 2 và 7, 3 và 4, 3 và 6, 3 và 7, 4 và 5, 4 và 6, 5 và 6, 5 và 7, 6 và 7. Hình dư i ñây bi u di n ñ th tương ng. Vi c l p l ch thi chính là vi c tô màu ñ th này. Vì s màu c a ñ th này là 4 nên c n có 4 ñ t thi. ð 1 Nâu 7 2 Xanh ð 6 3 Vàng Vàng 5 4 Nâu 2) Phân chia t n s : Các kênh truy n hình t s 1 t i s 12 ñư c phân chia cho các ñài truy n hình sao cho không có ñài phát nào cách nhau không quá 240 km l i dùng cùng m t kênh. Có th chia kênh truy n hình như th nào b ng mô hình tô màu ñ th . Ta xây d ng ñ th b ng cách coi m i ñài phát là m t ñ nh. Hai ñ nh ñư c n i v i nhau b ng m t c nh n u chúng cách nhau không quá 240 km. Vi c phân chia kênh tương ng v i vi c tô màu ñ th , trong ñó m i màu bi u th m t kênh. 3) Các thanh ghi ch s : Trong các b d ch hi u qu cao vi c th c hi n các vòng l p ñư c tăng t c khi các bi n dùng thư ng xuyên ñư c lưu t m th i trong các thanh ghi ch s c a b x lý trung tâm (CPU) mà không ph i trong b nh thông thư ng. V i m t vòng l p cho trư c c n bao nhiêu thanh ghi ch s ? Bài toán này có th gi i b ng mô hình tô màu ñ th . ð xây d ng mô hình ta coi m i ñ nh c a ñ th là m t bi n trong vòng l p. Giũa hai ñ nh có m t c nh n u các bi n bi u th b ng các ñ nh này ph i ñư c lưu trong các thanh ghi ch s t i cùng th i ñi m khi th c hi n vòng l p. Như v y s màu c a ñ th chính là s thanh ghi c n có vì nh ng thanh ghi khác nhau ñư c phân cho các bi n khi các ñ nh bi u th các bi n này là li n k trong ñ th . 111
  9. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p BÀI T P CHƯƠNG VI: 1. Cho G là m t ñơn ñ th ph ng liên thông có 10 m t, t t c các ñ nh ñ u có b c 4. Tìm s ñ nh c a ñ th G. 2. Cho G là m t ñơn ñ th ph ng liên thông có 9 ñ nh, b c các ñ nh là 2, 2, 2, 3, 3, 3, 4, 4, 5. Tìm s c nh và s m t c a G. 3. Tìm s ñ nh, s c nh và ñai c a: a) Kn; b) Km,n. 4. Ch ng minh r ng: a) Kn là ph ng khi và ch khi n ≤ 4. b) Km,n là ph ng khi và ch khi m ≤ 2 hay n ≤ 2. 5. ð th nào trong các ñ th không ph ng sau ñây có tính ch t: B m t ñ nh b t kỳ và các c nh liên thu c c a nó t o ra m t ñ th ph ng. a) K5; b) K6; c) K3,3. 6. Cho G là m t ñơn ñ th ph ng liên thông có n ñ nh và m c nh, trong ñó n ≥ 3. Ch ng minh r ng: m ≤ 3n − 6. 7. Trong các ñ th hình dư i ñây, ñ th nào là ph ng, ñ th nào không ph ng? N u ñ th là ph ng thì có th k thêm ít nh t là bao nhiêu c nh ñ ñư c ñ th không ph ng? a f b h b a c g c b f g f g d f e d e c d e G1 G2 G3 8. Ch ng minh r ng ñ th Peterson (ñ th trong Bài t p 8, Chương IV) là ñ th không ph ng. 9. Cho G là m t ñ th ph ng liên thông có n ñ nh, m c nh và ñai là g, v i g ≥ 3. Ch ng minh r ng: g m≤ (n − 2). g−2 10. ða di n l i có d m t (d ≥ 5), mà t m i ñ nh có ñúng 3 c nh. Hai ngư i chơi trò chơi như sau: m i ngư i l n lư t tô ñ m t m t trong các m t còn l i. Ngư i th ng là 112
  10. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ngư i tô ñư c 3 m t có chung m t ñ nh. Ch ng minh r ng t n t i cách chơi mà ngư i ñư c tô trư c luôn luôn th ng. 11. Ch ng minh r ng: a) M t ñ th ph ng có th tô ñúng các ñ nh b ng hai màu khi và ch khi ñó là ñ th phân ñôi. b) M t ñ th ph ng có th tô ñúng các mi n b ng hai màu khi và ch khi ñó là ñ th Euler. 12. Tìm s c s c a các ñ th cho trong Bài t p 7. 13. Tìm s c s c a các ñ th Kn, Km,n, Cn, và Wn. 14. Khoa Toán có 6 h i ñ ng h p m i tháng m t l n. C n có bao nhiêu th i ñi m h p khác nhau ñ ñ m b o r ng không ai b x p l ch h p hai h i ñ ng cùng m t lúc, n u các h i ñ ng là: H1 = {H, L, P}, H2 = {L, M, T}, H3 = {H, T, P}. 15. M t vư n bách thú mu n xây d ng chu ng t nhiên ñ trưng bày các con thú. Không may, m t s lo i thú s ăn th t các con thú khác n u có cơ h i. Có th dùng mô hình ñ th và tô màu ñ th như th nào ñ xác ñ nh s chu ng khác nhau c n có và cách nh t các con thú vào các chu ng thú t nhiên này? 16. Ch ng minh r ng m t ñơn ñ th ph ng có 8 ñ nh và 13 c nh không th ñư c tô ñúng b ng hai màu. 17. Ch ng minh r ng n u G là m t ñơn ñ th ph ng có ít hơn 12 ñ nh thì t n t i trong G m t ñ nh có b c ≤ 4. T ñó hãy suy ra r ng ñ th G có th tô ñúng b ng 4 màu. 113
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