Tài liệu Tô màu đồ thị và ứng dụng

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ĐỖ VĂN PHONG TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Hà Nội – Năm 2017 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ĐỖ VĂN PHONG TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng NGƯỜI HƯỚNG DẪN KHOA HỌC Th.s PHẠM VĂN DUẨN Hà Nội – Năm 2017 1 LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận tốt nghiệp, tôi xin bày tỏ lòng biết ơn sâu sắc tới Th.s Phạm Văn Duẩn người đã tận tình hướng dẫn để tôi có thể hoàn thành khóa luận này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô trong Khoa Toán, Trường đại học sư phạm Hà Nội 2 đã dạy bảo tôi tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. Hà Nội, ngày 24 tháng 04 năm 2017 Sinh viên ĐỖ VĂN PHONG Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG LỜI CAM ĐOAN Tôi xin cam đoan kết quả nghiên cứu trong khóa luận này là trung thực và chưa hề được sử dụng để bảo vệ một học vị nào. Mọi sự giúp đỡ cho việc thực hiện khóa luận này đã được cảm ơn và các thông tin trích dẫn trong khóa luận đã được chỉ rõ nguồn ngốc một cách rõ ràng và được phép công bố.Tôi hoàn toàn chịu trách nhiệm trước nhà trường về sự cam đoan này. Hà Nội, ngày 24 tháng 04 năm 2017 Sinh viên ĐỖ VĂN PHONG i Mục lục Lời mở đầu 1 1 KIẾN THỨC CHUẨN BỊ 3 1.1 1.2 Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . 3 1.1.2 Quan hệ kề nhau . . . . . . . . . . . . . . . . . 6 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . 9 1.2.1 Đồ thị phân đôi . . . . . . . . . . . . . . . . . . 9 1.2.2 Những đồ thị đơn đặc biệt . . . . . . . . . . . . 10 2 TÔ MÀU ĐỒ THỊ 2.1 2.2 2.3 12 Tô màu đỉnh . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . 12 2.1.2 Định lý . . . . . . . . . . . . . . . . . . . . . . 12 2.1.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . 21 Tô màu bản đồ . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Định lý . . . . . . . . . . . . . . . . . . . . . . 26 2.2.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . 31 Đa thức tô màu . . . . . . . . . . . . . . . . . . . . . . 34 ii Khóa luận tốt nghiệp Đại học 2.4 2.5 ĐỖ VĂN PHONG 2.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . 34 2.3.2 Định lý . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . 37 Thuật toán tô màu Welsh-Powell . . . . . . . . . . . . 40 2.4.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . 40 2.4.2 Ví dụ 41 . . . . . . . . . . . . . . . . . . . . . . . Kết luận chương . . . . . . . . . . . . . . . . . . . . . 3 MỘT SỐ ỨNG DỤNG CỦA TÔ MÀU ĐỒ THỊ 3.1 3.2 3.3 3.4 42 43 Bài toán xếp lịch thi . . . . . . . . . . . . . . . . . . . 43 3.1.1 Bài toán . . . . . . . . . . . . . . . . . . . . . . 43 3.1.2 Cách giải . . . . . . . . . . . . . . . . . . . . . 43 3.1.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . 44 Bài toán phân chia tần số . . . . . . . . . . . . . . . . 46 3.2.1 Bài toán . . . . . . . . . . . . . . . . . . . . . . 46 3.2.2 Cách giải . . . . . . . . . . . . . . . . . . . . . 46 3.2.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . 46 Bài toán soduku . . . . . . . . . . . . . . . . . . . . . . 49 3.3.1 Bài toán . . . . . . . . . . . . . . . . . . . . . . 49 3.3.2 Cách giải . . . . . . . . . . . . . . . . . . . . . 49 3.3.3 Ví dụ 50 . . . . . . . . . . . . . . . . . . . . . . . Kết luận chương . . . . . . . . . . . . . . . . . . . . . iii 53 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Lời mở đầu 1.Lý do chọn đề tài Khái niệm lý thuyết đò thị được khá nhiều nhà khoa học độc lập nghiên cứu và có nhiều đóng góp trong lĩnh vực toán học ứng dụng. Sử dụng bài toán tô màu để giải bài toán là một phương pháp hay trong lý thuyết đồ thị. Phương pháp này không đòi hỏi nhiều về kiến thức và khả năng tính toán mà chủ yếu đòi hỏi sự sáng tạo trong việc đưa ra một mô hình cụ thể và linh hoạt trong cách tư duy, không thể áp dụng một cách máy móc được. Đó là điểm mạnh cũng như cái khó của bài toán tô màu. Hiện nay, các tài liệu viết về lý thuyết đồ thị chưa được nhiều cũng gây ra một chút khó khăn cho việc nghiên cứu tài liệu tham khảo. Trong khi đó các tài liệu còn chưa đề cập nhiều đến ứng dụng của bài toán tô màu. Để hiểu rõ hơn về lý thuyết đồ thị và ứng dụng của nó trong việc giải quyết một số bài toán thực tế bằng cách tô màu cho đồ thị, tôi đã lựa chọn đề tài :"TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG". 2.Mục đích nghiên cứu Nghiên cứu tô màu đồ thị và ứng dụng vào một số bài toán thực tiễn 3. Đối tượng và phạm vi nghiên cứu -Đối tượng nghiên cứu: Đồ thị và các ứng dụng của đồ thị 1 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG -Phạm vi nghiên cứu: Tô màu đồ thị và một số ứng dụng tô màu đồ thị 4. Phương pháp nghiên cứu -Phương pháp nghiên cứu tài liệu. -Phương pháp đánh giá. -phương pháp hệ thống hóa một số ứng dụng của đồ thị. 5. Cấu trúc khóa luận Nội dung khóa luận bao gồm 3 chương: -Chương 1. Kiến thức chuẩn bị -Chương 2. Tô màu đồ thị -Chương 3. Một số ứng dụng tô màu đồ thị Do thời gian thực hiện đề tài không nhiều, kiến thức còn hạn chế nên khóa luận không thể tránh những sai sót. Tôi mong nhận được sự đóng góp ý kiến ý kiến phản biện của quý thầy cô và các bạn. Xin chân thành cảm ơn! 2 Chương 1 KIẾN THỨC CHUẨN BỊ Nhắc lại một số khái niệm, tính chất cơ bản của đồ thị có được sử dụng trong quá trình tìm hiểu chương 2 và chương 3. 1.1 1.1.1 Đồ thị Định nghĩa đồ thị Định nghĩa 1.1. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó, ký hiệu là G = (V, E) trong đó V được gọi là tập đỉnh và E được gọi là tập cạnh. Có thể coi E là tập tất cả các cặp (u, v) với u và v là hai đỉnh của V . Một số hình ảnh của đồ thị. Hình 1.1: Ví dụ về mô hình đồ thị. 3 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Định nghĩa 1.2. Đồ thị vô hướng là tập hữu hạn G gồm hai tập hữu hạn con V, E (ký hiệu G = {V, E}) với V là tập các đỉnh của đồ thị, E là tập các cặp đỉnh (i, j) mà các cặp này không tính đến thứ tự (nghĩa là trình tự (i, j) cũng giống như trình tự (i, j)). Cặp (i, j) gọi là cạnh của đồ thị. Ví dụ 1.1.1. Hình 1.2 là biểu diễn hình học của đồ thị vô hướng. Hình 1.2: Đồ thi vô hướng Định nghĩa 1.3. Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó trên một mặt phẳng sao cho các cạnh của nó không cắt nhau tại một điểm khác đỉnh. Hình vẽ đó gọi là một biểu diễn phẳng của đồ thị. Ví dụ 1.1.2. Một số hình ảnh về đồ thị phẳng Hình 1.3 Hình 1.3: Đồ thị phẳng 4 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Định lý 1.1. (Bất đẳng thức cạnh đỉnh).Trong một đồ thị phẳng liên thông G = (V, E) bất kỳ với chu vi nhỏ nhất g thỏa mãn 3 ≤ g < ∞ ta luôn có |E| ≤ g (|V | − 2) g−2 . Chứng minh. Giả sử G = (V, E) là đồ thị phẳng liên thông thỏa mãn của định lý. Ta cũng giả sử rằng G có E = {e1 , e2 , ..., et } và các miền f1 , f2 , ..., fl . Ta xác định ma trận X = (xij )txl cỡ t x l như sau: xij =   1 nếu ei là một cạnh biên trên miền fj ,  0 trong trường hợp ngược lại . Ma trận X xác định như trên gọi là ma trận cạnh miền của đồ thị phẳng G. Vì mỗi cạnh của G là một cạnh trên biên của nhiều nhất hai miền, nên trong mỗi hàng của ma trận X có nhiều nhất là hai số 1. Mặt khác, các cạnh ở trên biên của mỗi miền tạo thành một chu trình trong G. Do đó, mỗi cột của ma trận X có ít nhất g số 1, ở đây g là chu vi nhỏ nhất của G. Vì vậy, nếu s là số các số 1 có trong X, thì ta có các bất đẳng thức sau đây: gl ≤ s ≤ 2t Mặt khác, vì G liên thông nên l = t − |V | + 2. Sau khi thay thế vào 5 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG các bất đẳng thức trên ta được gl = gt − g |V | + 2g ≤ 2t ⇔ t(g − 2) ≤ g(|V | − 2) ⇔ |E| ≤ g g−2 (|V | − 2) do đó bất đẳng thức được chứng minh. 1.1.2 Quan hệ kề nhau Định nghĩa 1.4. Hai đỉnh u và v trong một đồ thị vô hướng G được gọi là liền kề nếu u, v là một cạnh của G. Nếu e = {u, v} thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là điểm đầu mút của cạnh {u, v}. Ví dụ 1.1.3. Trên hình 1.2 {a, b} , {b, c} , {c, d} , {d, a} , {a, c} gọi là hai đỉnh kề nhau. Định nghĩa 1.5. Bậc của một đỉnh trong đồ thị vô hướng là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Người ta ký hiệu bậc của đỉnh v là deg(v). Ví dụ 1.1.4. Bậc của các đỉnh trong các đồ thị G và H trên hình 1.4 là bao nhiêu? Hình 1.4: Đồ thị vô hướng G và H. 6 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Lời giải: Trong G, deg(a)=2, deg(b)=deg(c)=deg(f)=4, deg(d)=1, deg(e)=3 và deg(g)=0. Trong H, deg(a)=4, deg(b)=deg(e)=6, deg(c)=1 và deg(d)=5. Định nghĩa 1.6. Đường đi từ i đến j trên đồ thị là một dãy các đỉnh mà mỗi đỉnh thuộc dãy (trừ đỉnh cuối) luôn kề với đỉnh đứng ngay sau nó: i = x1 , x2 , x3 , ..., xk , xk+1 , ..., xn = j với mọi k = 1, 2, 3, ..., n − 1 x1 = i gọi là đỉnh đầu; xn = j gọi là đỉnh cuối của đường đi p. Ví dụ 1.1.5. Trên đồ thị Hình 1.4 có {a, b, e, f, c, d} , {a, b, c, d} là hai đường đi của đồ thị G. Định nghĩa 1.7. Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau. Ví dụ 1.1.6. Trên Hình 1.2 có các chu trình là {a, b, c, d, a} , {a, b, c, a} , {a, c, d, a}. Định nghĩa 1.8. Đồ thị vô hướng G = {V, E} được gọi là đồ thị liên thông nếu luôn tìm được đường đi giũa hai đỉnh bất kỳ của nó. Ví dụ 1.1.7. Đồ thị liên thông G Hình1.5 Hình 1.5: Đồ thị liên thông G Định nghĩa 1.9. Một cạnh e = (i, j) thuộc một đồ thị G {V, E} được gọi là cầu của đồ thị nếu sau khi xóa bỏ cạnh đó thì số thành phần liên thông của đồ thị tăng lên. 7 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Ví dụ 1.1.8. Từ hình 1.5 sau khi ta xóa đi cạnh {b, f } thì sô miền liên thông tăng lên một Hình 1.6 Hình 1.6: Cầu của đồ thị G Định nghĩa 1.10. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh đúng một lần.Chu trình Euler là đường đi Euler có điểm đầu điểm cuối trùng nhau. Định nghĩa 1.11. Đồ thị Euler vô hướng là đồ thị chứa một chu trình Euler. Ví dụ 1.1.9. Hình1.7 là đồ thị Euler Hình 1.7: Đồ thị vô hướng G. Vì có chu trình là a-e-c-d-e-b-a (tồn tại đường đi qua tất cả các cạnh chỉ một lần với điểm đầu trùng điểm cuối). 8 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Định nghĩa 1.12. Cho hai đồ thị G = (V, E) và G0 = (V 0 , E 0 ). Ta nói rằng G đẳng cấu G0 , ký hiệu G ∼ = G0 , nếu tồn tại một song ánh f : V → V 0 sao cho:uv là cạnh của G ⇔ f (u)f (v) là cạnh của G0 Ví dụ 1.1.10. Hình 1.8 cho ta thấy sự đẳng cấu giữa hai đồ thị G và H Hình 1.8: Đồ thị đẳng cấu giữa G và H. 1.2 1.2.1 Một số dạng đồ thị đặc biệt Đồ thị phân đôi Định nghĩa 1.13. Một đồ thị G được gọi là một đồ thị phân đôi nếu tập các đỉnh V có thể phân làm hai tập con không rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh của V1 với một đỉnh của V2 . Ví dụ 1.2.1. C6 là phân đôi như chỉ ra trên hình 1.9, vì các đỉnh của nó có thể chia làm hai tập con V1 = {v1 , v3 , v5 } và V2 = {v2 , v4 , v6 } và mỗi cạnh của C6 nối một đỉnh của V1 với một đỉnh của V2 . 9 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Hình 1.9: Minh họa C6 đồ thị phân đôi. 1.2.2 Những đồ thị đơn đặc biệt Định nghĩa 1.14. Một biểu đồ khối là một đồ thị trong đó tất cả các đỉnh đều có bậc ba. Ví dụ 1.2.2. Tất cả các đồ thị Petersen là một đồ thị khối (Hình 1.10). Hình 1.10: Đồ thị Petersen Định nghĩa 1.15. Đồ thị đầy đủ n đỉnh, ký hiệu là Kn , là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối. Đồ thị Kn có tất cả n(n−1) 2 cạnh. Nó là đồ thị đơn có nhiều cạnh nhất, đồng thời là đồ thị chính quy bậc n − 1. Ví dụ 1.2.3. Sau đây là danh sách và hình vẽ các đồ thị đầy đủ với số đỉnh từ 1 đến 8 cùng với số cạnh của chúng (Hình 1.11). Định nghĩa 1.16. Đồ thị vòng là đồ thị có n đỉnh v1 , v2 , . . . ,vn và n cạnh (v1 , v2 ),(v2 , v3 ), . . . ,(vn−1 , vn ), ký hiệu bởi Cn . 10 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Hình 1.11: Các đồ thị Kn , 1 ≤ n ≤ 8 Ví dụ 1.2.4. Sau đây là hình biểu diễn của đồ thị C3 , C4 , C5 , C6 (Hình 1.12) Hình 1.12: Các chu trình Cn , 3 ≤ n ≤ 6 11 Chương 2 TÔ MÀU ĐỒ THỊ 2.1 Tô màu đỉnh 2.1.1 Định nghĩa Định nghĩa 2.1. Một tô màu đỉnh của một đồ thị, mà ta sẽ đơn giản gọi là một tô màu, là một phép gán các màu cho các đỉnh sao cho hai đỉnh kề nhau bất kỳ có màu khác nhau. Định nghĩa 2.2. Sắc số cảu một đồ thi G, ký hệu χ(G), là số tự nhiên k nhỏ nhất để G có một k -tô màu. Đồ thị G được gọi là đồ thị k -tô màu. Đồ thị G được gọi là đồ thị k-tô màu được nếu χ(G) ≤ k và được gọi là k-sắc nếu χ(G) = k. 2.1.2 Định lý Định lý 2.1. Nếu G là đồ thị đơn giản có đỉnh bậc lớn nhất là 4 thì G là 4+1-tô màu được. Chứng minh. Chúng ta đi chứng minh định lý bằng phép qui nạp trên 12 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG số đỉnh của G. Hiển nhiên nếu G là đồ thị một đỉnh thì G có bậc lớn nhất là 4=0, nên đồ thị G lúc này là 4+1-tô màu được hay là 1-tô màu được. Bây giờ chúng ta giả sử G là một đồ thị đơn giản với số đỉnh là n và có bậc lớn nhất là 4 thì G là 4+1-tô màu được. Chứng minh, nếu xóa đi đỉnh v bất kỳ và các cạnh kề với nó. Khi đó đồ thị G còn lại n-1 đỉnh và đỉnh có bậc lớn nhất là 4, thì đồ thị G là 4+1-tô màu được. Hình 2.1. Bằng phép qui nạp của chúng ta giả thiết, đồ thị G là 4+1-tô màu được. Với 4+1 màu thì G đạt được bằng màu của v và các màu khác nhau từ các đỉnh kề với v. Hình 2.1: Đồ thị G Định lý 2.2. (Konig, 1936.)Giả sử G = (V.E) là một đồ thị bấy kỳ. Khi đó các khẳng định sau đây là tương đương nhau: 1. G là đồ thị 2-sắc; 2. G là đồ thị 2-phần khác đồ thị rỗng; 3. G là đồ thị khác rỗng và mọi chu trình trong G đều có độ dài chẵn. 13 Khóa luận tốt nghiệp Đại học ĐỖ VĂN PHONG Chứng minh. (a). (1)⇒(2): Giả sử G là đồ thị 2-sắc. Ta cũng giả sử rằng V1 và V2 là hai lớp đỉnh đồng màu của G trong 2-tô màu nào đó. Khi đó dễ thấy rằng G là đồ thị 2-phần với các phần là V1 và V2 . Vì G là 2-sắc, nên G cũng là đồ thị không rỗng. (b). (2)⇒(1): Giả sử G là đồ thị 2-phần khác đồ thị rỗng. Ta cũng giả sử rằng V1 và V2 là các phần của G. Ta tô các đỉnh của V1 bằng một màu và tô các đỉnh của V2 bằng một màu khác. Khi đó ta nhận được 2-tô màu của G vì G là đồ thị 2-phần. Mặt khác, G không có 1-tô màu vì nó là đồ thị khác rỗng. Vậy χ(G) = 2 và G là đồ thị 2-sắc. (c). (2)⇒(3):Giả sử G = (V, E) là đồ thị 2-phần khác đồ thị rỗng với các phần là V1 và V2 . Ta cũng giả sử rằng rằng C = v1 v2 v3 . . . vn v1 là một chu trình bất kỳ trong G. Nếu v1 ∈ V1 , thì v2 ∈ V2 , v3 ∈ V1 , v4 ∈ V2 , . . . , tức là những đỉnh với chỉ số dưới lẻ là đỉnh thuộc V1 , còn những đỉnh với chỉ số dưới chẵn là đỉnh thuộc V2 . Vì thế, độ dài của chu trình C phải là chẵn. (d). (3)⇒(2): giả sử G =(V, E) là đồ thị khác rỗng trong đó mọi chu trình đều có độ dài chẵn. Trước hết ta xét trường hợp G là liên thông. Ta cố định một đỉnh bất kỳ v1 ∈ V. Với mỗi đỉnh v ∈ V, ta gọi khoảng cách từ đỉnh v tới đỉnh v1 là độ dài của đường ngắn nhất trong G từ v tới v1 . Ký hiệu bằng V1 tập tất cả các đỉnh của G, mà có khoảng cách tới v1 là chẵn. Đặt V2 = V\V1 . Giả sử tồn tại cạnh trong G nối hai đỉnh u,v ∈ V1 . Gọi Pu và Pv là 14