TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
ĐỖ VĂN PHONG
TÔ MÀU ĐỒ THỊ
VÀ ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Toán ứng dụng
Hà Nội – Năm 2017
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
ĐỖ VĂN PHONG
TÔ MÀU ĐỒ THỊ
VÀ ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Toán ứng dụng
NGƯỜI HƯỚNG DẪN KHOA HỌC
Th.s PHẠM VĂN DUẨN
Hà Nội – Năm 2017
1
LỜI CẢM ƠN
Trước khi trình bày nội dung chính của khóa luận tốt nghiệp, tôi xin
bày tỏ lòng biết ơn sâu sắc tới Th.s Phạm Văn Duẩn người đã tận tình
hướng dẫn để tôi có thể hoàn thành khóa luận này.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô
trong Khoa Toán, Trường đại học sư phạm Hà Nội 2 đã dạy bảo tôi tận
tình trong suốt quá trình học tập tại khoa.
Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia
đình, bạn bè đã luôn bên em, động viên, giúp đỡ tôi trong suốt quá trình
học tập và thực hiện khóa luận tốt nghiệp.
Hà Nội, ngày 24 tháng 04 năm 2017
Sinh viên
ĐỖ VĂN PHONG
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả nghiên cứu trong khóa luận này là trung
thực và chưa hề được sử dụng để bảo vệ một học vị nào. Mọi sự giúp
đỡ cho việc thực hiện khóa luận này đã được cảm ơn và các thông tin
trích dẫn trong khóa luận đã được chỉ rõ nguồn ngốc một cách rõ ràng
và được phép công bố.Tôi hoàn toàn chịu trách nhiệm trước nhà trường
về sự cam đoan này.
Hà Nội, ngày 24 tháng 04 năm 2017
Sinh viên
ĐỖ VĂN PHONG
i
Mục lục
Lời mở đầu
1
1 KIẾN THỨC CHUẨN BỊ
3
1.1
1.2
Đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.1
Định nghĩa đồ thị . . . . . . . . . . . . . . . . .
3
1.1.2
Quan hệ kề nhau . . . . . . . . . . . . . . . . .
6
Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . .
9
1.2.1
Đồ thị phân đôi . . . . . . . . . . . . . . . . . .
9
1.2.2
Những đồ thị đơn đặc biệt . . . . . . . . . . . .
10
2 TÔ MÀU ĐỒ THỊ
2.1
2.2
2.3
12
Tô màu đỉnh . . . . . . . . . . . . . . . . . . . . . . .
12
2.1.1
Định nghĩa . . . . . . . . . . . . . . . . . . . .
12
2.1.2
Định lý . . . . . . . . . . . . . . . . . . . . . .
12
2.1.3
Ví dụ
. . . . . . . . . . . . . . . . . . . . . . .
21
Tô màu bản đồ . . . . . . . . . . . . . . . . . . . . . .
25
2.2.1
Định nghĩa . . . . . . . . . . . . . . . . . . . .
25
2.2.2
Định lý . . . . . . . . . . . . . . . . . . . . . .
26
2.2.3
Ví dụ
. . . . . . . . . . . . . . . . . . . . . . .
31
Đa thức tô màu . . . . . . . . . . . . . . . . . . . . . .
34
ii
Khóa luận tốt nghiệp Đại học
2.4
2.5
ĐỖ VĂN PHONG
2.3.1
Định nghĩa . . . . . . . . . . . . . . . . . . . .
34
2.3.2
Định lý . . . . . . . . . . . . . . . . . . . . . .
34
2.3.3
Ví dụ
. . . . . . . . . . . . . . . . . . . . . . .
37
Thuật toán tô màu Welsh-Powell . . . . . . . . . . . .
40
2.4.1
Định nghĩa . . . . . . . . . . . . . . . . . . . .
40
2.4.2
Ví dụ
41
. . . . . . . . . . . . . . . . . . . . . . .
Kết luận chương
. . . . . . . . . . . . . . . . . . . . .
3 MỘT SỐ ỨNG DỤNG CỦA TÔ MÀU ĐỒ THỊ
3.1
3.2
3.3
3.4
42
43
Bài toán xếp lịch thi . . . . . . . . . . . . . . . . . . .
43
3.1.1
Bài toán . . . . . . . . . . . . . . . . . . . . . .
43
3.1.2
Cách giải . . . . . . . . . . . . . . . . . . . . .
43
3.1.3
Ví dụ
. . . . . . . . . . . . . . . . . . . . . . .
44
Bài toán phân chia tần số . . . . . . . . . . . . . . . .
46
3.2.1
Bài toán . . . . . . . . . . . . . . . . . . . . . .
46
3.2.2
Cách giải . . . . . . . . . . . . . . . . . . . . .
46
3.2.3
Ví dụ
. . . . . . . . . . . . . . . . . . . . . . .
46
Bài toán soduku . . . . . . . . . . . . . . . . . . . . . .
49
3.3.1
Bài toán . . . . . . . . . . . . . . . . . . . . . .
49
3.3.2
Cách giải . . . . . . . . . . . . . . . . . . . . .
49
3.3.3
Ví dụ
50
. . . . . . . . . . . . . . . . . . . . . . .
Kết luận chương
. . . . . . . . . . . . . . . . . . . . .
iii
53
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Lời mở đầu
1.Lý do chọn đề tài
Khái niệm lý thuyết đò thị được khá 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 bài toán là một phương pháp 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.
Hiện nay, các tài liệu viết về lý thuyết đồ thị chưa được nhiều cũng
gây ra một chút khó khăn cho việc nghiên cứu tài liệu tham khảo.
Trong khi đó các tài liệu còn chưa đề cập nhiều đến ứng dụng của bài
toán tô màu.
Để hiểu rõ hơn về lý thuyết đồ thị và ứng dụng của nó trong việc
giải quyết một số bài toán thực tế bằng cách tô màu cho đồ thị, tôi
đã lựa chọn đề tài :"TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG".
2.Mục đích nghiên cứu
Nghiên cứu tô màu đồ thị và ứng dụng vào một số bài toán thực
tiễn
3. Đối tượng và phạm vi nghiên cứu
-Đối tượng nghiên cứu: Đồ thị và các ứng dụng của đồ thị
1
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
-Phạm vi nghiên cứu: Tô màu đồ thị và một số ứng dụng tô màu
đồ thị
4. Phương pháp nghiên cứu
-Phương pháp nghiên cứu tài liệu.
-Phương pháp đánh giá.
-phương pháp hệ thống hóa một số ứng dụng của đồ thị.
5. Cấu trúc khóa luận
Nội dung khóa luận bao gồm 3 chương:
-Chương 1. Kiến thức chuẩn bị
-Chương 2. Tô màu đồ thị
-Chương 3. Một số ứng dụng tô màu đồ thị
Do thời gian thực hiện đề tài không nhiều, kiến thức còn hạn chế
nên khóa luận không thể tránh những sai sót. Tôi mong nhận được
sự đóng góp ý kiến ý kiến phản biện của quý thầy cô và các bạn. Xin
chân thành cảm ơn!
2
Chương 1
KIẾN THỨC CHUẨN BỊ
Nhắc lại một số khái niệm, tính chất cơ bản của đồ thị có được sử
dụng trong quá trình tìm hiểu chương 2 và chương 3.
1.1
1.1.1
Đồ thị
Định nghĩa đồ thị
Định nghĩa 1.1. Đồ 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 đó, ký hiệu là G = (V, E) trong đó V được gọi là
tập đỉnh và E được gọi là tập cạnh. Có thể coi E là tập tất cả các
cặp (u, v) với u và v là hai đỉnh của V .
Một số hình ảnh của đồ thị.
Hình 1.1: Ví dụ về mô hình đồ thị.
3
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Định nghĩa 1.2. Đồ thị vô hướng là tập hữu hạn G gồm hai tập hữu
hạn con V, E (ký hiệu G = {V, E}) với V là tập các đỉnh của đồ thị,
E là tập các cặp đỉnh (i, j) mà các cặp này không tính đến thứ tự
(nghĩa là trình tự (i, j) cũng giống như trình tự (i, j)). Cặp (i, j) gọi
là cạnh của đồ thị.
Ví dụ 1.1.1. Hình 1.2 là biểu diễn hình học của đồ thị vô hướng.
Hình 1.2: Đồ thi vô hướng
Định nghĩa 1.3. Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó
trên một mặt phẳng sao cho các cạnh của nó không cắt nhau tại một
điểm khác đỉnh. Hình vẽ đó gọi là một biểu diễn phẳng của đồ thị.
Ví dụ 1.1.2. Một số hình ảnh về đồ thị phẳng Hình 1.3
Hình 1.3: Đồ thị phẳng
4
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Định lý 1.1. (Bất đẳng thức cạnh đỉnh).Trong một đồ thị phẳng liên
thông G = (V, E) bất kỳ với chu vi nhỏ nhất g thỏa mãn 3 ≤ g < ∞
ta luôn có
|E| ≤
g
(|V | − 2)
g−2
.
Chứng minh. Giả sử G = (V, E) là đồ thị phẳng liên thông thỏa mãn
của định lý. Ta cũng giả sử rằng G có E = {e1 , e2 , ..., et } và các miền
f1 , f2 , ..., fl . Ta xác định ma trận X = (xij )txl cỡ t x l như sau:
xij =
1
nếu ei là một cạnh biên trên miền fj ,
0
trong trường hợp ngược lại .
Ma trận X xác định như trên gọi là ma trận cạnh miền của đồ thị
phẳng G. Vì mỗi cạnh của G là một cạnh trên biên của nhiều nhất
hai miền, nên trong mỗi hàng của ma trận X có nhiều nhất là hai số
1. Mặt khác, các cạnh ở trên biên của mỗi miền tạo thành một chu
trình trong G. Do đó, mỗi cột của ma trận X có ít nhất g số 1, ở đây
g là chu vi nhỏ nhất của G. Vì vậy, nếu s là số các số 1 có trong X,
thì ta có các bất đẳng thức sau đây:
gl ≤ s ≤ 2t
Mặt khác, vì G liên thông nên l = t − |V | + 2. Sau khi thay thế vào
5
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
các bất đẳng thức trên ta được
gl = gt − g |V | + 2g ≤ 2t
⇔ t(g − 2) ≤ g(|V | − 2)
⇔ |E| ≤
g
g−2 (|V
| − 2)
do đó bất đẳng thức được chứng minh.
1.1.2
Quan hệ kề nhau
Định nghĩa 1.4. Hai đỉnh u và v trong một đồ thị vô hướng G được
gọi là liền kề nếu u, v là một cạnh của G. Nếu e = {u, v} thì e gọi là
cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối
các đỉnh u và v. Các đỉnh u và v gọi là điểm đầu mút của cạnh {u, v}.
Ví dụ 1.1.3. Trên hình 1.2 {a, b} , {b, c} , {c, d} , {d, a} , {a, c} gọi là
hai đỉnh kề nhau.
Định nghĩa 1.5. Bậc của một đỉnh trong đồ thị vô hướng là số các
cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần
cho bậc của nó. Người ta ký hiệu bậc của đỉnh v là deg(v).
Ví dụ 1.1.4. Bậc của các đỉnh trong các đồ thị G và H trên hình 1.4
là bao nhiêu?
Hình 1.4: Đồ thị vô hướng G và H.
6
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Lời giải: Trong G, deg(a)=2, deg(b)=deg(c)=deg(f)=4, deg(d)=1,
deg(e)=3 và deg(g)=0. Trong H, deg(a)=4, deg(b)=deg(e)=6, deg(c)=1
và deg(d)=5.
Định nghĩa 1.6. Đường đi từ i đến j trên đồ thị là một dãy các đỉnh
mà mỗi đỉnh thuộc dãy (trừ đỉnh cuối) luôn kề với đỉnh đứng ngay
sau nó: i = x1 , x2 , x3 , ..., xk , xk+1 , ..., xn = j với mọi k = 1, 2, 3, ..., n − 1
x1 = i gọi là đỉnh đầu; xn = j gọi là đỉnh cuối của đường đi p.
Ví dụ 1.1.5. Trên đồ thị Hình 1.4 có {a, b, e, f, c, d} , {a, b, c, d} là hai
đường đi của đồ thị G.
Định nghĩa 1.7. Chu trình là đường đi có đỉnh đầu và đỉnh cuối
trùng nhau.
Ví dụ 1.1.6. Trên Hình 1.2 có các chu trình là {a, b, c, d, a} , {a, b, c, a} , {a, c, d, a}.
Định nghĩa 1.8. Đồ thị vô hướng G = {V, E} được gọi là đồ thị liên
thông nếu luôn tìm được đường đi giũa hai đỉnh bất kỳ của nó.
Ví dụ 1.1.7. Đồ thị liên thông G Hình1.5
Hình 1.5: Đồ thị liên thông G
Định nghĩa 1.9. Một cạnh e = (i, j) thuộc một đồ thị G {V, E} được
gọi là cầu của đồ thị nếu sau khi xóa bỏ cạnh đó thì số thành phần
liên thông của đồ thị tăng lên.
7
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Ví dụ 1.1.8. Từ hình 1.5 sau khi ta xóa đi cạnh {b, f } thì sô miền
liên thông tăng lên một Hình 1.6
Hình 1.6: Cầu của đồ thị G
Định nghĩa 1.10. Đường đi Euler là đường đi qua tất cả các cạnh
mỗi cạnh đúng một lần.Chu trình Euler là đường đi Euler có điểm
đầu điểm cuối trùng nhau.
Định nghĩa 1.11. Đồ thị Euler vô hướng là đồ thị chứa một chu
trình Euler.
Ví dụ 1.1.9. Hình1.7 là đồ thị Euler
Hình 1.7: Đồ thị vô hướng G.
Vì có chu trình là a-e-c-d-e-b-a (tồn tại đường đi qua tất cả các cạnh
chỉ một lần với điểm đầu trùng điểm cuối).
8
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Định nghĩa 1.12. Cho hai đồ thị G = (V, E) và G0 = (V 0 , E 0 ). Ta
nói rằng G đẳng cấu G0 , ký hiệu G ∼
= G0 , nếu tồn tại một song ánh
f : V → V 0 sao cho:uv là cạnh của G ⇔ f (u)f (v) là cạnh của G0
Ví dụ 1.1.10. Hình 1.8 cho ta thấy sự đẳng cấu giữa hai đồ thị G và
H
Hình 1.8: Đồ thị đẳng cấu giữa G và H.
1.2
1.2.1
Một số dạng đồ thị đặc biệt
Đồ thị phân đôi
Định nghĩa 1.13. Một đồ thị G được gọi là một đồ thị phân đôi nếu
tập các đỉnh V có thể phân làm hai tập con không rỗng, rời nhau V1
và V2 sao cho mỗi cạnh của đồ thị nối một đỉnh của V1 với một đỉnh
của V2 .
Ví dụ 1.2.1. C6 là phân đôi như chỉ ra trên hình 1.9, vì các đỉnh của
nó có thể chia làm hai tập con V1 = {v1 , v3 , v5 } và V2 = {v2 , v4 , v6 } và
mỗi cạnh của C6 nối một đỉnh của V1 với một đỉnh của V2 .
9
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Hình 1.9: Minh họa C6 đồ thị phân đôi.
1.2.2
Những đồ thị đơn đặc biệt
Định nghĩa 1.14. Một biểu đồ khối là một đồ thị trong đó tất cả
các đỉnh đều có bậc ba.
Ví dụ 1.2.2. Tất cả các đồ thị Petersen là một đồ thị khối (Hình
1.10).
Hình 1.10: Đồ thị Petersen
Định nghĩa 1.15. Đồ thị đầy đủ n đỉnh, ký hiệu là Kn , là đồ thị đơn
vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối. Đồ thị Kn
có tất cả
n(n−1)
2
cạnh. Nó là đồ thị đơn có nhiều cạnh nhất, đồng thời
là đồ thị chính quy bậc n − 1.
Ví dụ 1.2.3. Sau đây là danh sách và hình vẽ các đồ thị đầy đủ với
số đỉnh từ 1 đến 8 cùng với số cạnh của chúng (Hình 1.11).
Định nghĩa 1.16. Đồ thị vòng là đồ thị có n đỉnh v1 , v2 , . . . ,vn và
n cạnh (v1 , v2 ),(v2 , v3 ), . . . ,(vn−1 , vn ), ký hiệu bởi Cn .
10
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Hình 1.11: Các đồ thị Kn , 1 ≤ n ≤ 8
Ví dụ 1.2.4. Sau đây là hình biểu diễn của đồ thị C3 , C4 , C5 , C6
(Hình 1.12)
Hình 1.12: Các chu trình Cn , 3 ≤ n ≤ 6
11
Chương 2
TÔ MÀU ĐỒ THỊ
2.1
Tô màu đỉnh
2.1.1
Định nghĩa
Định nghĩa 2.1. Một tô màu đỉnh của một đồ thị, mà ta sẽ đơn giản
gọi là một tô màu, là một phép gán các màu cho các đỉnh sao cho hai
đỉnh kề nhau bất kỳ có màu khác nhau.
Định nghĩa 2.2. Sắc số cảu một đồ thi G, ký hệu χ(G), là số tự
nhiên k nhỏ nhất để G có một k -tô màu. Đồ thị G được gọi là đồ thị
k -tô màu. Đồ thị G được gọi là đồ thị k-tô màu được nếu χ(G) ≤ k
và được gọi là k-sắc nếu χ(G) = k.
2.1.2
Định lý
Định lý 2.1. Nếu G là đồ thị đơn giản có đỉnh bậc lớn nhất là 4 thì
G là 4+1-tô màu được.
Chứng minh. Chúng ta đi chứng minh định lý bằng phép qui nạp trên
12
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
số đỉnh của G. Hiển nhiên nếu G là đồ thị một đỉnh thì G có bậc lớn
nhất là 4=0, nên đồ thị G lúc này là 4+1-tô màu được hay là 1-tô
màu được. Bây giờ chúng ta giả sử G là một đồ thị đơn giản với số
đỉnh là n và có bậc lớn nhất là 4 thì G là 4+1-tô màu được. Chứng
minh, nếu xóa đi đỉnh v bất kỳ và các cạnh kề với nó. Khi đó đồ thị G
còn lại n-1 đỉnh và đỉnh có bậc lớn nhất là 4, thì đồ thị G là 4+1-tô
màu được. Hình 2.1. Bằng phép qui nạp của chúng ta giả thiết, đồ thị
G là 4+1-tô màu được. Với 4+1 màu thì G đạt được bằng màu của
v và các màu khác nhau từ các đỉnh kề với v.
Hình 2.1: Đồ thị G
Định lý 2.2. (Konig, 1936.)Giả sử G = (V.E) là một đồ thị bấy kỳ.
Khi đó các khẳng định sau đây là tương đương nhau:
1. G là đồ thị 2-sắc;
2. G là đồ thị 2-phần khác đồ thị rỗng;
3. G là đồ thị khác rỗng và mọi chu trình trong G đều có độ dài chẵn.
13
Khóa luận tốt nghiệp Đại học
ĐỖ VĂN PHONG
Chứng minh. (a). (1)⇒(2): Giả sử G là đồ thị 2-sắc. Ta cũng giả sử
rằng V1 và V2 là hai lớp đỉnh đồng màu của G trong 2-tô màu nào đó.
Khi đó dễ thấy rằng G là đồ thị 2-phần với các phần là V1 và V2 . Vì
G là 2-sắc, nên G cũng là đồ thị không rỗng.
(b). (2)⇒(1): Giả sử G là đồ thị 2-phần khác đồ thị rỗng. Ta cũng
giả sử rằng V1 và V2 là các phần của G. Ta tô các đỉnh của V1 bằng
một màu và tô các đỉnh của V2 bằng một màu khác. Khi đó ta nhận
được 2-tô màu của G vì G là đồ thị 2-phần. Mặt khác, G không có
1-tô màu vì nó là đồ thị khác rỗng. Vậy χ(G) = 2 và G là đồ thị 2-sắc.
(c). (2)⇒(3):Giả sử G = (V, E) là đồ thị 2-phần khác đồ thị rỗng
với các phần là V1 và V2 . Ta cũng giả sử rằng rằng C = v1 v2 v3 . . .
vn v1 là một chu trình bất kỳ trong G. Nếu v1 ∈ V1 , thì v2 ∈ V2 , v3 ∈
V1 , v4 ∈ V2 , . . . , tức là những đỉnh với chỉ số dưới lẻ là đỉnh thuộc
V1 , còn những đỉnh với chỉ số dưới chẵn là đỉnh thuộc V2 . Vì thế, độ
dài của chu trình C phải là chẵn.
(d). (3)⇒(2): giả sử G =(V, E) là đồ thị khác rỗng trong đó mọi
chu trình đều có độ dài chẵn. Trước hết ta xét trường hợp G là liên
thông. Ta cố định một đỉnh bất kỳ v1 ∈ V. Với mỗi đỉnh v ∈ V, ta
gọi khoảng cách từ đỉnh v tới đỉnh v1 là độ dài của đường ngắn nhất
trong G từ v tới v1 . Ký hiệu bằng V1 tập tất cả các đỉnh của G, mà
có khoảng cách tới v1 là chẵn. Đặt V2 = V\V1 .
Giả sử tồn tại cạnh trong G nối hai đỉnh u,v ∈ V1 . Gọi Pu và Pv là
14
- Xem thêm -