Tài liệu Lí thuyết đồ thị và bài toán 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 ERDÖS - 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ục lục 1 Khái niệm đồ thị 1.1 Định nghĩa đồ thị . . . . . . . . . . . . 1.2 Đường đi và chu trình . . . . . . . . . . 1.3 Chu số và sắc số của đồ thị . . . . . . . 1.3.1 Chu số của đồ thị . . . . . . . . 1.3.2 Sắc số của đồ thị . . . . . . . . 1.4 Chu trình Euler và chu trình Hamilton . 1.4.1 Chu trình Euler . . . . . . . . . 1.4.2 Chu trình Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 6 9 9 10 17 17 20 Lý thuyết đồ thị, Định lý Ramsey và Giả thuyết Erdös Szekeres 2.1 Định lý Ramsey dưới ngôn ngữ đồ thị . . . . . . . . . . . . 2.2 Chứng minh định lí Ramsey nhờ ngôn ngữ đồ thị . . . . . . 2.3 Định lí Ramsey và chứng minh Giả thuyết Erdös - Szekeres 2.3.1 Lịch sử bài toán Erdös-Szekeres . . . . . . . . . . . 2.3.2 Định lí Ramsey dưới ngôn ngữ tập hợp . . . . . . . 2.3.3 Ứng dụng của Định lí Ramsey . . . . . . . . . . . . 2.3.4 Đánh giá cận trên và cận dưới của ES(n) . . . . . . 25 25 28 34 34 37 39 40 3 Mối quan hệ giữa lý thuyết đồ thị và giả thuyết Erdös Szekeres 3.1 Định lý Erdös -Szekeres mở rộng cho các điểm ở vị trí lồi . . 3.2 Giả thuyết "Big Line or Big Clique" . . . . . . . . . . . . . 3.2.1 Tổng quát hóa của Định lý Erdös - Szekeres . . . . . 3.2.2 Một số khẳng định. . . . . . . . . . . . . . . . . . . 43 45 46 50 55 2 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, Erdös 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], Erdös và Szekeres cũng đã đưa ra giả thuyết: ES(n) = 2n−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 Erdös -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í Erdös -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í Erdös -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 Erdös -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 Erdös -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 Erdös -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í Erdös 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 6= ∅, 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: hx1 , 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ị G0 = (V 0 , E 0 ) được gọi là đồ thị con của đồ thị G nếu: V 0 ⊆ V ; E 0 = E ∩ (V 0 × V 0 ). 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 n2 thì đồ thị G liên thông. 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 1.3.1 Chu số và sắc số của đồ thị 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) 6= 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 G0 ⊆ G thì χ (G0 ) ≤ χ (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 α0 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. (König) 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ị G0 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) ≤ χ (G0 ) ≤ χ (G) + 1. Giả sử bâc cao nhất của các đỉnh trong G0 là d0 . Hiển nhiên d ≤ d0 . Nếu χ (G) ≤ d thì χ (G) ≤ d + 1 ≤ d0 + 1. Nếu χ (G) = d+1 thì: Trường hợp: d ≤ d0 ta có : χ (G) ≤ d+1+1 ≤ d0 +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: χ (G0 ) ≤ χ (G) ≤ d + 1 = d0 + 1. 0 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 āx̄ và c̄x̄ sẽ tạo thành một chu trình, 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 1.4.1 Chu trình Euler và chu trình Hamilton 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ị G0 từ G bằng cách thêm vào cạnh a, b. G0 sẽ không có đỉnh bậc lẻ nên theo định lí 1.18 G0 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