Đồ Án Tô màu đồ thị

LỜI NÓI ĐẦU

Cấu trúc dữ liệu là một trong những môn học chuyên ngành cơ bản của khoa công nghệ thông tin. Nó cung cấp cho chúng em nhiều kiến thức quan trọng về thuật toán cũng như về tổ chức dữ liệu. Học tốt môn học này sẽ tạo nền tảng cho việc học những môn chuyên ngành sau này. Trong học kì 4 chúng em đã được thầy giáo Phan Chí Tùng giảng dạy về môn học này. Chúng em xin cảm ơn thầy, cũng như các thầy cô giáo trong khoa đã giảng dạy chúng em trong những học kì vừa qua.
Đề tài đồ án cấu trúc dữ liệu mà chúng em được giao để thực hiện đó là đề tài số 120, bài toán “ TÔ MÀU ĐỒ THỊ “ . Đồ án này là đồ án đầu tiên mà chúng em thực hiện trong quá trình học tại khoa Công nghệ thông tin – Đại học Bách khoa Đà Nẵng, do đó không tránh khỏi những sai sót mong được sự chỉ dạy và giúp đỡ của các thầy cô để chương trình hoàn thiện hơn.

2. Đề bài :
Cho một đồ thị vô hướng N đỉnh, mỗi đỉnh được nối với 1 số đỉnh khác. Bài toán đặt ra là: Hãy tô màu các đỉnh sao cho không có hai đỉnh nào có 2 màu giống nhau mà lại nối trực tiếp với nhau với số màu cần tô là ít nhất.


MỤC LỤC
LỜI NÓI ĐẦU 1
BÀI TOÁN TÔ MÀU ĐỒ THỊ 2
I. Giới thiệu : 2
1. Lý thuyết đồ thị 2
2. Đề bài : 2
II. Thuật toán 3
1. Mô tả thuật toán 3
2. Ví dụ áp dụng thuật toán 3
3. Sơ đồ khối: 4
CẤU TRÚC DỮ LIỆU 5
I. Tổ chức lưu trữ đỉnh của đồ thị 5
II. Tổ chức lưu trữ đồ thị 5
CHƯƠNG TRÌNH 6
KẾT QUẢ 7
KẾT LUẬN 9
I. Kết quả đạt được : 9
II. Những điều chưa đạt được : 9
PHỤ LỤC 10
I. Bài toán liên quan 10
Định lý bốn màu (four-color theorem) 10
II. Một số thuật toán tô màu đồ thị khác : 10
1. Large dergree first - fill from top 10
2. Thuật toán tô màu theo thứ tự bậc lớn nhất (LDO: Largest Degree Ordering) 10
3. Thuật toán tô màu theo thứ tự độ bão hoà (SDO: Saturation Degree Ordering) cải tiến: 10
III. Tập tin program.cpp 11
IV. Tập tin LINE.H 20
MỤC LỤC 21