Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Tô màu đỉnh của đồ thị
Nội dung xem thử
Mô tả chi tiết
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN
TRẦN THỊ MAI THẢO
TÔ MÀU ĐỈNH CỦA ĐỒ THỊ
LUẬN VĂN THẠC SĨ PHƯƠNG PHÁP TOÁN SƠ CẤP
Bình Định - 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN
TRẦN THỊ MAI THẢO
TÔ MÀU ĐỈNH CỦA ĐỒ THỊ
Chuyên ngành : Phương pháp toán sơ cấp
Mã số : 8460113
Người hướng dẫn: TS. TRẦN ĐÌNH LƯƠNG
i
Lời cam đoan
Tôi xin cam đoan mọi kết quả của đề tài “Tô màu đỉnh của đồ thị” là
công trình nghiên cứu của tôi dưới sự hướng dẫn của TS. Trần Đình Lương và
chưa từng được công bố trong bất cứ công trình khoa học nào khác cho tới thời
điểm này.
Các nội dung và kết quả sử dụng trong luận văn đều có trích dẫn và chú thích
nguồn gốc. Nếu có điều gì gian lận, tôi xin chịu trách nhiệm về luận văn của
mình.
Quy Nhơn, ngày 22 tháng 7 năm 2021
Học viên thực hiện đề tài
Trần Thị Mai Thảo
ii
Mục lục
Mở đầu 1
1 Sắc số của đồ thị 4
1.1 Một số kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Sắc số của đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Thuật toán tô màu đỉnh đồ thị . . . . . . . . . . . . . . . . . . . . 14
2 Đa thức màu của đồ thị 23
2.1 Một số tính chất của đa thức màu của đồ thị . . . . . . . . . . . . 23
2.2 Đa thức màu của một số họ đồ thị . . . . . . . . . . . . . . . . . . 27
3 Một số bài toán ứng dụng 38
3.1 Bài toán điều khiển đèn tín hiệu giao thông . . . . . . . . . . . . . 38
3.2 Bài toán lập lịch thi . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Bài toán lập thời khóa biểu . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Bài toán phân chia tần số . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Bài toán Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Kết luận 57
Danh mục tài liệu tham khảo 57
iii
Quyết định 59
iv
Danh mục các kí hiệu
V (G) Tập đỉnh của đồ thị G
E(G) Tập cạnh của đồ thị G
δ(G) Bậc bé nhất của đồ thị G
∆(G) Bậc lớn nhất của đồ thị G
degGv Bậc của đỉnh v của đồ thị G
Pn Đồ thị đường
Kn Đồ thị đầy đủ
Cn Đồ thị chu trình
Wn Đồ thị bánh xe
Km,n Đồ thị hai nhánh
Tn Đồ thị cây