Nhóm 6
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
1
2
TOÁN RỜI RẠC
ĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN
VỀ TÔ MÀU ĐỒ THỊ
Đỗ Văn Anh – KHMT3
3
ĐỒ 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?
Đỗ Văn Anh – KHMT3

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
2
R
1

R
21

r = e – v + 2

r: số miền

e: số cạnh

v: số đỉnh
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
8
ĐỒ 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
i
(i = 2,3, …, e)

G ≡ G

Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
9
ĐỒ 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
đều thuộc G
n


n+1
b
n+1
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
10
ĐỒ 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
(hoặc a
n+1

a
n+1
b
n+1
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
11
ĐỒ 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
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
12
ĐỒ 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)
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
14
ĐỒ THỊ PHẲNG

Công thức Euler

Hệ quả 2

Ví dụ: Chứng minh K
3,3
không phẳng.
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
15
ĐỒ 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


e
f
g
h
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
17
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.
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
18
Tô màu đồ thị

Bài toán


G

Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
19
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ăn Anh – KHMT3
Đỗ Văn Anh – KHMT3
20
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


Đị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)

V’ = V \ {v
n+1
}, E’ ⊂ E

G (V’, E’) ≡ K
n

v
n+1

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
Đỗ Văn Anh – KHMT3
Đỗ Văn Anh – KHMT3
24
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