Luận văn Thạc sĩ toán học: Lý thuyết đồ thị và giả thuyết Erdos - Szekeres

Chia sẻ: Tran Van Lam | Ngày: | Loại File: PDF | Số trang:62

Thêm vào BST

Báo xấu

110
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Năm 1935, Klein, ERDOS và SZEKERES đã đặt câu hỏi: Cho một số tự nhiên n bất kì, tồn tại hay không một số tự nhiên ES(n) sao cho từ ES(n) điểm trên mặt phẳng, trong đó không có ba điểm nào thẳng hàng, có thể trích ra n điểm là đỉnh của một đa giác lồi ?

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ toán học: Lý thuyết đồ thị và giả thuyết Erdos - Szekeres

Đ I H C THÁI NGUYÊN TRƯ NG Đ I H C KHOA H C H HUY N TRANG LÍ THUY T Đ TH VÀ GI ¨ THUY T ERDOS - SZEKERES LU N VĂN TH C S TOÁN H C Chuyên ngành : TOÁN NG D NG Mã s : 60 46 36 Giáo viên hư ng d n: PGS. TS. T DUY PHƯ NG THÁI NGUYÊN, 2011 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
M cl c 1 Khái ni m đ th 5 1.1 Đ nh nghĩa đ th . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Đư ng đi và chu trình . . . . . . . . . . . . . . . . . . . . . 6 1.3 Chu s và s c s c a đ th . . . . . . . . . . . . . . . . . . 9 1.3.1 Chu s c a đ th . . . . . . . . . . . . . . . . . . . 9 1.3.2 S c s c a đ th . . . . . . . . . . . . . . . . . . . 10 1.4 Chu trình Euler và chu trình Hamilton . . . . . . . . . . . . 17 1.4.1 Chu trình Euler . . . . . . . . . . . . . . . . . . . . 17 1.4.2 Chu trình Hamilton . . . . . . . . . . . . . . . . . . 20 2 Lý thuy t đ th , Đ nh lý Ramsey và Gi thuy t Erdos - ¨ Szekeres 25 2.1 Đ nh lý Ramsey dư i ngôn ng đ th . . . . . . . . . . . . 25 2.2 Ch ng minh đ nh lí Ramsey nh ngôn ng đ th . . . . . . 28 2.3 Đ nh lí Ramsey và ch ng minh Gi thuy t Erdos - Szekeres ¨ 34 2.3.1 L ch s bài toán Erd¨s-Szekeres . . . . . . . . . . . o 34 2.3.2 Đ nh lí Ramsey dư i ngôn ng t p h p . . . . . . . 37 2.3.3 ng d ng c a Đ nh lí Ramsey . . . . . . . . . . . . 39 2.3.4 Đánh giá c n trên và c n dư i c a ES(n) . . . . . . 40 3 M i quan h gi a lý thuy t đ th và gi thuy t Erdos - ¨ Szekeres 43 3.1 Đ nh lý Erdos -Szekeres m r ng cho các đi m v trí l i . . ¨ 45 3.2 Gi thuy t "Big Line or Big Clique" . . . . . . . . . . . . . 46 3.2.1 T ng quát hóa c a Đ nh lý Erdos - Szekeres . . . . . ¨ 50 3.2.2 M t s kh ng đ nh. . . . . . . . . . . . . . . . . . . 55 2 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
L i nói đ u Năm 1935, Klein, Erdos và Szekeres đã đ t câu h i: Cho m t s t nhiên ¨ n b t kì, t n t i hay không m t s t nhiên ES(n) sao cho t ES(n) đi m trên m t ph ng, trong đó không có ba đi m nào th ng hàng, có th trích ra n đi m là đ nh c a m t đa giác l i? Đ ch ng minh s t n t i c a s ES(n), Szekeres (1935, xem [9]) đã phát hi n l i Đ nh lí Ramsey (do nhà toán h c tr ngư i Anh Ramsey phát bi u và ch ng minh năm 1930, xem [19]). Trong [9], Erdos và Szekeres cũng đã đưa ra gi thuy t: ¨ n−2 ES(n) = 2 + 1. V i s c g ng c a hàng trăm nhà toán h c, sau 75 năm, gi thuy t Erdos ¨ -Szekeres m i ch đư c ch ng minh cho trư ng h p n = 3, 4, 5 và g n đây (2006, xem [21]) cho trư ng h p n = 6 nh máy tính. C hai Đ nh lí Ramsey và Đ nh lí Erdos -Szekeres đ u có chung m t b n ¨ ch t tri t h c: Khi s ph n t (s đi m) c a m t t p h p đ nhi u, có th ch n đư c t p con có c u trúc (đa giác l i). Đ nh lí Ramsey có th phát bi u trên ngôn ng đ th . Trư ng h p đơn gi n nh t c a Đ nh lí Ramsey là bài toán sau: Cho đ th đ y đ v i sáu đ nh và các c nh đư c tô b i hai màu đ và xanh. Ch ng minh r ng có ít nh t ba c nh đ ng màu (ho c đ ho c xanh). Bài toán này cũng có th phát bi u dư i ngôn ng trò chơi như sau: Có sáu ngư i ng i quanh bàn ti c, hãy ch ng t r ng có ít nh t ho c ba ngư i đôi m t quen nhau ho c đôi m t không quen nhau. Do b n ch t tri t h c sâu s c, Đ nh lí Ramsey đã tr thành hòn đá t ng c a Lí thuy t Ramsey và có r t nhi u ng d ng trong toán h c và th c t (lí thuy t s , hình h c t h p, lí thuy t đ th , lí thuy t m ng, toán trò chơi, trong công ngh thông tin,...). M t đi u thú v là, g n đây (2011), các tác gi c a [10] đã s d ng Đ nh lí Erdos -Szekeres suy r ng đ tr l i m t câu h i m c a gi thuy t "big ¨ 3 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
line and big clique" trong lí thuy t đ th (xem [10]). Như v y, lí thuy t đ th , Đ nh lí Ramsey và gi thuy t Erdos -Szekeres có ¨ m i quan h khá ch t ch và thú v . Cơ b n d a trên bài báo [10], lu n văn Lí thuy t Đ th và Gi thuy t Erdos -Szekeres c g ng phác th o m i quan h thú v gi a ba đ i tư ng ¨ toán h c trên. Lu n văn g m 3 chương: Chương 1 : Trình bày các khái ni m cơ b n lí thuy t đ th . Các đ nh nghĩa và đ nh lí c a Chương này s đư c s d ng trong hai chương sau. Chương 2 : Trình bày gi thuy t Erdos -Szekeres các ch ng minh Đ nh lí ¨ Ramsey. Chương 3 :D a trên tài li u [10], trình bày ch ng minh Đ nh lí Erdos - ¨ Szekeres suy r ng và áp d ng đ tr l i m t câu h i m c a gi thuy t "big line or big clique" trong lí thuy t đ th . Lu n văn đư c hoàn thành dư i s hư ng d n c a PGS TS T Duy Phư ng. Tác gi xin bày t lòng kính tr ng và bi t ơn th y hư ng d n đã t n tình giúp đ , gi ng gi i trong su t quá trình tác gi h c t p và nghiên c u đ tài. Tác gi xin trân tr ng c m ơn các th y cô giáo trư ng Đ i h c Khoa h c thuôc Đ i h c Thái Nguyên và các th y cô giáo Vi n Toán h c Vi t Nam đã t n tâm gi ng d y và giúp đ tác gi hoàn thành khóa h c. Đ ng th i tác gi xin chân thành c m ơn các b n bè đ ng nghi p và gia đình đã đ ng viên, giúp đ và t o đi u ki n v m i m t trong quá trình h c t p. Song, do còn h n ch v th i gian, cũng như trình đ hi u bi t nên lu n văn không tránh kh i nh ng thi u sót, tác gi r t mong nh n đư c s ch b o c a các th y cô giáo và nh ng góp ý c a b n đ c đ lu n văn đư c hoàn thi n hơn. Thái Nguyên, ngày 30 tháng 10 năm 2011. Tác gi H Huy n Trang 4 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Chương 1 Khái ni m đ th Chương này trình bày nh ng khái ni m cơ b n nh t c a lí thuy t đ th d a theo [1] và [2] nh m s d ng trong các chương 2 và 3. 1.1 Đ nh nghĩa đ th Chúng ta có th coi b n đ các tuy n đư ng giao thông c a m t thành ph , sơ đ t ch c m t cơ quan, sơ đ kh i tính toán c a m t thu t toán, sơ đ m t m ng máy tính ... là nh ng ví d c th v đ th . Đ nh nghĩa 1.1.1. Đ th G = (V, E) là m t b g m hai t p h p V và E , trong đó: 1. V = ∅, các ph n t c a V g i là các đ nh (vertices). 2. E ⊆ V × V là t p h p các c p không s p th t c a các đ nh đư c g i là các c nh (edges). Ví d 1.1 Đ th G cho b i hình v trên v i t p các đ nh V = {a, b, c, d, e} và t p các c nh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}. N u (a, b) là m t c nh c a đ th thì ta nói r ng đ nh b k v i đ nh a và c hai đ nh a và b k v i c nh (a, b). 5 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
C p đ nh (x, y) ∈ E không s p th t đư c g i là c nh vô hư ng, còn n u có s p th t đư c g i là c nh có hư ng. Vì th , ta thư ng phân các đ th thành hai l p: Đ th vô hư ng và đ th có hư ng. Đ nh nghĩa 1.1.2. Đ th ch ch a các c nh vô hư ng đư c g i là đ th vô hư ng, còn n u đ th ch ch a các c nh có hư ng đư c g i là đ th có hư ng. Đ nh nghĩa 1.1.3. Đ th G = (V, E) đư c g i là đ i x ng n u: ∀x, y ∈ V : (x, y) ∈ E ⇔ (y, x) ∈ E . Nh n xét:Các đ th vô hư ng là đ i x ng. Đ nh nghĩa 1.1.4. Đ th G = (V, E) mà m i c p đ nh đư c n i v i nhau b i không quá m t c nh đư c g i là đơn đ th (thư ng g i t t là đ th ). Còn n u nh ng c p đ nh đư c n i v i nhau nhi u hơn m t c nh thì đư c g i là đa đ th . 1.2 Đư ng đi và chu trình Gi s G = (V, E) là m t đ th . Đ nh nghĩa 1.2.1. Đư ng đi trong đ th là m t dãy các đ nh: x1 , x2 , ..., xi , xi+1 , ..., sao cho m i đ nh trong dãy (không k đ nh đ u tiên) k v i đ nh trư c nó b ng m t c nh nào đó, nghĩa là: ∀ i = 2, 3, ..., k − 1, k : (xi−1 , xi ) ∈ E. Ta nói r ng đư ng đi này đi t đ nh đ u x1 đ n đ nh cu i xk . S c nh c a đư ng đi đư c g i là đ dài c a đư ng đi đó. Đư ng đi đơn là đư ng đi mà các đ nh trên nó khác nhau t ng đôi. Đ nh nghĩa 1.2.2. Chu trình là m t đư ng đi khép kín (t c là đ nh cu i c a đư ng trùng v i đ nh đ u c a đư ng đi). Ta thư ng kí hi u chu trình là: [x1 , x2 , ..., xi , xi+1 , ..., xk−1 , xk ] 6 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
trong đó x1 = xk . Đ cho g n, ta kí hi u chu trình là [x1 , x2 , ..., xi , xi+1 , ..., xk−1 ] . Khi nói đ n m t chu trình, nhi u khi ta cũng không c n xác đ nh đi m đ u và đi m cu i c a nó. Chu trình đư c g i là chu trình đơn n u các đ nh trên nó khác nhau t ng đôi. Trong m t đ th , đ nh nút là đ nh k v i chính nó. Đ nh cô l p là đ nh mà không có các đ nh khác k v i nó. T p m - đ c l p là m t đ th c a m - đ nh cô l p. Đ nh nghĩa 1.2.3. i) Đ th G = (V , E ) đư c g i là đ th con c a đ th G n u: V ⊆ V ; E = E ∩ (V × V ). ii) Đ th G” = (V, E”) v i E” ⊆ E đư c g i là đ th riêng c a đ th G. Ví d 1.2 Hình 1.2 Đ th th hai là đ th con c a đ th đ u. Đ nh nghĩa 1.2.4. i) Hai đ nh c a đ th G đư c g i là liên thông n u trên đ th này có m t đư ng đi n i chúng v i nhau. ii) Đ th G đươc g i là liên thông n u m i c p đ nh c a đ th đ u liên thông v i nhau. Quan h liên thông trên t p đ nh là m t quan h tương đương. Nó t o lên m t phân ho ch trên t p các đ nh. M i l p tương đương c a quan h này đươc g i là m t m ng liên thông (hay thành ph n liên thông). 7 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Kí hi u: p là s m ng liên thông c a m t đ th . M t đ th G đư c g i là p− liên thông n u như G liên thông và v n còn là đ th liên thông n u như ta b đi ít hơn p đ nh tùy ý cùng v i các c nh k v i các đ nh này. Đ nh nghĩa 1.2.5. B c c a m t đ nh là s c nh k v i đ nh đó và thư ng kí hi u d(a) là b c c a đ nh a trong đ th G. B c c a đ th là s các đ nh, thư ng đư c kí hi u là n. Đ nh lý 1.2.1. T ng t t c các b c c a đ nh trong m t đ th b ng hai l n s c nh c a đ th đó. Ch ng minh. Ta tính b c c a đ nh. M i đ nh thu c m t c nh nào đó thì b c c a nó tăng thêm 1. Mà m i c nh thì có hai đ nh. Do đó t ng t t c các b c c a đ nh là g p đôi s c nh c a đ th . H qu 1.2.1. S đ nh có b c l trong m t đ th ph i là m t s ch n. Đ nh lý 1.2.2. Đ th G có n đ nh. N u b c c a m i đ nh trong G không nh hơn n thì đ th G liên thông. 2 Ch ng minh Ta ch ng minh b ng ph n ch ng. Gi s đ th G liên thông. Khi đó có ít nh t hai đ nh a và b n m trong hai m ng liên thông khác nhau. V y thì, n ≤ d(a) + d(b) ≤ n − 2. Suy ra đi u mâu thu n. M t s tính ch t c a b c c a m t đ nh Đ nh có b c 0 đư c g i là đ nh cô l p (isolated vertex). Đ nh có b c 1 đư c g i là đ nh treo, c nh t i đ nh treo g i là c nh treo. Đ th mà m i đ nh đ u là đ nh cô l p g i là đ th r ng. Đ th đư c g i là đ th ph ng n u nó có th bi u di n đư c trên m t ph ng sao cho không có hai đư ng bi u di n nào c t nhau. Đ th đư c g i là đ th đ y đ n u hai đ nh b t kì đ u có c nh n i, t c là m i đ nh c a đ th đ u k v i m i đ nh khác. Ta kí hi u Kn là đ th vô hư ng đ y đ n đ nh. Trong đ th Kn , m i đ nh đ u có b c là n − 1 và đ th là liên thông. Hai đ nh b t kì đư c n i v i nhau b ng m t đư ng đi ng n nh t có đ dài b ng 1, đó chính là c nh n i hai đ nh y. Ví d 1.4: Ví d v đ th Kn . 8 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
1.3 Chu s và s c s c a đ th 1.3.1 Chu s c a đ th Đ nh nghĩa 1.3.1. Cho đ th G = (V, E) có n đ nh, m c nh và p thành ph n liên thông. Đ i lư ng c = m − n + p đư c g i là chu s c a đ th G. Ví d 1.5 Xét đ th sau: Hình 1.5 Đ th đ nh hư ng không liên thông Đ th trên có n = 7, m = 8, p = 2.V y chu s c = 8 − 7 + 2 = 3 Đ nh lý 1.3.1. N u thêm m t c nh m i vào đ th G thì chu s tăng thêm 1 ho c không thay đ i. Ch ng minh Gi s thêm c nh m i (a, b) vào đ th G. Khi đó m tăng thêm 1. i) N u hai đ nh a, b thu c cùng m t m ng liên thông thì n, p không đ i, do v y chu s tăng thêm 1. ii) N u hai đ nh a, b thu c hai m ng liên thông khác nhau trong G thì p gi m đi 1, do v y chu s không đ i. 9 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
H qu 1.3.1. Chu s c a đ th là m t s nguyên không âm. Ch ng minh Th t v y, đ th G đư c xây d ng t đ th G0 g m n đ nh và không có c nh nào c . Sau đó l n lư t thêm các c nh vào đ th G0 đ đư c đ th G. Chu s c a G0 là c = 0 − n + n = 0. Quá trình thêm c nh không làm gi m chu s . V y chu s c a G l n hơn ho c b ng chu s c a G0 = 0. 1.3.2 S c s c a đ th Khái ni m s c s liên quan đ n bài toán tô màu đ th như sau: Hãy tô màu các đ nh c a đ th đã cho, sao cho hai đ nh k nhau ph i đư c tô b ng hai màu khác nhau. Ta nói r ng, đ th G tô đư c b ng k màu n u t n t i hàm m : V → {0, 1, 2, ..., k − 1} sao cho, n u hai đ nh x và y k nhau thì m(x) = m(y). D th y r ng, đ th G tô màu đư c khi và ch khi nó không có đ nh nút. Đ nh nghĩa 1.3.2. S c s c a m t đ th chính là s màu ít nh t dùng đ tô màu các đ nh c a đ th đó. Ta kí hi u χ (G) là s c s c a đ th G. Hi n nhiên χ (G) ≤ n. Nghĩa là s c s (s màu) không vư t quá s đ nh c a đ th . T p B ⊆ V đư c g i là t p n đ nh trong c a đ th G n u: ∀x ∈ B : B ∩ F (x) = ∅ Nh n xét M i cách tô màu m cho đ th G ng v i m t cách phân ho ch t p đ nh V thành các t p n đ nh trong không giao nhau, m i t p ng v i m t màu. Ngươc l i, m i cách phân ho ch t p đ nh V thành các t p n đ nh trong không giao nhau s cho ta m t cách tô màu. Ví d 1.6 Tìm s c s c a đ th G sau: 10 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Nh n xét r ng 4 đ nh A, B, C, D đôi m t k nhau nên ph i đư c tô b ng 4 màu khác nhau.V y χ (G) ≥ 4. Hơn n a có th dùng 4 màu đánh s 1, 2, 3, 4 đ tô màu G như sau: V y χ (G) = 4. Nh n xét M i cách tô màu m cho đ th G ng v i m t cách phân ho ch t p đ nh V thành các t p n đ nh trong không giao nhau, m i t p ng v i m t màu. Ngươc l i, M i cách phân ho ch t p đ nh V thành các t p n đ nh trong không giao nhau s cho ta m t cách tô màu. Đ nh nghĩa 1.3.3. Hai đ th G1 = (V1 , E1 ) và G2 = (V2 , E2 ) đư c g i là đ ng hình n u t n t i m t song ánh lên các t p đ nh S : V1 → V2 b o toàn các c nh sao cho: ∀x, y ∈ V1 , (x, y) ∈ E1 ⇔ (S(x), S(y)) ∈ E2 . Ví d : Hai đ th dư i đây là đ ng hình v i song ánh: S(ai ) = xi , i = 1, 2, 3, 4. 11 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.6 Hai đ th đ ng hình. Đ nh lý 1.3.2. N u G ch a m t đ th con đ ng hình v i Km thì χ (G) ≥ m. Ví d 1.7 Hãy tô màu đ th sau: Hình 1.7 Tô màu các đ nh c a đ th . Đ th trên có s c s b ng 3. Nh n xét Có hai đi u ki n lưu ý khi tìm s c s c a đ th G. N u G ⊆ G thì χ (G ) ≤ χ (G) . N u dùng k màu đ tô màu G thì không c n quan tâm đ n nh ng đ nh có b c nh hơn k. Đ nh lý 1.3.3. Đ th đ y đ n đ nh Kn có s c s b ng n. Đ nh lý 1.3.4. M i chu trình có đ dài l có s c s b ng 3. Ch ng minh Dùng quy n p. Gi s chu trình có đ dài là 2n + 1. 12 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Ta ch ng minh quy n p theo n. Trư ng h p n = 1. Hi n nhiên đúng vì chu trình g m 3 đ nh, mà hai c nh b t kì đ u k v i nhau. V y, ta ph i dùng đúng ba màu đ tô các đ nh. Gi s đã có chu trình có đ dài là 2n + 1 và có s c s b ng 3. Ta xây d ng chu trình có đ dài là 2(n + 1) + 1. Gi s α là m t chu trình có đ dài là 2(n+1)+1 = 2n+3 v i dãy các đ nh là: [x1 , x2 , ..., xi , xi+1 , ..., x2n+1 , x2n+3 ]. N i x1 v i x2n+1 ta đư c m t chu trình có đ dài 2n + 1. Theo gi thi t quy n p, chu trình α có s c s b ng 3. L y màu c a x1 tô cho x2n+2 , còn màu c a x2n+1 tô cho x2n+3 . Chu trình α đã đư c tô màu mà không ph i thêm màu m i. V y, chu trình α có s c s b ng 3. Đ nh lý 1.3.5. (Konig) Gi s đ th G có ít nh t m t c nh. Đ th G là ¨ hai s c (có s c s là 2) khi và ch khi G không có chu trình đơn vô hư ng đ dài l . Ch ng minh: (⇒) Hi n nhiên. Gi s G là đ th hai s c. Theo đ nh lý 1.3.4 thì G không th có chu trình đơn vô hư ng đ dài l . (⇐) Gi s G không có chu trình đơn vô hư ng đ dài l . Ta s ch ng minh r ng ta có th tô màu các đ nh c a đ th G b ng hai màu. Không m t tính t ng quát, ta có th gi s G liên thông. Ch n m t đ nh v0 ∈ G. Ta tô màu các đ nh c a G b ng hai màu đánh s 0 và 1 theo cách sau: V i m i đ nh x có m t đư ng trong G n i v0 v i x, n u đư ng này có đ dài ch n thì tô màu 0 cho x, n u đư ng này có đ dài l thì tô màu 1 cho x. Đ ch ng minh r ng cách tô màu này hoàn toàn xác đ nh (well - defined), ch c n ch ng minh v i m i đ nh x không th có hai đư ng n i v0 v i x mà có tính ch n l khác nhau. Th t v y, n u có hai đư ng mang tính ch n l khác nhau cùng n i v0 v i x thì d th y r ng G ph i ch a ít nh t m t chu trình l . Vô lí. H qu 1.3.2. T t c các chu trình đ dài ch n đ u có s c s là 2. Đ nh lý 1.3.6. (Đ nh lí Vizing) N u b c l n nh t c a các đ nh trong đ th G là r thì s c s c a đ th G ≤ d + 1. Ch ng minh Dùng quy n p theo s đ nh n. Trư ng h p n = 1: B c c a đ nh b ng 0 và s c s b ng 1. 13 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Trư ng h p n = 2: B c c a đ nh b ng 0 thì s c s b ng 1, còn b c c a các đ nh b c 1 thì có s c s b ng 2. Gi s trư ng h p n đúng. Ta ch ng minh nó cũng đúng cho trư ng h p n + 1. Gi s đ th G có n đ nh, các đ nh có b c cao nh t là r. Theo gi thi t quy n p: χ (G) ≤ d + 1. Đ th G có n + 1 đ nh đư c xem là đ th G có n đ nh và thêm m t đ nh m i a và m t s c nh k nó. Khi đó: χ (G) ≤ χ (G ) ≤ χ (G) + 1. Gi s bâc cao nh t c a các đ nh trong G là d . Hi n nhiên d ≤ d . N u χ (G) ≤ d thì χ (G) ≤ d + 1 ≤ d + 1. N u χ (G) = d+1 thì: Trư ng h p: d ≤ d ta có : χ (G) ≤ d+1+1 ≤ d +1. Hình 1.7 Cách ch n màu cho đ nh m i. Trư ng h p d = d thì đ nh m i a đư c n i v i không quá r đ nh. Do v y, ch c n gi nguyên cách tô màu c a G thì các đ nh k v i a đư c tô không quá r màu và v n còn th a m t màu dành cho đ nh a. Suy ra: χ (G ) ≤ χ (G) ≤ d + 1 = d + 1. H qu 1.3.3. (Đ nh lí Brook) N u G là m t đ th liên thông v i b c l n nh t d, thì ta có χ (G) ≤ d(G) n u như G không ph i là đ th đ y đ và không ph i là chu trình l c nh. Trong m t cách tô màu đ nh c a đ th G cho trư c, m t đ nh a c a G đư c g i là đư c tô màu n đinh n u như không có láng gi ng nào c a a đư c tô màu c a a. M t cách tô màu các đ nh c a đ th G đư c g i là m t cách tô màu n đ nh n u như đ nh nào c a đ th G cũng đư c tô màu n đ nh, nghĩa là không có hai đ nh k nhau nào c a đ th G đư c tô màu gi ng nhau c . Ví d 1.8 Tìm s c s c a đ th Petersen. 14 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.8 Tô màu đ th Petersen. Trư c h t ta th y có th dùng 4 màu đ tô n đ nh 10 đ nh c a đ th Petersen b ng m t cách tùy ý t đ nh 1 đ n đ nh 10 như sau. Khi tô m t đ nh nào đó b ng m t màu nào đó, ta tô ti p m t đ nh x k nó b i m t màu khác t t c các màu láng gi ng c a nó. Vi c tô màu này luôn làm đư c b i vì ta có 4 màu đ l a ch n mà s láng gi ng c a đ nh x đúng b ng 3 (minh h a Hình 1.8a). Nhưng cũng có th tô màu các đ nh c a đ th Petersen b i 3 màu. Cách tô màu như v y đư c bi u di n Hình 1.8b. Ngoài ra d th y r ng không th tô màu các đ nh c a đ th Petersen b i 2 màu, vì đ th có m t chu trình 5 c nh. Trên chu trình này, n u các đ nh c nh nhau không cùng màu thì s đ nh c a đ th ph i là s ch n, là đi u vô lí. V y, χ (G) = 3. Đ nh lý 1.3.7. Đ nh lý năm màu (Kempe - Heawood) M i đ th ph ng (không có đ nh nút) đ u có s c s nh hơn b ng 5. Ch ng minh Xét đ th G có n đ nh. Dùng phép ch ng minh quy n p trên n. Trư ng h p n = 1. Khi đó, đ th có m t đ nh (hi n nhiên đúng). Gi s m i đ th ph ng có n đ nh (n ≥ 1) đ u có th tô b ng năm màu. Coi m t đ th ph ng có n + 1 đ nh. Có th gi s G là đơn đ th . Vì G ph ng nên G có m t đ nh x có b c nh hơn b ng 5. Lo i b đ nh x này kh i G, ta nh n đư c m t đ th ph ng m i có n đ nh. Tô màu cho đ th m i b ng 5 màu, do gi thi t quy n p nên đi u này th c hi n đư c. Bây gi ta đưa đ nh x vào l i đ th . N u các đ nh k v i x đư c tô b ng ít hơn 5 màu thì tô màu x b ng m t trong 5 màu khác màu các đ nh k v i x là xong. Đ th G đã đư c tô b ng 5 màu. Ta ch xét trư ng h p d(x) = 5 và 5 đ nh k v i x đư c tô b ng 5 màu 15 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
như Hình 1.9 Hình 1.9 Năm đ nh k v i năm màu Xét t t c các đư ng trong G b t đ u t a và g m các đ nh ch tô b ng màu 1 và màu 3. Trong các đư ng này, n u không có đư ng nào đi qua đ nh c thì ta có th thay đ i màu các đ nh trên t t c các đư ng nói trên theo cách đ i màu 1 cho 3 và ta có th tô đ nh x màu 1. N u có m t đư ng t a đ n c g m toàn các đ nh ch tô màu 1 và màu 3 thì đư ng này c ng thêm hai c nh ax và ¯x s t o thành m t chu trình, ¯¯ c¯ hai đ nh b, d không th n m cùng bên trong ho c cùng bên ngoài chu trình này đư c. Suy ra, không có đư ng nào t b đ n d g m các đ nh ch tô màu b ng màu 2 và màu 4. V y l i có th thay đ i màu các đ nh trên t t c các đư ng b t đ u t b g m các đ nh ch tô màu 2 và màu 4 theo cách đ i màu 2 thành màu 4 và ngư c l i. Lúc này, b và d có cùng màu 4 và ta có th tô đ nh x b ng màu 2. Bài toán b n màu Trên m t b n đ b t kì, ta n i nó đư c tô màu n u m i mi n c a nó đư c tô mi n xác đ nh sao cho hai mi n k nhau (chung m t ph n biên) ph i đư c tô b ng hai màu khác nhau. V n đ đ t ra là c n dùng t i thi u bao nhiêu màu đ tô m t b n đ b t kì đã đư c đ t ra t kho ng gi a th k 19. Mô hình toán h c c a bài toán như sau. V i m i b n đ M cho trư c, ta xây d ng m t đ th G tương ng: M i mi n c a M ng v i m t đ nh c a G, hai mi n c a M có chung m t ph n biên n u và ch n u hai đ nh tương ng trong G có c nh n i. D th y r ng đ th G nh n đư c theo cách trên là m t đ th ph ng. Như th thì bài toán tô màu M tr thành bài toán tô màu G. Ngay t khi m i xu t hi n bài toán ngư i ta đã đ t gi thuy t r ng l i gi i c a bài toán này là 4. Tuy nhiên, không có m t ch ng minh đúng nào cho gi thi t này đư c đưa ra cho đ n năm 1976, m t nhóm các nhà toán h c g m: Kewneth Appel, 16 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Woltgang Haken, J. Koch đã xây d ng m t l i gi i d a trên các k t qu do máy tính IBM 360 cung c p (m t hàng ngàn gi trên máy tính) đã kh ng đ nh đư c gi thi t b n màu là đúng. Ta có Đ nh lí b n màu (Appel - Haken) như sau. Đ nh lý 1.3.8. M i đ th ph ng không có đ nh nút đ u có s c s không quá 4. D th y r ng, đ th vô hư ng đ y đ Kn (n ≥ 5) có s c s l n hơn 4 nên không ph ng. 1.4 Chu trình Euler và chu trình Hamilton 1.4.1 Chu trình Euler Đ nh nghĩa 1.4.1. Xét m t đ th liên thông G. M t đư ng Euler c a G là m t đư ng có đ nh b t đ u khác đ nh k t thúc và đi qua t t c các c nh c a G. M t chu trình Euler c a G là m t chu trình đi qua t t c các c nh c a G. Đ thì g i là đ th Euler khi nó ch a chu trình Euler và đư c g i là n a Euler khi nó ch a đư ng đi Euler. Nh n xét M t đ th là Euler là n a Euler. Đi u ngư c l i không đúng. Ví d 1.9 Khái ni m chu trình Euler xu t phát t bài toán b y cây c u do Euler gi i quy t vào năm 1737. thành ph Kowigburg có 7 cây c u b c ngang sông Pregel, gi a sông có cù lao Kneiphof t o nên 4 vùng đ t. 17 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Vào năm 1736, Euler (1707 - 1783) nhà toán h c ngư i Th y Sĩ đã ch ng minh không th có cách đi qua c b y cây c u, m i cái đúng m t l n r i quay v đi m xu t phát b ng l p lu n sau. Bi u di n b n mi n đ t A, B, C, D b ng đi m trong m t ph ng, m i c u n i hai mi n đư c bi u di n b ng m t đo n n i hai đi m tương ng, ta s có đ th . Bây gi m t đư ng đi qua 7 cây c u, m i cái đúng m t l n r i quay v đi m xu t phát s có s l n đi đ n A b ng s l n r i kh i A, nghĩa là ph i s d ng đ n m t s ch n cây c u n i v i A. Mà do s c u n i đ n A là 5 (l ) nên không có đư ng đi nào th a mãn đi u ki n c a bài toán. Đ nh lý 1.4.1. (Đ nh lí Euler 1) Cho m t đ th vô hư ng G liên thông và có hơn m t đ nh thì G có chu trình Euler n u và ch n u m i đ nh c a G đ u có b c ch n. Ch ng minh (⇒) M i l n chu trình đi qua m t đ nh thì đ nh đó b t đi hai c nh k . Cu i cùng s c nh k c a m i đ nh b ng 0. Do đó, s c nh k v i m i đ nh ph i là s ch n. (⇐) Xu t phát t m t đ nh a nào đó, ta l p dãy c nh k liên ti p cho đ n khi h t kh năng đi ti p. Khi d ng ph i đ nh a vì b c các đ nh đ u ch n, ta thu đư c chu trình C1 . N u đã vét h t các c nh thì đó là chu trình c n tìm. N u v n còn c nh thì theo tính liên thông c a đ th ph i có m t c nh nào đó chưa đư c ch n và k v i đ nh a1 nào đó c a chu trình đã có. L i xu t phát t a1 và ti p t c quá trình như trên cho đ n khi h t kh năng đí ti p, ta đư c chu trình C2 , ... 18 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.10 Các chu trình k nhau. Khi đã vét h t c nh, ta l p chu trình Euler cho đ th này như sau: T đ nh a đi theo n a trên c a C1 đ n a1 , l i ti p t c t a1 đi theo n a trên c a C2 đ n a2 , ... Khi đã đ n chu trình con cu i cùng thì ta đi ngư c l i theo các n a dư i c a các chu trình con, ... và cu i cùng tr v đ nh a. Ta nh n đư c m t chu trình Euler. Đ nh lý 1.4.2. (Đ nh lí Euler 2) Cho m t đ th vô hư ng G liên thông và có hơn m t đ nh thì G có đư ng đi Euler n u và ch n u có đúng hai đ nh b c l . Ch ng minh (⇒) N u có đư ng đi Euler vô hư ng n i a v i b thì a, b là hai đ nh duy nh t có b c l . (⇐) Gi s a, b là hai đ nh duy nh t có b c l . Xây d ng đ th G t G b ng cách thêm vào c nh a, b. G s không có đ nh b c l nên theo đ nh lí 1.18 G s có chu trình Euler vô hư ng. B c nh (a, b) đi ta có đư ng đi Euler vô hư ng trong đ th G. Đ nh lý 1.4.3. (Đ nh lí Euler 3) Cho m t đ th có hư ng G liên thông và có hơn m t đ nh thì G có chu trình Euler n u và ch n u G cân b ng (s c nh đi vào b ng s c nh đi ra), nghĩa là: ∀x ∈ X : d− (x) = d+ (x) trong đó d− (x) là s c nh đi vào đ nh x và d+ (x) là s c nh đi ra kh i x. Đ nh lý 1.4.4. (Đ nh lí Euler 4) Cho m t đ th có hư ng G liên thông và có hơn m t đ nh thì G có chu trình Euler n u và ch n u G có hai đ nh a, b th a mãn: d− (a) = d+ (a) − 1 và d+ (b) = d− (b) + 1 và m i đ nh còn l i đ u cân b ng. Hơn n a đư ng Euler ph i b t đ u t a và k t thúc b. 19 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Ch ng minh i) Gi s đ th G có đư ng Euler α đi qua t t c các c nh c a đ th . Khi đó. - V i đ nh xu t phát a c a α: Tr c nh đ u tiên c a α đi ra t a, c có m t c nh đi vào a thì ph i có m t c nh đi ra kh i a vì α k t thúc đ nh khác. Do v y, d− (a) = d+ (a) − 1. - V i đ nh k t thúc b c a α: Tr c nh cu i cùng c a α đi t i b, c có m t c nh đi ra kh i b thì ph i có m t c nh đi vào b vì α k t thúc b. Do v y, d+ (b) = d− (b) + 1. - V i các đ nh khác: S c nh đi vào b ng s c nh đi ra nên chúng là cân b ng. ii) Gi s đ th G liên thông và có hai đ nh a, b th a mãn: d− (a) = d+ (a) − 1 và d+ (b) = d− (b) + 1, còn m i đ nh còn l i đ u cân b ng. Ta thêm vào m t c nh m i (b, a). Khi đó, m i đ nh là cân b ng nên theo Đ nh lí Euler 3 thì đ th có chu trình Euler có hư ng. Bây gi b c nh (b, a) kh i chu trình thì ta đư c m t đư ng đi Euler có hư ng. 1.4.2 Chu trình Hamilton Năm 1857, W. R. Hamilton(1805 - 1865), nhà toán h c ngư i Ailen đã đưa ra trò chơi sau đây: Trên m i đ nh trong s hai mươi đ nh c a m t kh i đa di n 12 m t ngũ giác đ u có ghi tên m t thành ph l n c a th gi i. Hãy tìm cách đi b ng các c nh c a kh i này đ đi qua t t c các thành ph , m i thành ph đúng m t l n. Bài toán này d n đ n nh ng khái ni m sau đây. Đ nh nghĩa 1.4.2. Xét m t đ th có hư ng G liên thông và có hơn m t đ nh. M t đư ng Hamilton là đư ng đi qua m i đ nh c a đ th đúng m t l n. Chu trình Hamilton là chu trình đi qua m i đ nh c a đ th đúng m t l n. Đ th G đư c g i là Đ th Hamilton n u nó ch a chu trình Hamilton và g i là đ th n a Hamilton n u nó có đư ng đi Hamilton. Rõ ràng, m t đ th Hamilton là n a Hamilton, nhưng đi u ngư c l i không còn đúng. 20 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn