Đang chuẩn bị liên kết để tải về 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

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. | Tô màu đỉnh của đồ thị Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.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ập CuuDuongThanCong.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 v4 CuuDuongThanCong.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 v6 CuuDuongThanCong.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 v4 CuuDuongThanCong.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 v4 CuuDuongThanCong.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 .