Xem mẫu
- Đồ thị phẳng
Trần Vĩnh Đức
HUST
Ngày 1 tháng 3 năm 2016
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 36
- Tài liệu tham khảo
▶ Eric Lehman, F Thomson Leighton & Albert R Meyer,
Mathematics for Computer Science, 2013 (Miễn phí)
▶ 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 36
- way to represent this graph in a plane without any edges crossing?
Giới thiệu
FIGURE 1 Three Houses and Three Utilities.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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ị.
FIGURE 2 The FIGURE 3 K4 Drawn
FIGURE 2 The FIGURE 3 K4 Drawn
Graph K . with No Crossings.
Graph K4 . 4 with No Crossings.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 36
- Ví dụ
10.7 Planar Graphs 719
10.7 Planar Graphs 719
wn FIGURE 4 The FIGURE 5 A Planar
FIGURE 4 The FIGURE 5 A Planar
Graph Q3 . Representation of Q3 .
Graph Q3 . Representation of Q3 .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 36
- anar. We will give an example to showsubregions, R21beand
how this can R22in, an
done as shown
ad in Figure 7
develop some general results that can be used to do this.
Ví dụ v
, planar?
Đồ thị K3,3 : v1 v2 v3
draw K3,3 in the plane with no edges crossing is doomed. We now
presentation of K3,3 , the vertices v1 and v2 must be connected to both
s form a closed curve that splits the plane into two regions, R1 and
a). The vertex v3 is in either R1 or R2 . When v3 is in R2 , the inside v
ges between v3 and v4 and between v3 and v5 separate R2 into two
v4 v5 v6
s shown in Figure 7(b).
không phẳng vì FIGURE 6 The Graph K . F
3,3
v1 v5 v1 v5
R21
R2 R1 v3 R1
R22
v4 v2 v4 v2
(a) (b)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 36
- Proof: First, we specify a planar representati
a sequence of subgraphs G1 , G2 , . . . , Ge =
is done using the following inductive defini
Obtain
Euler chứng minh rằng Gn from
mọi biểu diễn phẳngby
Gn−1 củaarbitrarily adding a
một đồ thị đều
chia mặt phẳng thành cùng số miền như nhau.
R4
R2 R6
R3
R1
R5
FIGURE 8 The Regions of the Planar R
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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. 3
▶ Giả sử định lý đúng với r > 1.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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. 3
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
s
mãn v ≥ 3. Vậy thì e ≤ 3v − 6.
c
7
▶ Bậc của một miền là số
b d
3 cạnh trên biên của miền đó.
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
R3
nhiêu cạnh?
f
FIGURE 11 The Degrees of Regions.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 36
- Bài tập
E, we can produce a subgraph of G by removing the edges in E
subgraph has the same vertex set V as G. Its edge set is E − E %
▶ Dùng hệ quả trước, hãy chỉ ra rằng đồ thị K5 không phẳng.
a a
e b
e
d c c
ocessors. FIGURE 15 A Subgraph of K5 .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 36
- R2 , as shown in Figure 7(a). The ver
Bài tập of the closed curve, the edges betwe
subregions, R21 and R22 , as shown in
▶ 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
FIGURE 6 The Graph K3,3 .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 ∞.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 36
nguon tai.lieu . vn
