Bài giảng Lý thuyết đồ thị - Chương 6: Bài toán tô màu đồ thị

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 6: Bài toán tô màu đồ thị

1. Môn học: Lý thuyết đồ thị Chương 6: Bài toán tô màu đồ thị Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
2. Nội dung I. Định nghĩa II. Định lý 4 màu III. Nhận biết đồ thị 2-màu IV. Thuật toán SequentialColor V. Một số bài toán ứng dụng Chương 6 – Bài toán tô màu đồ thị 2 Lý thuyết đồ thị
3. I. Định nghĩa ™ Cần phải tô màu một bản đồ với điều kiện: ƒ Hai miền chung biên giới được tô hai màu khác nhau ƒ Số màu cần dùng là tối thiểu ™ Hãy xác định số màu tối thiểu cho mọi bản đồ Bản đồ này cần dùng 4 màu để tô Chương 6 – Bài toán tô màu đồ thị 3
4. I. Định nghĩa a d c be Bài toán tô màu bản đồ quy về bài toán tô màu các Đỉnh của đồ thị Định nghĩa 1 Tô màu một đơn đồ thị là sự gán màu cho các đỉnh của nó sao cho hai đỉnh liền kề nhau được gán màu khác nhau. Định nghĩa 2 Số màu của một đồ thị là số tối thiểu các màu cần thiết để tô màu đồ thị này. Chương 6 – Bài toán tô màu đồ thị 4
5. II. Định lý 4 màu ™Định lý: Số màu của một đồ thị phẳng là không lớn hơn 4 ƒ Định lý này được phát biểu lần đầu tiên năm 1850 và được 2 nhà toán học Mỹ Appel và Haken chứng minh năm 1976 bằng phản chứng. ƒ Đối với các đồ thị không phẳng số màu có thể tuỳ ý lớn ƒ Để chứng minh đồ thị G là n-màu ta phải • Chỉ ra 1 cách tô màu G với n màu • CMR không thể tô màu G với ít hơn n màu Chương 6 – Bài toán tô màu đồ thị 5
6. II. Định lý 4 màu ™ Các bài toán tô màu đồ thị 1. Cho đồ thị G và số nguyên k. Xây dựng một thuật toán để kiểm tra xem có thể tô màu G bằng k màu, nếu được thì thực hiện việc đó. 2. Cho đồ thị G hãy xác định số màu k của đồ thị và hãy tô màu G bằng k màu đó Chương 6 – Bài toán tô màu đồ thị 6
7. II. Nhận biết đồ thị 2-màu ™ Định lý Một đồ thị G là 2-màu khi và chỉ khi G không chứa một chu trình lẻ nào. ™ Chứng minh 1. Giả sử G là đồ thị 2-màu ta phải CMR G không chứa chu trình lẻ. Thật vậy nếu G có chu trình lẻ C=(v1, v2, , v2n+1, v1) Do C chỉ được tô bởi 2 màu ⇒ các đỉnh lẻ sẽ được tô bằng 1 màu. Nhưng lúc đóv1 và v2n+1 là 2 đỉnh kề nhau có cùng màu vô lý !!! (ĐPCM) Chương 6 – Bài toán tô màu đồ thị 7
8. II. Nhận biết đồ thị 2-màu ™ Chứng minh 2. Giả sử G không chứa chu trình lẻ.Ta sẽ CMR G là đồ thị 2-màu. ƒ Chọn 1 đỉnh r làm gốc và tô nó màu đỏ. ∀ x ∈ V sẽ được tô màu đỏ nếu đường đi ngắn nhất từ x tới r có số cành chẵn. Trái lại tô x màu xanh. ƒ Ta sẽ chứng minh rằng đỉnh x, y của cạnh (x,y) bất kỳ được tô hai màu khác nhau. ƒ Trái lại giả sử x và y là 2 đỉnh của cạnh (x,y) nào đó được tô cùng màu Chương 6 – Bài toán tô màu đồ thị 8
9. II. Nhận biết đồ thị 2-màu ™ Chứng minh ƒ Trường hợp 1: Px và Py không có chung cạnh. Ta có Px + (x,y) + Py là chu trình có số cạnh lẻ. (Mâu thuẫn giả thiết). Chương 6 – Bài toán tô màu đồ thị 9
10. II. Nhận biết đồ thị 2-màu ™ Chứng minh ƒ Trường hợp 2: Px và Py có chung k cạnh từ đỉnh a tới đỉnh b. Ta sẽ nhận được hai chu trình Ca , Cb và k cạnh chung. Ta có Px + (x,y) + Py có số lẻ cạnh mà: | Px + (x,y) + Py | = | Ca | + | Cb | + 2k Do đómột trong hai chu trình Ca hoặc Cb sẽ có số cạnh lẻ Vô lý !!! (ĐPCM) Vậy G là 2 - màu Chương 6 – Bài toán tô màu đồ thị 10
11. III. Thuật toán SequentialColor Vớik=2 việcnhậnbiết đồ thị 2 – màu đã đượcgiảiquyết Tuy vậyviệcnhậnbiết đồ thị k – màu vớik > 2 vẫnchưacó lờigiải ThuậttoánSequentialColor tô màu 1 đồ thị với k màu: Xem các đỉnh theo thứ tự từ 1 đến|V|, tạimỗi đỉnh v gán màu đầutiêncósẵnmàchưa được gán cho 1 đỉnh nào liềnv 1. Xếpcácđỉnh theo thứ tự bấtkỳ 1,2, n 2. TạotậpLi -tậpcácmàucóthể gán cho đỉnh I 3. Bắt đầutôtừđỉnh 1 4. Với đỉnh k ∈ {1, ,n} tô màu đầutiêncủaLk cho k 5. ∀ j > k và j kề k loạibỏ trong Lj màu đã đượctôchok 6. Giảithuậtdừng lạikhitấtcả các đỉnh đã đượctô Chương 6 – Bài toán tô màu đồ thị 11
12. III. Thuật toán SequentialColor ™ Ví dụ Các màu: X: Xanh Đ: Đỏ T: Tím V: Vàng Thứ tự tô các đỉnh: 1, 2, 3, 4 Các bướcL1L2L3L4Màu tô Khởi tạoX, Đ, T, V X, Đ, T, V X, Đ, T, V X, Đ, T, V B1 X X, Đ, T, V X, Đ, T, V Đ, T, V 1 - Xanh B2 X Đ, T, V Đ, T, V 2 - Xanh B3 Đ T, V 3 - Đỏ B4 T 4 - Tím Chương 6 – Bài toán tô màu đồ thị 12
13. III. Thuật toán SequentialColor ™ Ví dụ Các màu: X: Xanh Đ: Đỏ T: Tím V: Vàng Thứ tự tô các đỉnh: 4, 3, 2, 1 Các bướcL4L3L1L2Màu tô Khởi tạoX, Đ, T, V X, Đ, T, V X, Đ, T, V X, Đ, T, V B1 X Đ, T, V Đ, T, V X, Đ, T, V 4 - Xanh B2 ĐĐ, T, V X, T, V 3 - Đỏ B3 Đ X, T, V 1 - Đỏ B4 X 2 - Xanh Chương 6 – Bài toán tô màu đồ thị 13
14. III. Thuật toán SequentialColor ™ Nhận xét ƒ Là dạng thuật toán tham lam Æ Lời giải tìm được chưa chắc tối ưu ƒ Độ phức tạp của giải thuật O(n2) Chương 6 – Bài toán tô màu đồ thị 14
15. IV.Một số bài toán ứng dụng ™Bài toán lập lịch thi ƒ Lập lịch thi: Hãy lập lịch thi trong trường đại học sao cho không có sinh viên nào có 2 môn thi cùng lúc • Các đỉnh : Các môn thi • Có 1 cạnh nối 2 đỉnh nếu như có 1 SV thi cả 2 môn này • Thời gian thi được thể hiện bởi các màu khác nhau ƒ Việc lập lịch thi sẽ tương ứng với việc tô màu đồ thị này Chương 6 – Bài toán tô màu đồ thị 15
16. IV.Một số bài toán ứng dụng ™ Bài toán lập lịch thi ƒ Có 7 môn thi: Toán (t), Anh Văn (a), Lý (l), Pascal (p), Tin học đại cương (h), Tiếng vệt thực hành (v), Visual Basic (b). ƒ Các cặp môn thi có chung sinh viên là: (t,a), (t, l), (t, p), (t,b),(a,l), (a,p), (a,h), (a,b), (l,p), (l,b), (p,h), (p,v), (h,b), (v,b). Kết quả tô màu al p h v b t Đỏ Xanh Tím Nâu Lá cây Vàng Đen Kết quả xếp lịch thi Đợt thi Môn thi 1Anh Văn 2 Lý, Tin học đại cương 3 Pascal, Visual Basic 4Tiếng việt thực hành, Toán Chương 6 – Bài toán tô màu đồ thị 16
17. IV.Một số bài toán ứng dụng ™Bài toán phân chia tần số ƒ Phân chia tần số: Các kênh truyền hình từ số 2 tới 13 được phân chia cho các đài truyền hình ở Bắc Mỹ sao cho 2 đài ở gần nhau dưới 150 km có 2 kênh khác nhau ƒ Giải quyết: • Mỗi đài phát : 1 đỉnh • Hai đài gần nhau dưới 150 km là 2 đỉnh được nối với nhau • Việc phân chia kênh: Tô màu đồ thị, trong đómỗi màu biểu thị một kênh Chương 6 – Bài toán tô màu đồ thị 17