Tiểu Luận Bài toán tô mầu đồ thị và ứng dụng

MỤC LỤC
MỤC LỤC 1
LỜI MỞ ĐẦU 2
PHÂN CÔNG CÔNG VIỆC NHÓM 3. 3
Chương 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ. 4
1.1 Các khái niệm cơ bản. 4
1.1.1 Đồ thị vô hướng và đồ thị có hướng. 4
1.1.2 Bậc, nửa bậc vào, nửa bậc ra. 5
1.1.3 Đường đi, chu trình, tính liên thông. 5
1.2 Đồ thị đẳng cấu. 7
1.3 Đồ thị phẳng. 8
1.3.1 Đồ thị phẳng. 8
1.3.2 Công thức Euler. 8
Chương 2: BÀI TOÁN TÔ MÀU ĐỒ THỊ. 9
2.1 Tô màu đỉnh. 9
2.2 Thuật toán tuần tự ưu tiên đỉnh bậc lớn nhất. 12
2.3 Tô màu đồ thị phẳng. 14
2.4 Tô màu cạnh. 16
Chương 3: MỘT SỐ BÀI TOÁN ỨNG DỤNG 17
3.1 Ứng dụng bài toán tô màu đỉnh. 17
3.1.1 Bài toán điều khiển đèn hiệu nút giao thông. 17
3.1.2 Bài toán lập lịch thi 18
3.1.3 Bài toán phân chia tần số. 19
3.1.4 Bài toán thanh ghi trong bộ dịch. 20
3.1.5 Bài toán nữ sinh của Kirkman. 21
3.2 Ứng dụng bài toán tô màu cạnh. 22
3.2.1 Bài toán nữ sinh Lucas. 22
3.2.2 Bài toán chia thời khóa biểu. 23
KẾT LUẬN 25
TÀI LIỆU THAM KHẢO 26

LỜI MỞ ĐẦU
Lý thuyết đồ thị là một lĩnh vực khoa học đã có từ lâu và có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về những cái cầu ở thành phố Konigsberg.
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó, nó được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau như xác định các mạch vòng trong vấn đề mạch điện, phân biệt các hợp chất hữu cơ khác nhau có cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị Ngoài ra, đồ thị được sử dụng để giải các bài toán thực tế về lập lịch, lập thời khóa biểu, phân bố tần số cho các trạm phát thanh và truyền hình
Cùng với sự phát triển khoa học kỹ thuật và công nghệ thông tin như hiện nay thì ngành lý thuyết đồ thị ngày càng có nhiều ứng dụng trong cuộc sống.
Trên cơ sở đã học môn Lý thuyết đồ thị, chúng tôi đã nghiên cứu, và muốn tìm hiểu hơn nữa về những ứng dụng hữu ích, thực tế của bài toán tô màu đồ thị. Do đó, nhóm đã chọn đề tài: “Bài toán tô mầu đồ thị và ứng dụng”.
Nội dung đề tài gồm 3 chương:
Chương 1: Đại cương về đồ thị
Chương 2: Bài toán tô mầu đồ thị
Chương 3: Một số bài toán ứng dụng
Do thời gian có hạn và trình độ còn hạn chế nên chúng tôi chỉ đi vào nghiên cứu tìm hiểu thuật toán và giới thiệu một số ứng dụng của bài toán tô màu đồ thị.