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

Chương 4Đồ thị phẳng – Bài toán tô màu đồ thị*Lý thuyết đồ thị*Đồ thị phẳngBài toán mở đầu:Có 3 gia đình, 3 nhà cung cấp điện, nước, gas.Các gia đình đều cần điện, nước, gas và đều muốn đi dây riêng.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.*Lý thuyết đồ thị*ABC?Đồ thị phẳngĐị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:*Lý thuyết đồ thị*Đồ thị phẳngKhông là đồ thị phẳngĐồ thị phẳng (tt)Các đồ thị không phẳng nổi tiếng*Lý thuyết đồ thị*Đồ thị K5 – đồ thị đầy đủĐồ thị K3x3 – đồ thị hai phía đầy đủCông thức EulerXét đồ thị sau:Đị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ị*143256Công thức Euler (tt)Chứng minh công thức Euler:*Lý thuyết đồ thị*Công thức Euler (tt)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 – 6Chứng minh:Gọi r là số miềnMỗi miền đều tương ứng với ít nhất 3 cạnhMỗi cạnh tướng ứng với đúng 2 miềnGọi bậc của mỗi miền là số cạnh tương ứng với nóSuy ra, tổng bậc của các miền ít nhất là bằng 2 lần số cạnhÁp dụng công thức Euler suy ra điều phải chứng minh.*Lý thuyết đồ thị*Định lý KuratowskiĐị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 K3x3VD: các đồ thị sau đây không là đồ thị phẳng*Lý thuyết đồ thị*Tô màu đồ thị*Lý thuyết đồ thị*Tô màu đồ thị (tt)*Lý thuyết đồ thị*Phải dùng 3 màu để tổ?Phải dùng 4 màu để tổTô màu đồ thị (tt)*Lý thuyết đồ thị*Tô màu đồ thị (tt)*Lý thuyết đồ thị*13245678912354768912345671243567Bài toán tô màu đồ thịĐị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.Đị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.*Lý thuyết đồ thị*1235476891243567Đồ thị có số màu là 3Đồ thị có số màu là 4Bài toán tô màu đồ thị (tt)Đị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.Một số thông tin liên quan:Bài toán được đưa ra năm 1850Có rất nhiều chứng minh sai về bài toán nàyChứng minh sai nổi tiếng là của Alfred Kempe vào năm 1879Percy Heawood phát hiện ra chứng minh sai ở trên vào năm 1890Dự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ị*Bài toán tô màu đồ thị (tt)Tìm số màu của các đồ thị sau:*Lý thuyết đồ thị*Ứng dụngBà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.Giải pháp:Biểu diễn bằng đồ thị: Mỗi môn học là một đỉnhNế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.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ị*Ứng dụng (tt)VD: Có 7 môn thi với thông tin như sau:Môn 1: có các sinh viên A, B, C và D thiMôn 2: có các sinh viên A, E, F, G và H thiMôn 3: có các sinh viên B, E, I, J và K thiMôn 4: có các sinh viên B, F, L và M thiMôn 5: có các sinh viên G, L, N và O thiMôn 6: có các sinh viên J, M, N và P thiMô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ị*Ứng dụng (tt)*Lý thuyết đồ thị*VD: Có 7 môn thi với thông tin như sau:Môn 1: có các sinh viên A, B, C và D thiMôn 2: có các sinh viên A, E, F, G và H thiMôn 3: có các sinh viên B, E, I, J và K thiMôn 4: có các sinh viên B, F, L và M thiMôn 5: có các sinh viên G, L, N và O thiMôn 6: có các sinh viên J, M, N và P thiMôn 7: có các sinh viên D, H, K, O và P thi 1234567Đợt thiMôn thi11, 522, 63344, 7Ứng dụng (tt)Bài toán phân chia tần số.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ênhHãy tìm cách phân sao cho số kênh dùng là ít nhấtGiải pháp:Biểu diễn bằng đồ thị:Mỗi đỉnh là một đài phátHai đỉnh được nối một cạnh nếu hai đài phát cách nhau ít hơn 150 dặmSố màu của đồ thị chính là số kênh cần dùng.*Lý thuyết đồ thị*Ứng dụng (tt)Bài toán các thanh ghi chỉ số: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ờiTìm số thanh ghi ít nhất cần sử dụng trong một chương trìnhGiải pháp:Biểu diễn bằng đồ thị:Mỗi biến tương ứng với mỗi đỉnhHai đỉ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ểmSố thanh ghi ít nhất cần sử dụng sẽ là số màu của đồ thị trên*Lý thuyết đồ thị*