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 − 6.

Chứng minh:

Trong một đồ thị phẳng

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

Công thức Euler

Hệ quả 3

Cho G là một đơn đồ thị phẳng liên thông với e cạnh
và v đỉnh. Khi đó V có ít nhất đỉnh w thỏa d(w) ≤ 5

Định lý 2

Cho G là một đơn đồ thị phẳng với e cạnh, v đỉnh và
có k thành phần liên thông. Gọi r là số miền (regions)
trong biểu diễn phẳng của G. Khi đó:

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

Xác định số màu tối
thiểu cần có để tô màu
một bản đồ sao cho hai
miền kề nhau có màu
khác nhau.
18
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 đồ

Mô hình hóa bài toán

Đỉnh: các miền có trên
bản đồ

Đị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).
20
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

Định nghĩa

Ví dụ

Tìm sắc số của đồ thị sau:

Số màu cần tô: 4

v
1
v
3
v
6
v

Quy nạp theo n

n = 1: Thỏa

Giả sử χ(K
n
) = n

Xét K
n+1
= (V, E)

V’ = V \ {v
n+1
}, E’ ⊂ E

G (V’, E’) ≡ K
n

v
n+1
v
i
∈ E
⇒ χ(K
n+1
) = n + 1
22
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị

C
D
E
F
24
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ý 3

Một đơn đồ thị G = (V, E) có thể tô bằng 2 màu khi và
chỉ khi nó không có chu trình độ dài lẻ

Chứng minh

Nhận xét

χ(C
n
) = 2 nếu n chẵn (n≥ 3)

χ(C
n
) = 3 nếu n lẻ (n≥ 3)
25
Chương 2. Đồ thị phẳng và bài toán tô màu đồ thị
Tô màu đồ thị
