1
TOÁN RỜI RẠC
ỨNG DỤNG TRONG TIN HỌC
ĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN
VỀ TÔ MÀU ĐỒ THỊ
2
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Bài toán

Tìm cách làm cho các con
đường đi dẫn từ 3 ngôi nhà
tới 3 cái giếng sao cho không
có 2 con đường nào cắt
nhau?

Mô hình bài toán

Đỉnh: các gia đình và
giếng nước

Cạnh: đường đi từ nhà
đến các giếng

Có thể vẽ đồ thị mà không
có 2 cạnh nào cắt nhau?
3
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG



Đồ thị phẳng

Ví dụ

Chứng minh K
3,3
không phẳng.
v
1
v
2
v
3
v
4
v
5
v
6

v
1
v
2
v
4
v
5
R

miền bằng nhau

Định lý 1

Trong đơn đồ thị phẳng, liên thông thì
r = e – v + 2

r: số miền

e: số cạnh

v: số đỉnh
8
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Chứng minh

Xây dựng dãy đồ thị con của G

G1 ≡ e
1

G
i
= G
i-1
∪ e

n+1
, b
n+1
)
9
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Chứng minh

Xét đồ thị phẳng G
n+1


G
n+1
= G
n
∪ (a
n+1
, b
n+1
)

Nếu a
n+1
, b
n+1

n+1
+ 2.
a
n+1
b
n+1
10
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Chứng minh

Xét đồ thị phẳng G
n+1


G
n+1
= G
n
∪ (a
n+1
, b
n+1
)

Nếu b
n+1

n+1
+ 2.
a
n+1
b
n+1
11
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Ví dụ

Tính số miền trong một đơn đồ thị phẳng liên
thông có 8 đỉnh và mỗi đỉnh đều có bậc 3
12
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Hệ quả 1

Cho G là một đơn đồ thị phẳng liên thông với e
cạnh và v đỉnh; v
≥
3. Khi đó: e
≤
3v

−
4.

Chứng minh:

Trong một đồ thị phẳng không có chu trình độ dài 3

Mỗi miền được bao ít nhất 4 cạnh

Mỗi cạnh nằm trên nhiều nhất 2 miền
⇒ 4r ≤ 2e (*)

Theo định lý Euler: r = e – v + 2

Thay vào (*) ta có: e ≤ 2v − 4 (đpcm)
14
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG

Công thức Euler

Hệ quả 2

Ví dụ: Chứng minh K
3,3
không phẳng.
15
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
ĐỒ THỊ PHẲNG



Ví dụ:

Chứng minh các đồ thị sau không phẳng.
a
b c
d
e
f
a
b
c
d
e
f
g
h
17
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

Bài toán

Tô màu một bản đồ

2 miền có chung biên
giới được tô bằng 2
màu tùy ý, miễn là
khác nhau


C
D
E
F
G
A
B
C
D
E
F
G

19
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

Định nghĩa

Tô màu một đơn đồ thị là việc gán màu cho các
đỉnh của nó sao cho hai đỉnh liền kề có màu khác
nhau.

Sắc số (Chromatic number)

Số màu tối thiểu cần thiết để tô màu G.

Ký hiệu:
χ
(G).

v
5

v
6
v
7
21
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

Định lý

Mọi đơn đồ thị đầy đủ đều có: χ(K
n
) = n.

Chứng minh

Quy nạp theo n

n = 1: Thỏa

Giả sử χ(K
n
) = n

Xét K
n+1
= (V, E)

Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

Một số định lý về tô màu đồ thị

Định lý 2

Nếu G có chứa một đồ thị con đẳng cấu với K
n
thì
χ
(G)
≥
n

Ví dụ: Tìm sắc số của đồ thị sau

Chú ý

Nếu G’ ⊂ G thì χ(G) ≥ χ(G’)
A
B
C
D
E
F
24
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị


Định lý 4 (Định lý 4 màu)

Mọi đồ thị phẳng đều có sắc số không lớn hơn 4

Định lý được chứng minh bởi Appel và Haken

Đây là định lý đầu tiên được chứng minh với sự trợ giúp
của máy tính

Ta có thể chứng minh định lý yếu hơn:

Mọi đồ thị phẳng đều có sắc số không lớn hơn 5