Bài giảng Toán rời rạc: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Tô màu đỉnh của đồ thị cung cấp cho người học những nội dung kiến thức như: Định nghĩa và ví dụ, thuật toán tham lam tô màu đỉnh, đồ thị hai phần, một số bài tập. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức Tô màu đỉnh của đồ thị Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 44 Tài liệu tham khảo ▶ Norman L. Biggs, Discrete Mathematics, Oxford University Press, 2002.CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 44 Nội dung Định nghĩa và ví dụ Thuật toán tham lam tô màu đỉnh Đồ thị hai phần Bài tậpCuuDuongThanCong.com https://fb.com/tailieudientucntt Ví dụ Trường BK muốn xếp giờ học cho sáu môn học v1 , v2 , v3 , v4 , v5 , v6 biết rằng có một vài sinh viên học các môn : v1 và v2 , v1 và v4 , v3 và v5 , v2 và v6 , v4 và v5 , v5 và v6 , v1 và v6 . v1 v6 v2 v5 v3 v4CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 44 Xếp lịch học v1 v6 v2 v5 v3 v4 Tiết 1 Tiết 2 Tiết 3 Tiết 4 v1 và v3 v2 và v4 v5 v6CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 44 Xếp lịch học ▶ Ta tìm cách phân hoạch tập đỉnh thành 4 phần sao cho không phần nào chứa cặp đỉnh kề nhau. ▶ Một cách hình thức, đây là một hàm c : {v1 , v2 , v3 , v4 , v5 , v6 } −→ {1, 2, 3, 4} gán mỗi đỉnh với một giờ học. ▶ Không mất tổng quát ta dùng các số nguyên dương cho các màu.CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 44 Định nghĩa Một cách tô màu đỉnh của đồ thị G = (V, E) là một hàm c : V −→ N thỏa mãn tính chất : Nếu {x, y} ∈ E thì c(x) ̸= c(y). v1 v6 v2 v5 v3 v4CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 44 Định nghĩa Sắc số của đồ thị G, ký hiệu là χ(G), là số nguyên k nhỏ nhất thỏa mãn có một cách tô màu G dùng k màu. Nói cách khác, χ(G) = k nếu và chỉ nếu có một cách tô màu c từ V tới tập {1, 2, . . . , k}, và k là số nguyên nhỏ nhất thỏa mãn tính chất này. Ví dụ v1 v6 v2 Tìm sắc số của đồ thị v5 v3 v4CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 44 Tìm số màu Để chứng minh rằng sắc số của một đồ thị là k thì ta phải: 1. tìm một cách tô màu dùng k màu; 2. chứng minh rằng không có cách tô màu nào dùng ít hơn k màu.CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 44 Bài tập Tìm sắc số của các đồ thị sau: (i) đồ thị đầy đủ Kn ; (ii) đồ thị vòng C2r ; (iii) đồ thị vòng C2r+1 ;CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 44 Bài tập Tìm sắc số của các đồ thị sau:CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 44 Bài tập Hãy mô tả tất cả các đồ thị G có χ(G) = 1.CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 44 Nội dung Định nghĩa và ví dụ Thuật toán tham lam tô màu đỉnh Đồ thị hai phần Bài tậpCuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán Cho đồ thị G. Hãy tìm χ(G). là bài toán khó. Người ta chưa biết thuật toán “nhanh” nào để giải nó, và hầu hết mọi người đều tin rằng không có thuật toán như vậy.CuuDuongThanCong.com https://fb.com/ ...