Tài liệu Bài toán tô màu đồ thị và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ HOÀNG LINH BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ HOÀNG LINH BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. Trần Vũ Thiệu Thái nguyên - 2015 MỞ ĐẦU Đồ thị là một cấu trúc toán học rời rạc, bao gồm hai yếu tố đỉnh và cạnh, và là mô hình toán học cho nhiều vấn đề lý thuyết và thực tiễn đa dạng. Bài toán tô màu cho các đỉnh (hay các cạnh) của một đồ thị là một chủ đề quan trọng và hấp dẫn của lý thuyết đồ thị. Bài toán này có những ứng dụng thiết thực trong kinh tế, kỹ thuật và đời sống. Chẳng hạn, ta thường gặp bài toán tô màu bản đồ, tô màu cho dây dẫn điện. Một số vấn đề không liên quan đến tô màu cũng có thể được xử lý nhờ bài toán tô màu: bố trí kho chứa hóa chất, thiết kế các bảng vi mạch điện tử, sắp xếp lịch hỏi thi, bố trí các trạm truyền tin, xác lập các tuyến xe buýt thành phố, v.v ... Lý thuyết đồ thị ra đời và phát triển gắn liền với tên tuổi của nhiều nhà toán học nổi tiếng: Euler (Thụy sĩ), với bài toán về 7 cầu ở thành phố Königsberg, König và Egeváry (Hungari), với phương pháp Hungari giải bài toán phân việc. Về vấn đề tô màu đồ thị có nhiều kết quả lý thuyết đáng chú ý: Định lý Brooks, Minty về tô màu đỉnh; Định lý König, Vizing, Shannon về tô màu cạnh, định lý 5 màu của Heawood (1890) và Định lý 4 màu của Appel và Haken (1976), đã giải quyết được giả thuyết 4 màu nổi tiếng do Guthrie nêu ra lần đầu năm 1852. "Bài toán tô màu đồ thị và ứng dụng". Luận văn này có mục đích tìm hiểu và trình bày các khái niệm cơ bản về đồ thị và các dạng đồ thị thường gặp, về bài toán tô màu trên đồ thị (tô đỉnh, tô cạnh và tô diện - tô màu bản đồ) và một số ứng dụng của các bài toán này. Trình bày các kết quả lý thuyết, các định lý về tô màu trên các loại đồ thị khác nhau và các thuật toán tô màu đỉnh và cạnh, dựa trên các kết quả lý thuyết đã có. Nội dung luận văn được viết trong hai chương. 1 Chương 1 "Khái niệm cơ bản về đồ thị" nhắc lại các khái niệm cơ bản về đồ thị: đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu trình, đồ thị liên thông, không liên thông, các phép toán trên đồ thị. Miêu tả nhiều dạng đồ thị đặc biệt: rừng và cây, đồ thị hình sao, đồ thị vòng, đồ thị đường, đồ thị bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ thị đều (chính qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng, ... Chương 2 "Bài toán tô màu đồ thị" đề cập tới vấn đề tô màu các đỉnh, cạnh và diện của một đồ thị. Trình bày các kết quả về tô màu đỉnh: định lý Brooks (1941), định lý Minty (1962), các định lý tô màu đồ thị phảng, đặc biệt định lý bốn màu (Appel và Haken, 1976). Về tô màu bản đồ (tô diện của đồ thị phẳng) có các định lý về bản đồ 2 màu, bản đồ lập phương 3 màu và định lý bốn màu cho bản đồ. Về tô màu cạnh của đồ thị: trình bày định lý Vizing (1964) về số màu tối thiểu cần tô, định lý tô cạnh đồ thị đầy đủ, tô cạnh đồ thị hai phần (Định lý König, 1916) và quan hệ với định lý bốn màu. Cuối chương đề cập tới đa thức màu, cho biết có thể tô đỉnh của đò thị bằng k màu được không, nếu được thì có mấy cách tô. Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS - TS Trần Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên, Viện Toán hoc - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên 20 tháng 04 năm 2015 Tác giả Vũ Hoàng Linh 2 Chương 1 KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ Chương này trình bày các kiến thức cơ sở về lý thuyết đồ thị. Mục 1.1 nêu các định nghĩa, khái niệm dùng trong lý thuyết đồ thị và các phép toán trên đồ thị. Mục 1.2 mô tả các dạng đồ thị thường gặp. Trong chương dẫn ra nhiều ví dụ minh họa. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [2], [3], [4] và [5]. 1.1. ĐỊNH NGHĨA VÀ KÝ HIỆU 1.1.1. Khái niệm đồ thị Trong thực tế ta thường gặp các sơ đồ giao thông (Hình 1.1) hay sơ đồ mạch điện (Hình 1.2). Các sơ đồ này được khái quát thành sơ đồ vẽ ở Hình 1.3. Từ đó ta đi tới định nghĩa sau. Hình 1.1. Sơ đồ khu phố Hình 1.2. Sơ đồ mạch điện Hình 1.3. Đồ thị đại diện Đồ thị (graph) là một tập hợp hữu hạn và khác rỗng các điểm, gọi là các đỉnh (vertex) hay nút (node), và một tập hợp các đường (thẳng hay cong) nối liền một số cặp điểm này, gọi là các cạnh (edge) của đồ thị (Số cạnh có thể bằng 0). Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái (a, b, c, ... hay A, B, C, ...) hoặc chữ số (1, 2, 3, ...). Cạnh nối liền đỉnh v với đỉnh w được ký hiệu là (v, w) hay đơn giản là vw (v và w có thể là các chữ số). Một cạnh có dạng (a, a), nối đỉnh a với chính nó, gọi là một khuyên (loop). Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V × V thì để cho gọn, ta viết G = (V, E). Ta cũng dùng ký hiệu V(G) để chỉ tập đỉnh và E(G) để chỉ tập cạnh của đồ thị G. Ký hiệu n = |V(G)| là số đỉnh và m = |E(G)| là số cạnh của đồ thị G. 3 Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi một hình vẽ trên mặt phẳng. Chẳng hạn, Hình 1.3 biểu diễn một đồ thị có 5 đỉnh: P, Q, R, S, T và 8 cạnh (mỗi cạnh là một đoạn thẳng nối hai đỉnh). Chú ý rằng điểm cắt nhau của hai cạnh PS và QT trong hình vẽ không phải là một đỉnh của đồ thị. Đỉnh v gọi là kề (adjacent) đỉnh w nếu có một cạnh của đồ thị nối v với w. Nếu ký hiệu cạnh này là e thì ta viết e = (v, w) và nói cạnh e liên thuộc (incident) v, w hay v, w là hai đầu mút của e. Cạnh e và e' gọi là kề nhau nếu e, e' có chung đỉnh. Hai cạnh e và e' cùng nối một cặp đỉnh gọi là cạnh kép (multiple edge). Đồ thị không có cạnh kép gọi là một đơn đồ thị (simple graph). Trái lại, gọi là một đa đồ thị. Hình 1.4 và 1.5 minh họa cạnh kép và khuyên trong đa đồ thị. Hình 1.4. Cạnh kép và đa đồ thị Hình 1.5. Khuyên trong đa đồ thị Một cạnh của đồ thị gọi là cạnh có hướng (directed edge) nếu có qui định rõ một đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn được gọi là một cung. Một đồ thị gồm toàn các cạnh gọi là đồ thị vô hướng (undirected graph), đồ thị gồm toàn các cung gọi là đồ thị có hướng (digraph). Một đồ thị vừa có cạnh vừa có cung gọi là đồ thị hỗn hợp (mixed graph). Bằng cách thay một cạnh bởi hai cung có hướng ngược chiều nhau, ta có thể qui mọi đồ thị về đồ thị có hướng. Hình 1.6 mô tả một đồ thị có hướng. Hình 1.6. Đồ thị có hướng Hình 1.7. Đồ thị không liên thông 4 Bậc (degree) của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc nó, ký hiệu là (v). Đỉnh có bậc 0 gọi là đỉnh cô lập (isolated vertex), đỉnh có bậc 1 gọi là đỉnh treo (end-vertex), Tương tự, trong đồ thị có hướng ta gọi bậc ra (bậc vào) của đỉnh v là số cung đi khỏi v (số cung đi tới v), ký hiệu tương ứng là + (v) và - (v). Qui ước: khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.7 ta có (P) = (S) = (U) = (V) = 2; (Q) = (R) = 3 và (T) = 4 (có khuyên ở T). Dễ dàng chứng minh các tính chất sau đây về bậc của đỉnh trong đồ thị: a) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnh của đồ thị và số đỉnh có bậc lẻ bao giờ cũng là một số chẵn. b) Trong một đồ thị có hướng, tổng các bậc vào của mọi đỉnh bằng tổng các bậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị. Nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng các cung trong đồ thị. Vì thế, khi bỏ qua hướng trên các cung (đổi cung thành cạnh) ta sẽ nhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho. 1.1.2. Phép toán trên đồ thị Sau đây ta tập trung chủ yếu xét các đồ thị vô hướng và một số phép toán. • Đồ thị con (subgraph) của một đồ thị G là đồ thị nhận được từ G bằng cách bỏ đi một số đỉnh và một số cạnh của nó. Nói chính xác, H = (V(H), E(H)) là một đồ thị con của G nếu V(H) V(G) và E(H) E(G). Ta cũng nói G chứa H. H gọi là đồ thị con cảm sinh (induced subgraph) của G nếu H là một đồ thị con của G và E(H) = {(x, y) ∈ E(G) : x, y ∈ V(H)}. Ở đây H là đồ thị con của G sinh bởi V(H). Vì thế ta còn viết H = G[V(H)]. Đồ thị con H của G gọi là đồ thị con bao trùm nếu V(H) = V(G), tức tập đỉnh của H và của G trùng nhau. • Với v ∈ V(G), ký hiệu G - v là đồ thị con của G cảm sinh bởi V(G) \ {v}, tức đồ thị nhận được từ G bằng cách bỏ đỉnh v và các cạnh liên thuộc v. • Với e ∈ E(G), ta định nghĩa G - e := (V(G), E(G) \ {e}), tức đồ thị nhận được từ G bằng cách xóa cạnh e (không xóa hai đầu mút của e). Ta cũng định nghĩa 5 G \ e là đồ thị nhận được bằng cách co cạnh e thành một điểm duy nhất. Hình 1.8 minh họa các đồ thị G, G - e và G \ e. Hình 1.8. Đồ thị G, cạnh e và các đồ thị G e và G \ e tương ứng 1.1.3. Đồ thị đẳng cấu Hai đồ thị G1 và G2 gọi là đẳng cấu (isomorphic) nếu chúng có số đỉnh và số cạnh như nhau và có phép tương ứng một - một giữa tập đỉnh của G1 và G2 sao cho hai đỉnh được nối với nhau bởi một cạnh trong đồ thị này khi và chỉ khi hai đỉnh tương ứng trong đồ thị kia cũng được nối với nhau bởi một cạnh và ngược lại. Hình 1.9 vẽ các đồ thị đẳng cấu với đồ thị vẽ ở Hình 1.3. Các cạnh của hai đồ thị ở Hình 1.9 chỉ gặp nhau ơ đinh. Các đồ thị đẳng cấu được xem là tương đương (là một). Hình 1.9. Các đồ thị đẳng cấu với đồ thị ở Hình 1.3 1.1.4. Đồ thị liên thông Có thể ghép hai đồ thị để lập lên một đồ thị lớn hơn. Cho G1 = (V(G1), E(G1)), G2 = (V(G2), E(G2)) với V(G1) ∩V(G2) = ∅. Khi đó, hợp (union) G1 ∪ G2 là đồ thị có tập đỉnh là V(G1) ∪ V(G2) và tập cạnh là E(G1) ∪ E(G2) (Hình 1.10). Hình 1.10. Đồ thị G1, G2 và hợp G1 ∪ G2 Hình 1.11. Đồ thị không liên thông Hầu hết các đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông (connected graph) nếu nó không biểu diễn được dưới dạng hợp của hai hay nhiều 6 đồ thị. Trái lại, đồ thị gọi là không liên thông (disconnected graph). Rõ ràng là bất cứ một đồ thị không liên thông G nào cũng biểu diễn được dưới dạng hợp của các đồ thị liên thông, mỗi đồ thị liên thông gọi là một thành phần liên thông của G. Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.11. Hình 1.12. Các kiểu đồ thị liên thông không quá 5 đỉnh 7 Khi cần chứng minh một kết luận nào đó cho các đồ thị nói chung, ta thường chứng minh kết quả tương ứng cho các đồ thị liên thông, sau đó áp dụng kết quả thu được cho từng thành phần liên thông riêng lẻ của đồ thị. Một bảng gồm tất cả các đồ thị liên thông (không ghi tên đỉnh) có tối đa 5 đỉnh được vẽ ở Hình 1.12. 1.1.5. Đường và chu trình trong đồ thị vô hướng Đường (path) P từ đỉnh v tới đỉnh w là một dãy liên tiếp các cạnh có dạng: (a0, a1), (a1, a2), ... , (ak-1, ak) với (ai-1, ai) E(G), a0 = v, ak = w và k 1, trong đó các đỉnh a0, a1, ... , ak đều khác nhau. Để đơn giản, đôi khi ta viết P = {a0, a1, ... , ak} và nói đó là đường nối đỉnh v và đỉnh w. Đỉnh v gọi là đỉnh đầu, đỉnh w gọi là đỉnh cuối của đường P. Một đường nối một đỉnh với chính nó (đỉnh đầu trùng với đỉnh cuối) gọi là một chu trình (cycle). Độ dài (length) của đường (chu trình) là số cạnh của đường (chu trình) đó. Ví dụ với đồ thị vẽ ở Hình 1.9 một đường nối đỉnh P và đỉnh R là (P, T), (T, Q), (Q, R) hay đơn giản là P, T, Q, R. Hai đường khác từ P tới R là P, T, S, R và P, Q, R hay P, S, R. Đồ thị này có các chu trình sau: (P, Q), (Q, R), (R, S), (S, T), (T, P); (Q, S), (S, T), (T, Q), v.v ... 1.1.6. Biểu diễn đồ thị bằng ma trận Mặc dù cách biểu diễn đồ thị bằng hình vẽ gồm các điểm được nối với nhau bởi các cạnh khá thuận tiện, song cách này không còn phù hợp nếu ta muốn lưu giữ một đồ thị cỡ lớn trên máy tính. Có cách lưu giữ một đơn đồ thị là liệt kê các đỉnh kề với mỗi đỉnh của đồ thị. Ví dụ cho cách biểu diễn này được chỉ ra ở Hình 1.13. v u w u : v, y v : u, w, y w: v, x, y x w, y y : u, v, w, x x y Hình 1.13. Liệt kê các đỉnh kề ∙ ∙ ∙ ∙ Hình 1.14. Đồ thị rỗng N4 Một cách biểu diễn hữu ích khác là dùng các ma trận. 8 • Ma trận kề: Nếu G là một đồ thị với các đỉnh được đánh số 1, 2, … , n, thì ma trận kề (adjacency matrrix) cuả G là ma trận vuông A cấp n, phần tử ở hàng i cột j của A bằng số cạnh nối đỉnh i và đỉnh j của đồ thị. • Ma trận liên thuộc: Nếu các cạnh của đồ thị cũng được đánh số 1, 2, … , m, thì ma trận liên thuộc (incidence matrrix) của G là ma trận chữ nhật M cấp n×m, phần tử ở hàng i cột j của M bằng 1 nếu đỉnh i kề cạnh j và bằng 0 nếu trái lại. Hình 1.15 vẽ đồ thị G cùng với ma trận kề và ma trận liên thuộc của nó. Hình 1.15. Ma trận kề và ma trận liên thuộc 1.2. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT Mục này trình bày một số dạng đồ thị đặc biệt, đáng chú ý và hay được dùng trong lý thuyết đồ thị và trong các ứng dụng. 1.2.1 Đồ thị rỗng (Đồ thị không) Một đồ thị có đỉnh, nhưng không có cạnh nào (tập cạnh rỗng) gọi là một đồ thị rồng (empty graph) hay đồ thị không (null graph). Ký hiệu đồ thị rỗng n đỉnh là Nn. Mỗi đỉnh của một đồ thị rỗng là một đỉnh cô lập (đỉnh bậc 0) và các đồ thị rỗng rất ít được chú ý. Một đồ thị rỗng N4 được vẽ ở Hình 1.14. 1.2.2. Rừng và cây Có thể hiểu đồ thị liên thông theo nghĩa tương đương như sau. Một đồ thị vô hướng gọi là liên thông nếu có đường đi nối hai đỉnh bất kỳ của đồ thị. Trái lại, đồ thị gọi là không liên thông. Đồ thị không liên thông sẽ bị tách thành một số đồ thị con liên thông, đôi một không có đỉnh chung. Mỗi đồ thị con liên thông như thế là một thành phần liên thông. Cạnh e gọi là một cầu (bridge) nếu xóa e (không xóa 9 đỉnh) thì đồ thị còn lại sẽ tăng thêm một thành phần liên thông, mỗi thành phần gồm ít nhất một cạnh. Ví dụ, các đồ thị vẽ ở Hình 1.9 là liên thông, còn đồ thị vẽ ở Hình 1.11 là không liên thông (gồm 3 thành phần liên thông). Một đồ thị vô hướng không có chu trình gọi là một rừng (forest). Một rừng liên thông gọi là một cây (tree), tức cây là một đồ thị liên thông và không có chu trình. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). Rừng có thể gồm nhiều thành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy, rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá (leaf). Đồ thị hình sao là một cây có duy nhất một đỉnh không phải là lá. Một đồ thị con, không chứa chu trình của đồ thị G gọi là một cây của G. Một đồ thị con bao trùm của G mà là một cây được gọi là một cây bao chùm (spanning tree) của G. Một số tính chất đặc trưng của cây: cây n đỉnh có đúng n - 1 cạnh, trong một cây, bao giờ cũng có một đường đi duy nhất nối một cặp đỉnh bất kỳ của cây. Các ví dụ về rừng và cây được vẽ ở Hình 1.16. Hình 1.16. Ví dụ về rừng và cây 1.2.3. Đồ thị đầy đủ Một đơn đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là một đồ thị đầy đủ (completed graph). Đồ thị đầy đủ n đỉnh ký hiệu là Kn. Số cạnh của Kn bằng n(n - 1)/2. Đồ thị K4 và K5 được vẽ ở Hình 1.17. Hình 1.17. Đồ thị đầy đủ K4 và K5 10 1.2.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xe Một đồ thị liên thông và mọi đỉnh bậc 2 gọi là một đồ thị vòng (cycle graph). Ký hiệu đồ thị vòng n đỉnh là Cn. Đồ thị nhận được từ Cn bằng cách bỏ di một cạnh bất kỳ gọi là một đồ thị đường (path graph) n đỉnh, ký hiệu là Pn. Đồ thị nhận được từ Cn - 1 bằng cách thêm vào một đỉnh v và nối mỗi đỉnh của Cn - 1 với v bởi một cạnh, gọi là một đồ thị bánh xe (wheel) n đỉnh, ký hiệu là Wn. Các đồ thị C6, P6 và W6 được vẽ ở Hình 1.18. Hình 1.18. Đồ thị vòng C6, đồ thị đường P6 và đồ thị bánh xe W6 1.2.5. Đồ thị đều (đồ thị chính qui) Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị đều hay đồ thị chính qui (regular graph). Nếu mọi đỉnh có bậc r thì đồ thị được gọi là đồ thị đều (chính qui) bậc r hoặc r - chính qui. Có tầm quan trọng đặc biệt là các đồ thị bậc 3 (cubic graph), tức các đồ thị đều (chính qui) bậc 3. Một ví dụ điển hình về đồ thị bậc 3 là đồ thị Petersen (Petersen graph), đồ thị này được vẽ ở Hình 1.19. Chú ý rằng đồ thị rỗng Nn là đồ thị chính qui bậc 0, đồ thị vòng Cn là đồ thị chính qui bậc 2 và đồ thị đầy đủ Kn là đồ thị chính qui bậc n - 1. Hình 1.19. Đồ thị Petersen (chính qui bậc 3) 1.2.6. Đồ thị Platon Trong các đồ thị chính qui, đáng chú ý là các đồ thị Platon (Platonic graph). Đồ thị Platon được hình thành từ các đỉnh và các cạnh của 5 khối đa diện đều: hình 11 tứ diện, hình tám mặt, hình lập phương, khối hai mươi mặt và khối mười hai mặt (Hình 1.20). Tứ diện Hình tám mặt Hình lập phương Khối 20 mặt Khối 12 mặt Hình 1.20. Đồ thị Platon 1.2.7. Đồ thị hai phần Nếu tập đỉnh của đồ thị G có thể chia tách ra thành hai tập rời nhau A và B sao cho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B, thì G được gọi là một đồ thị hai phần (bipartite graph) (Hình 1.21). Nói một cách khác, đồ thị hai phần là đồ thị mà có thể tô các đỉnh của nó bằng hai màu đen và trắng sao cho mỗi cạnh nối một đỉnh đen (trong A) và một đỉnh trắng (trong B). Có thể chứng minh rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi mọi chu trình trong G đều có độ dài (số cạnh) chẵn. Đồ thị hai phần đầy đủ (complete bipartite graph) là một đồ thị hai phần mà mỗi đỉnh trong A được nối với mỗi đỉnh trong B bằng đúng một cạnh. Ta ký hiệu đồ thị hai phần có r đỉnh đen và s đỉnh trắng là Kr,s. Các đồ thị K1,3; K2,3, K3,3 và K4,3 được vẽ ở Hình 1.22. Dễ dàng kiểm tra lại rằng Kr, s có (r + s) đỉnh và r×s cạnh. Hình 1.21. Đồ thị hai phần Hình 1.22. Đồ thị hai phần đầy đủ: K1,3, K2,3, K3,3, K4,3 12 1.2.8. Đồ thị lập phương Trong các đồ thị hai phần đều (mọi đỉnh có cùng bậc), người ta đặc biệt quan tâm tới các đồ thị lập phương (cubes). Ký hiệu Qk là k - lập phương (k - cube), đó là một đồ thị đều, bậc k (k - chính qui) mà các đỉnh của nó có thể đặt tương ứng với dãy số (a1, a2, … , ak), trong đó mọi ai = 0 hoặc 1, và các cạnh của đồ thị nối liền hai đỉnh tương ứng với hai dãy số chỉ khác nhau ở một vị trí. Để ý rằng Q3 là đồ thị hai phần đều, bậc 3 (Hình 1.23). Có thể kiểm tra lại rằng Qk có 2k đỉnh và k×2k - 1 cạnh, và là đồ thị k - chính qui (đồ thị đều, bậc k). G Hình 1.23. Đồ thị hai phần đều, bậc 3: Q3 G Hình 1.24. Phần bù của đơn đồ thị G 1.2.9. Phần bù của đơn đồ thị Nếu G là một đơn đồ thị với tập đỉnh V(G), thì phần bù (complement) G của G là một đơn đồ thị, với cùng tập đỉnh V(G) và hai đỉnh kề nhau trong G khi và chỉ khi chúng không kề nhau trong G. Chẳng hạn, Hình 1.24 vẽ đồ thị G và phần bù G của nó. Có thể thấy rằng phần bù của một đồ thị đầy đủ là một đồ thị rỗng và phần bù của một đồ thị hai phần đầy đủ là hợp của hai đồ thị đầy đủ. 1.2.10. Đồ thị phẳng Một đồ thị (hay đa đồ thị) G gọi là đồ thị phẳng (planar graph) khi nào nó có thể biểu diễn được trên một mặt phẳng sao cho ứng với mỗi đỉnh là một điểm và ứng với mỗi cạnh là một đoạn thẳng hay cong và bất kỳ hai cạnh nào cũng không có điểm chung khác với các đầu mút của chúng. Chẳng hạn, đồ thị vẽ ở Hình 1.4 và Hịnh 1.5 là các (đa) đồ thị phẳng. Khi đó, mỗi miền mặt phẳng hạn định bởi các cạnh và không chứa đỉnh hoặc cạnh ở bên trong của nó, gọi là một diện (face) của đồ thị phẳng G. Biên (boundary) của một diện là chu trình tạo nên bởi các cạnh hạn định nó. Hai diện gọi là kề nhau 13 (adjacent) khi nào biên của chúng có ít nhất một cạnh chung (hai diện chỉ có đỉnh chung thì không xem là kề). Rõ ràng mỗi đồ thị phẳng liên thông đều có một diện vô hạn duy nhất, còn mọi diện khác đều là diện hữu hạn. Ví dụ. Một bản đồ địa lý không có đảo (không có khuyên) là một đồ thị phẳng: mỗi đỉnh là điểm chung của ít nhất ba đường biên giới (bậc của đỉnh ≥ 3), mỗi cạnh là một đoạn đường biên giới nối hai đỉnh và mỗi diện là một nước. Đồ thị phẳng có các đặc điểm đáng chú ý sau: • Trong một đồ thị phẳng liên thông, giữa số đỉnh n, số cạnh m và số diên d có hệ thức: n - m + d = 2 (công thức Euler). • Trong một đơn đồ thị phẳng phải có ít nhất một đỉnh với bậc ≤ 5. • Đồ thị K5 (Hình 1.17) và K3,3 (Hình 1.22) là hai đồ thị không phẳng. • Một đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con nào thuộc kiểu K5 hay K3,3 (Định lý Kuratowski). Ví dụ. Hình lập phương vẽ ở Hình 1.25a là một đồ thị phẳng. Biểu diễn phẳng của đồ thị được vẽ ở Hình 1.25b. Đồ thị này có số đỉnh n = 8, số cạnh m = 12 và số diện d = 6 (5 diện hữu hạn và 1 diện vô hạn). Công thức Ơle đương nhiên đúng đối với đồ thị phẳng này (8 - 12 + 6 = 2).           Hình 1.25. a) Hình lập phương;       b) Biểu diễn phẳng Tóm lại, chương này đã đề cập tới các khái niệm cơ bản về đồ thị: đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu trình, đồ thị liên thông và không liên thông. Trình bày các phép toán thường dùng trên đồ thị (thêm, bớt đỉnh hoặc cạnh). Miêu tả nhiều dạng đồ thị đặc biệt: rừng và cây, đồ thị hình sao, đồ thị vòng, đồ thị bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ thị đều (chính qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng, ... 14 Chương 2 BÀI TOÁN TÔ MÀU ĐỒ THỊ Chương này đề cập tới bài toán tô màu đồ thị và giới thiệu định lý bốn màu nổi tiếng. Mục 2.1 xét bài toán tô màu các đỉnh của đồ thị. Mục 2.2 xét bài toán tô màu bản đồ. Mục 2.3 xét bài toán tô màu các cạnh của đồ thị. Cuối chương, ở mục 2.4, đề cập tới đa thức màu và vấn đề có bao nhiêu cách tô màu có thể. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [2], [3], [5] và [6]. 2.1. TÔ MẦU CÁC ĐỈNH CỦA ĐỒ THỊ Nhiều vấn đề kỹ thuật hiện đại (chẳng hạn, tin học và tự động hóa) đưa tới việc tô màu các đỉnh của một đồ thị G, sao cho hai đỉnh kề nhau có các màu khác nhau. Để cho gọn, ta sẽ nói một cách tô như thế là một cách tô đúng. Đương nhiên nếu G có n đỉnh thì chỉ việc dùng n màu khác nhau là có thể tô đúng được rồi. Nhưng nhiều khi không cần tới n màu mà chỉ cần một số màu ít hơn cũng tô đúng được. Chẳng hạn, nếu đồ thị G không có chu trình thì chỉ cần 2 màu là đủ tô đúng trong mọi trường hợp. Do đó vấn đề đặt ra là: số màu tối thiểu cần thiết để tô đúng các đỉnh của một đồ thị cho trước là bao nhiêu? Ta nói một đồ thị là k - sắc tính (k - colourable) nếu nó có thể tô đúng bằng k màu. Số k nhỏ nhất mà G còn là k - sắc tính, nghĩa là số màu tối thiểu cần thiết để tô đúng được các đỉnh của G, gọi là số sắc tính hay sắc số (chromatic number) của đồ thị G và viết (G) = k. Hình 2.1. Sắc số của đồ thị: (G) = 4 15 Chẳng hạn, đồ thị G vẽ ở Hình 2.1 có (G) = 4. Các màu được biểu thị bằng chữ cái Hy lạp ( , , và ). Vì vậy, G là k - sắc tính với mọi k ≥ 4. Vấn đề tìm số sắc tính của một đồ thị thường rất phức tạp (trừ khi G không có chu trình), và cho tới nay nó vẫn chưa có một lời giải thỏa đáng. Trong mục này sẽ trình bày một số kết quả đáng chú ý về các đồ thị k - sắc tính. Sau đây ta giả thiết G là đơn đồ thị vô hướng, liên thông và không có khuyên. Rõ ràng, sắc số của đồ thị đầy đủ n đỉnh bằng n: χ(Kn) = n. Vì vậy có các đồ thị với sắc số lớn tùy ý. Theo chiều ngược lại, χ(G) = 1 khi và chỉ khi G là đồ thị không (null graph), tức là đồ thị G có đỉnh nhưng không có cạnh, và χ(G) = 2 khi và chỉ khi G là một đồ thị hai phần khác không (non-null bipartite graph). Chú ý rằng một cây bất kỳ, cũng như mọi chu trình độ dài chẵn bất kỳ là 2 - sắc tính. Ta có thể dễ dàng lấy ví dụ về đồ thị là 3 – sắc tính. Chẳng hạn, các chu trình độ dài lẻ hay các đồ thị bánh xe với một số lẻ đỉnh và đồ thị Petersen là 3 - sắc tính. Các đồ thị bánh xe với một số chẵn đỉnh là 4 - sắc tính. Trong [1] đưa ra một lớp đồ thị phẳng 3 - sắc tính đáng chú ý, đó là các đồ thị với n ≥ 6 đỉnh và mọi đỉnh có bậc 3 (Hình 2.2). Hình 2.2. Đồ thị phẳng đẳng cấp bậc 3 là 3 - sắc tính Ta có thể nói đôi điều về số sắc tính (sắc số) của một đồ thị tuỳ ý: Nếu đồ thị có n đỉnh thì sắc số của nó không vượt quá n, và nếu đồ thị chứa Kr (đồ thị đầy đủ r đỉnh) như một đồ thị con thì sắc số của nó không ít hơn r. Nhìn chung, các kết quả này không giúp ta biết chính xác sắc số của một đồ thị. Tuy nhiên, nếu biết bậc của các đỉnh trong đồ thị thì ta có thể biết nhiều hơn. Định lý 2.1. Nếu đơn đồ thị G có bậc lớn nhất của đỉnh bằng Δ thì G là (Δ + 1) - sắc tính. 16 Chứng minh. Dùng phương pháp quy nạp toán học theo số đỉnh của G. Giả sử G là một đơn đồ thị n đỉnh. Nếu ta xoá một đỉnh bất kỳ v, cùng với các cạnh liên thuộc nó, thì đồ thị còn lại là một đơn đồ thị (n - 1) đỉnh và bậc lớn nhất của đỉnh cùng lắm bằng Δ (xem Hình 2.3). Theo giả thuyết quy nạp, đồ thị này là (Δ + 1) sắc tính. Giữ nguyên màu của các đỉnh trong đồ thị này, ta sẽ tô cho đỉnh v một màu, khác với những màu đã tô cho các đỉnh kề v (số này nhiều nhất bằng ). Kết quả là G được tô bằng ( + 1) màu, tức G là ( + 1) - sắc tính. ∎ Hình 2.3. Minh họa chứng minh Định lý 2.1 Bằng xử lý tinh tế hơn, có thể làm mạnh thêm Định lý 2.1 và đi tới kết quả sau đây, với tên gọi Định lý Brooks. Chứng minh xem [5], tr. 86 - 88. Định lý 2.2. (Brooks, 1941) Nếu G là một đơn đồ thị liên thông mà không phải là một đồ thị đầy đủ và nếu bậc lớn nhất của đỉnh là ≥ 3 thì G là - sắc tính. Cả hai định lý trên đều rất hữu ích, đặc biệt khi bậc của các đỉnh xấp xỉ như nhau. Chẳng hạn theo Định lý 2.1, mỗi đồ thị lập phương (cubic graph) là 4 - sắc tính, và theo Định lý 2.2, mỗi đồ thị lập phương liên thông, khác đồ thị đầy đủ K4, là 3 - sắc tính. Mặt khác, nếu đồ thị có vài đỉnh với bậc lớn thì các định lý này cho ta rất ít thông tin. Điều này được minh hoạ rõ bởi đồ thị hai phần đầy đủ K1,s. Định lý Brooks cho thấy đồ thị này là s - sắc tính, nhưng thực tế chỉ cần dùng 2 màu là có thể tô đúng các đỉnh của đồ thị loại này, nghĩa là K1,s là 2 - sắc tính với mọi s. Không có cách nào hiệu quả để thoát khỏi tình trạng này. Tình trạng tồi tệ này sẽ không xảy ra, nếu ta giới hạn chỉ xét các đồ thị phẳng. Trên thực tế, có thể dễ dàng chứng minh kết quả khá mạnh nói rằng mọi đơn đồ thị phẳng là 6 - sắc tính. Định lý 2.3. Mọi đơn đồ thị phẳng là 6 - sắc tính. 17 Chứng minh. (Tương tự như Định lý 2.1, tức là dùng phương pháp quy nạp theo số đỉnh của đồ thị) Hiển nhiên định lý đúng đối với các đơn đồ thị phẳng không quá 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n đỉnh, và mọi đơn đồ thị phẳng (n - 1) đỉnh là 6 - sắc tính. Do đồ thị G phẳng nên G chứa một đỉnh v có bậc nhiều nhất là 5. Nếu xoá v và các cạnh liên thuộc v thì đồ thị còn lại có n - 1 đỉnh, và vì vậy nó là 6 -sắc tính (xem Hình 2.4). Giữ nguyên màu của các đỉnh trong đồ thị này, ta tô cho đỉnh v bằng màu, khác với những màu đã tô cho các đỉnh kề v (số này không quá 5). Kết quả là G được tô bằng 6 màu, tức G là 6 - sắc tính. ∎ Hình 2.4. Minh họa chứng minh Định lý 2.3 Cũng như Định lý 2.1, có thể làm mạnh thêm Định lý 2.3 này bằng cách xử lý tinh tế hơn. Kết quả nhận được gọi là Định lý 5 màu (Five Colour Theorem). Định lý 2.4. Một đơn đồ thị phẳng bao giờ cũng là 5 - sắc tính. Chứng minh. Tương tự như định lý 2.3, tuy nhiên các chi tiết sẽ phức tạp hơn. Ta chứng minh định lý bằng phương pháp quy nạp theo số đỉnh. Hiển nhiên định lý đúng đối với đơn đồ thị phẳng ít hơn 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n đỉnh, và mọi đơn đồ thị phẳng n - 1 đỉnh là 5 - sắc tính. Do đồ thị G phẳng nên G chứa một đỉnh v với bậc không quá 5. Cũng như trong chứng minh định lý trước, sau khi xoá đỉnh v và các cạnh liên thuộc v, ta được một đơn đồ thị n - 1 đỉnh và đồ thị này là 5 - sắc tính. Mục đích của ta bây giờ là tô đỉnh v bằng một trong 5 màu này, và như vậy sẽ hoàn thành việc tô các đỉnh của G bằng 5 màu. Nếu bậc của đỉnh v nhỏ hơn 5 thì v có thể được tô bằng màu bất kỳ, chưa dùng để tô cho các (tối đa là 4) đỉnh kề v, và như vậy hoàn thành chứng minh định lý trong trường hợp này. Giả sử bậc của v bằng 5 và 5 đỉnh kề v là v1, ... , v5, được 18