Giáo trình Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh Đức
Đồ thị phẳng
Trần Vĩnh Đức
HUST
Ngày 1 tháng 3 năm 2016
1 / 36
Tài liệu tham khảo
▶
Eric Lehman, F Thomson Leighton & Albert R Meyer,
▶
▶
K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch
Tiếng Việt)
Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà
Nội, 2004.
2 / 36
Giới thiệu
3 / 36
Định nghĩa
Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó trên mặt phẳng
mà không có cạnh nào cắt nhau. Hình vẽ như thế gọi là một biểu
diễn phẳng của đồ thị.
4 / 36
Ví dụ
5 / 36
Ví dụ
Đồ thị K3,3
:
v1
v2
v3
v4
v5
v6
không phẳng vì
v1
v5
v1
v5
R21
R2
R1
R1
v3
R22
v4
v2
v4
v2
6 / 36
Euler chứng minh rằng mọi biểu diễn phẳng của một đồ thị đều
chia mặt phẳng thành cùng số miền như nhau.
R4
R6
R2
R3
R1
R5
7 / 36
Định lý (Công thức Euler)
Cho G là một đồ thị phẳng liên thông với e cạnh và v đỉnh. Gọi r
là số miền trong biểu diễn phẳng của G. Khi đó
r = e − v + 2.
8 / 36
Ví dụ
Xét một đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc
3. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu
miền?
▶
Tổng bậc bằng 3v = 3 × 20 = 60
▶
Số cạnh e = 30
▶
Theo công thức Euler
r = e − v + 2 = 30 − 20 + 2 = 12
9 / 36
Chứng minh công thức Euler
▶
Ta chứng minh bằng quy nạp theo số miền r.
Nếu r = 1 thì đồ thị không có chu trình. Tại sao?
Vậy e = v − 1. ꢀ
Giả sử định lý đúng với r > 1.
▶
▶
▶
10 / 36
Chứng minh công thức Euler
▶
Vì r > 1, nên đồ thị có chu trình.
▶
Giả sử {u, v} là cạnh của một chu trình nào đó.
▶
Vậy {u, v} là biên của hai miền S và T. Tại sao?
▶
Xóa cạnh {u, v} làm nhập hai miền S và T làm một, còn các
miền khác giữ nguyên.
▶
Đồ thị mới thu được có e − 1 cạnh và r − 1 miền.
Theo giả thiết quy nạp:
▶
r − 1 = e − 1 − v + 2
▶
Ta được r = e − v + 2. ꢀ
11 / 36
Hệ quả
Nếu G là một đồ thị phẳng liên thông với e cạnh và v đỉnh thỏa
mãn v ≥ 3. Vậy thì e ≤ 3v − 6.
c
7
▶
Bậc của một miền là số
cạnh trên biên của miền đó.
b
d
3
R1
▶
▶
Bậc của mỗi miền ít nhất
a
R2
phải bằng 3.
g
6
e
Tổng bậc các miền bằng bao
nhiêu cạnh?
R3
f
12 / 36
Chứng minh.
▶
Tổng bậc các miền
∑
deg(R) = 2e ≥ 3r
R
Vậy ta có 2e/3 ≥ r.
▶
▶
Theo công thức Euler
r = e − v + 2 ≤ 2e/3.
Kết luận e ≤ 3v − 6.
13 / 36
Bài tập
▶
Dùng hệ quả trước, hãy chỉ ra rằng đồ thị K5 không phẳng.
a
e
b
d
c
14 / 36
Hệ quả
Nếu G là một đồ thị phẳng liên thông thì G có một đỉnh bậc
không vượt quá 5.
Chứng minh.
Dùng hệ quả trước & Định lý bắt tay.
15 / 36
Hệ quả
Nếu một đồ thị phẳng liên thông có e cạnh, v đỉnh trong đó v ≥ 3
và không có chu trình độ dài 3 thì e ≤ 2v − 4.
Chứng minh.
▶
Nếu không có chu trình độ dài 3 thì bậc của mỗi miền ≥ 4.
Bài tập: Chứng minh tiếp hệ quả này.
▶
16 / 36
Bài tập
▶
Dùng hệ quả trước, hãy chứng minh rằng đồ thị K3,3 không
phẳng?
v1
v2
v3
v4
v5
v6
17 / 36
Định nghĩa
Độ dài của chu trình ngắn nhất trong đồ thị được gọi là chu vi
nhỏ nhất của đồ thị đó.
Nếu như đồ thị không tồn tại chu trình, thì chu vi nhỏ nhất của G
được định nghĩa bằng ∞.
18 / 36
Định lý (Bất đẳng thức cạnh đỉnh)
Trong đồ 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ó
g
|E| ≤
(|V| − 2).
g − 2
19 / 36
Bài tập
Dùng bất đẳng thức cạnh đỉnh để chứng minh rằng K3,3 và K5
không phải đồ thị phẳng.
20 / 36
Tải về để xem bản đầy đủ
36 trang
18820
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_9_do_thi_phang_tran_vinh_duc.pdf
