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

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

1. Chương 4 Đồ thị phẳng – Bài toán tô màu đồ thị
2. Lý thuyết đồ thị 6/14/2021 2
3. Đồ thị phẳng n Bài toán mở đầu: u Có 3 gia đình, 3 nhà cung cấp điện, nước, gas. u Các gia đình đều cần điện, nước, gas và đều muốn đi dây riêng. u Cần nối dây từ các gia đình đến các nhà cung cấp sao cho không dây nào cắt dây nào. A B ? C Lý thuyết đồ thị 6/14/2021 3
4. Đồ thị phẳng n Định nghĩa: Đồ thị vô hướng G là đồ thị phẳng nếu ta có thể biểu diễn nó trên một mặt phẳng sao cho không có cạnh nào cắt nhau. VD: Đồ thị phẳng Không là đồ thị phẳng Lý thuyết đồ thị 6/14/2021 4
5. Đồ thị phẳng (tt) n Các đồ thị không phẳng nổi tiếng Đồ thị K5 – đồ thị Đồ thị K3x3 – đồ thị đầy đủ hai phía đầy đủ Lý thuyết đồ thị 6/14/2021 5
6. Công thức Euler n Xét đồ thị sau: 1 2 3 4 6 5 n Định lý: Cho G là đồ thị phẳng, liên thông với n đỉnh và m cạnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó, ta có: r = m - n + 2 Lý thuyết đồ thị 6/14/2021 6
7. Công thức Euler (tt) n Chứng minh công thức Euler: Lý thuyết đồ thị 6/14/2021 7
8. Công thức Euler (tt) n Hệ quả. Nếu G là đơn đồ thị phẳng liên thông với e cạnh, v đỉnh, trong đó v 3. Khi đó ta có: e 3v – 6 n Chứng minh: u Gọi r là số miền u Mỗi miền đều tương ứng với ít nhất 3 cạnh u Mỗi cạnh tướng ứng với đúng 2 miền u Gọi bậc của mỗi miền là số cạnh tương ứng với nó u Suy ra, tổng bậc của các miền ít nhất là bằng 2 lần số cạnh u Áp dụng công thức Euler suy ra điều phải chứng minh. Lý thuyết đồ thị 6/14/2021 8
9. Định lý Kuratowski n Định lý: Đồ thị G là đồ thị phẳng nếu và chỉ nếu G không chứa đồ thị con đẳng cấu với K5 hoặc K3x3 n VD: các đồ thị sau đây không là đồ thị phẳng Lý thuyết đồ thị 6/14/2021 9
10. Tô màu đồ thị Lý thuyết đồ thị 6/14/2021 10
11. Tô màu đồ thị (tt) Phải dùng 3 màu để tổ Phải dùng 4 màu để tổ ? Lý thuyết đồ thị 6/14/2021 11
12. Tô màu đồ thị (tt) Lý thuyết đồ thị 6/14/2021 12
13. Tô màu đồ thị (tt) 1 2 7 8 4 7 1 2 8 4 6 3 6 9 3 5 9 5 2 6 2 6 4 5 1 5 1 4 3 7 3 7 Lý thuyết đồ thị 6/14/2021 13
14. Bài toán tô màu đồ thị n Định nghĩa. Tô màu một đồ thị vô hướng là một sự gán màu cho các đỉnh sao cho hai đỉnh kề nhau phải khác màu nhau. n Định nghĩa. Số màu (sắc số) của một đồ thị là số màu tối thiểu cần thiết để tô màu đồ thị này. 1 2 7 8 2 6 1 4 5 4 3 6 9 3 7 5 Đồ thị có số màu là 3 Đồ thị có số màu là 4 Lý thuyết đồ thị 6/14/2021 14
15. Bài toán tô màu đồ thị (tt) n Định lý. (Định lý 4 màu) Số màu của một đồ thị phẳng là không lớn hơn 4. n Một số thông tin liên quan: u Bài toán được đưa ra năm 1850 u Có rất nhiều chứng minh sai về bài toán này u Chứng minh sai nổi tiếng là của Alfred Kempe vào năm 1879 u Percy Heawood phát hiện ra chứng minh sai ở trên vào năm 1890 u Dựa vào đó, năm 1976 Appel và Haken đã chứng minh bằng cách sử dụng máy tính Lý thuyết đồ thị 6/14/2021 15
16. Bài toán tô màu đồ thị (tt) n Tìm số màu của các đồ thị sau: Lý thuyết đồ thị 6/14/2021 16
17. Ứng dụng n Bài toán lập lịch thi: Hãy lập lịch thi trong một trường đại học sao cho không có sinh viên nào thi hai môn cùng một lúc. n Giải pháp: u Biểu diễn bằng đồ thị: l Mỗi môn học là một đỉnh l Nếu 2 môn học nào được dự thi bởi cùng 1 sinh viên thì sẽ nối bằng 1 cạnh. l Cách lập lịch sẽ tương ứng với bài toán tô màu của đồ thị này. Lý thuyết đồ thị 6/14/2021 17
18. Ứng dụng (tt) n VD: Có 7 môn thi với thông tin như sau: u Môn 1: có các sinh viên A, B, C và D thi u Môn 2: có các sinh viên A, E, F, G và H thi u Môn 3: có các sinh viên B, E, I, J và K thi u Môn 4: có các sinh viên B, F, L và M thi u Môn 5: có các sinh viên G, L, N và O thi u Môn 6: có các sinh viên J, M, N và P thi u Môn 7: có các sinh viên D, H, K, O và P thi Hãy xếp lịch thi thành các đợt sao cho các sinh viên đều có thể dự thi tuần tự các môn mình đăng ký Lý thuyết đồ thị 6/14/2021 18
19. Ứng dụng (tt) n VD: Có 7 môn thi với thông tin như sau: 1 u Môn 1: có các sinh viên A, B, C và D thi 7 2 u Môn 2: có các sinh viên A, E, F, G và H thi u Môn 3: có các sinh viên B, E, I, J và K thi u Môn 4: có các sinh viên B, F, L và M thi 3 u Môn 5: có các sinh viên G, L, N và O thi 6 u Môn 6: có các sinh viên J, M, N và P thi u Môn 7: có các sinh viên D, H, K, O và P thi 5 4 Đợt thi Môn thi 1 1, 5 2 2, 6 3 3 4 4, 7 Lý thuyết đồ thị 6/14/2021 19
20. Ứng dụng (tt) n Bài toán phân chia tần số. u Các kênh truyền hình từ số 2 đến số 13 được phân chia cho các đài truyền hình sao cho không có 2 đài cách nhau không quá 150 dặm lại dùng chung một kênh u Hãy tìm cách phân sao cho số kênh dùng là ít nhất n Giải pháp: u Biểu diễn bằng đồ thị: l Mỗi đỉnh là một đài phát l Hai đỉnh được nối một cạnh nếu hai đài phát cách nhau ít hơn 150 dặm u Số màu của đồ thị chính là số kênh cần dùng. Lý thuyết đồ thị 6/14/2021 20
21. Ứng dụng (tt) n Bài toán các thanh ghi chỉ số: u Trong lập trình các thanh ghi thường được dùng để lưu trữ giá trị các biến tạm thời u Tìm số thanh ghi ít nhất cần sử dụng trong một chương trình n Giải pháp: u Biểu diễn bằng đồ thị: l Mỗi biến tương ứng với mỗi đỉnh l Hai đỉnh được nối với nhau nếu hai biến cùng được ghi xuống tại một thời điểm u Số thanh ghi ít nhất cần sử dụng sẽ là số màu của đồ thị trên Lý thuyết đồ thị 6/14/2021 21