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 https tailieudientucntt 1 44 Tài liệu tham khảo Norman L. Biggs Discrete Mathematics Oxford University Press 2002. https 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 https 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 https 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 https 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. https 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 https 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 https 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. https 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 https .
