ài toán tô màu cho các đỉnh (hay các cạnh) của một đồ thị để giải toán là phương pháp khá hay và hấp dẫn của lý thuyết đồ thị. Phương pháp này không đòi hỏi nhiều về khả năng tính toán mà chủ yếu đòi hỏi sự sáng tạo trong việc đưa ra mô hình cụ thể và linh hoạt trong cách tư duy không thể áp dụng một cách máy móc được. Đó là điểm mạnh cũng như cái khó của bài toán tô màu. Mời các bận cùng tham khảo. | ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC o0o ĐINH THỊ VÂN LUẬT TƯƠNG HỖ TRONG TÔ MÀU ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC o0o ĐINH THỊ VÂN LUẬT TƯƠNG HỖ TRONG TÔ MÀU ĐỒ THỊ Chuyên ngành Phương pháp Toán sơ cấp Mã số 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC LÊ TRƯỜNG THÁI NGUYÊN 2017 iii Mục lục Lời cảm ơn 1 Danh mục các hình vẽ và bảng biểu 2 Mở đầu 4 1 ĐA THỨC MÀU CỦA ĐỒ THỊ 6 . Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . 6 . Đơn đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 6 . Các thuật ngữ cơ bản . . . . . . . . . . . . . . . . . . 8 . Đường đi chu trình . . . . . . . . . . . . . . . . . . . 8 . Tính liên thông . . . . . . . . . . . . . . . . . . . . . 9 . Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . . . 10 . Đồ thị vòng . . . . . . . . . . . . . . . . . . . . . . . 10 . Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . 12 . Đồ thị Petersen . . . . . . . . . . . . . . . . . . . . 12 . Đồ thị hai phần đầy đủ . . . . . . . . . . . . . . . . . 12 . Tô màu đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 14 . Tô màu thực sự . . . . . . . . . . . . . . . . . . . . . 14 . Đồ thị phẳng . . . . . . . . . . . . . . . . . . . . . . 16 . Định lí bốn màu . . . . . . . . . . . . . . . . . . . . 17 . Đồ thị xóa co rút . . . . . . . . . . . . . . . . . . . . 17 . Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . 18 . Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 21 iv . Hệ quả . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Luật tương hỗ của đa thức màu 28 . Định hướng của đồ thị . . . . . . . . . . . . . . . . . . . . . 28 . Đường định hướng . . . . . . . . . . . . . . . . . . . . . . . 29 . Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 . Cặp tương thích . . . . . . . . . . . .
