1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
NGUYỄN THỊ VIỆT THẢO
BÀI TOÁN TÔ MÀU VÀ
ỨNG DỤNG GIẢI TOÁN SƠ CẤP
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60.46.40
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC
Đà
Nẵng - năm 2011
2
Công trình ñược hoàn thành tại
TRƯỜNG ĐẠI HỌC SƯ PHẠM, ĐẠI HỌC ĐÀ NẴNG
Người hướng dẫn khoa học: PGS. TSKH Trần Quốc Chiến
Phản biện 1: TS. Cao Văn Nuôi
Phản biện 2: PGS. TS. Huỳnh Thế Phùng
Luận văn sẽ ñược bảo vệ trước Hội ñồng chấm Luận văn
tốt nghiệp Thạc sĩ khoa học họp tại Đại học Đà Nẵng vào
ngày 26/11/2011
Có thể tìm hiểu luận văn tại:
- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng
- Thư viện trường ĐH Sư phạm, Đại học Đà Nẵng
3
MỞ ĐẦU
1. Lý do chọn ñề tài
Khái niệm lý thuyết ñồ thị ñược nhiều nhà khoa học ñộc lập
nghiên cứu và có nhiều ñóng góp trong lĩnh vực toán học ứng
dụng. Sử dụng bài toán tô màu ñể giải toán là một phương pháp
khá hay trong lý thuyết ñồ thị. Phương pháp này không ñòi hỏi
nhiều về kiến thức 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ột 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.
Mong muốn của tác giả luận văn là có thể cung cấp cho
người ñọc một cái nhìn tổng quan nhưng cũng khá chi tiết về việc
sử dụng tô màu như một nghệ thuật giải toán, hy vọng nó sẽ giúp
ích phần nào cho việc bồi dưỡng học sinh chuyên ở các trường
THPT, phát triển tư duy cho học sinh, mở ra một hướng nghiên
cứu mới cho những ai quan tâm.
2. Mục ñích nghiên cứu
Ứng dụng lí thuyết ñồ thị nói chung và bài toán tô màu ñồ thị
nói riêng ñể giải các bài toán không mẫu mực, các bài toán
thường gặp trong thực tế và một vài bài toán trong các kì thi Toán
quốc tế.
3. Đối tượng và phạm vi nghiên cứu
- Nghiên cứu tổng quan về lí thuyết ñồ thị, tô màu ñồ thị.
- Nghiên cứu lớp các bài toán ứng dụng tô màu ñồ thị.
4. Phương pháp nghiên cứu
+ Nghiên cứu lí thuyết
Dựa vào các giáo trình ñã ñược học, các tài liệu liên quan
ñến lí thuyết ñồ thị và tô màu ñồ thị.
+ Nghiên cứu thực tiễn
Nghiên cứu các bài toán trong các giáo trình và tài liệu
tham khảo.
5. Chọn tên ñề tài Bài toán tô màu và ứng dụng giải toán sơ cấp.
4
6. Cấu trúc luận văn Gồm ba chương
Chương 1: Kiến thức cơ sở
Chương 2: Bài toán tô màu ñồ thị
Chương 3: Ứng dụng
CHƯƠNG 1. KIẾN THỨC CƠ SỞ
1.1 CÁC KHÁI NIỆM CƠ BẢN
1.1.1 Các ñịnh nghĩa
1.1.2 Bậc của ñồ thị
1.1.3 Các ñơn ñồ thị ñặc biệt
1.1.4 Đồ thị ñường
1.2 ĐƯỜNG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG
1.2.1 Các ñịnh nghĩa
1.2.2 Các bài toán về ñường ñi
1.2.3 Một số ñịnh lí
1.3 ĐỒ THỊ PHẲNG
1.3.1 Bài toán mở ñầu
1.3.2 Đồ thị phẳng
1.3.3 Công thức Euler
1.3.4 Định lí Kuratowski
CHƯƠNG 2. BÀI TOÁN TÔ MÀU ĐỒ THỊ
2.1 GIỚI THIỆU
2.2 TÔ MÀU ĐỈNH
2.2.1 Đồ thị ñối ngẫu
2.2.2 Các khái niệm cơ bản
Định nghĩa 2.1 Tô màu ñỉnh một ñơn ñồ thị là sự gán màu cho
các ñỉnh của nó sao cho không có hai ñỉnh kề nhau ñược gán cùng
một màu.
Định nghĩa 2.2 Sắc số của ñồ thị G, ký hiệu là χ(G), là số màu tối
thiểu cần thiết ñể tô màu các ñỉnh của ñồ thị (mỗi ñỉnh một màu),
sao cho hai ñỉnh kề nhau tùy ý ñược tô bằng hai màu khác nhau.
5
2.2.3 Một số ñịnh lí
Định lí 2.1 Một chu trình ñộ dài lẻ luôn có sắc số bằng 3.
Định lí 2.2 (Định lí Konig) Một ñơn ñồ thị có thể tô bằng hai màu
khi và chỉ khi nó không có chu trình ñộ dài lẻ.
Hệ quả 2.1 Tất cả các chu trình ñộ dài chẵn ñều có sắc số bằng 2.
Định lí 2.3 Đồ thị ñầy ñủ K
n
với n ñỉnh luôn luôn có sắc số bằng n.
Định lí 2.4 Với mỗi số nguyên dương n, tồn tại một ñồ thị không
chứa K
3
và có sắc số bằng n.
Định lí 2.5 Nếu ñồ thị G chứa ñồ thị con ñẳng cấu với ñồ thị ñầy
ñủ K
n
thì λ(G)≥n.
Định lí 2.6 χ(G)
P
≤
∆(G) + 1 với mọi ñồ thị G, trong ñó ∆(G) là
bậc ñỉnh lớn nhất của G (ñẳng thức xảy ra khi G = K
n
hoặc G là
chu trình ñộ dài lẻ).
Định lí 2.7 (Brooks) Cho G là ñơn ñồ thị n ñỉnh, liên thông khác
K
n
và không phải chu trình ñộ dài lẻ. Khi ñó χ (G)
≤
∆(G).
2.3 THUẬT TOÁN TÔ MÀU ĐỈNH
i) Lập danh sách các ñỉnh ñồ thị.
E
’
:=
[
]
1 2
, ,...,
n
v v v
theo thứ tự bậc giảm dần:
1 2
n
d v d v d v
≥ ≥ ≥
.
Đặt i:=1
ii) Tô màu i cho ñỉnh ñầu tiên trong danh sách. Duyệt lần
lượt các ñỉnh tiếp theo và tô màu i cho ñỉnh không kề ñỉnh ñã
ñược tô màu i.
iii) Nếu tất cả các ñỉnh ñã ñược tô màu thì kết thúc: Đồ thị
ñã ñược tô màu bằng i màu. Ngược lại sang bước iv).
iv) Loại khỏi E’ các ñỉnh ñã tô màu, ñặt i:=i+1, và quay lại
bước ii).
2.4 TÔ MÀU ĐỒ THỊ PHẲNG
2.4.1 Một số ñịnh lí về sắc số của ñồ thị phẳng
Định lí 2.8 Mọi bản ñồ tạo bởi các ñường thẳng trên mặt phẳng
có thể tô bằng hai màu.
Định lí 2.9 Điều kiện cần và ñủ ñể bản ñồ có thể tô bằng hai màu
là mọi ñỉnh của ñồ thị phẳng tương ứng có bậc chẵn lớn hơn hoặc
bằng 2.