Đại cương về đồ thị ppsx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (537.85 KB, 44 trang )
Đại cương về đồ thị
Đồ thị vô hướng (undirected graph)
Cạnh (edge) {1,4}
Đỉnh (vertex)
“Đỉnh 2 và đỉnh 3 “Đỉnh 2 và đỉnh 3
kề nhau (adjacent)kề nhau (adjacent)””
Số đỉnh n = 4.
Số cạnh m = 5.
Đa đồ thị, Đồ thị đơn (simple graph)
Đồ thị G(V, E)
Tập đỉnh V = {1, 2, 3, 4}
Tập cạnh: E = {12, 13, 14, 23, 34}
‘Đơn’ = Không có
cạnh song song và
không có khuyên
Khuyên
(loop)
Hai cạnh song
song (parallel)
Tập cạnh: E = {12, 13, 14, 23, 34}
Đồ thị có hướng (directed graph)
Cung (arc) [1,2]
Khuyên
(loop)
Đỉnh đầu
(initial)
Đỉnh cuối
(terminal)
Bậc của đỉnh trong đồ thị vô hướng
Định nghĩa: Bậc (degree) của một đỉnh x là số
cạnh kề với x.
Degree(1) = d(1) = 3
Degree(2) = d(2) = 2
Đỉnh treo, đỉnh cô lập
d(3) = 1
đỉnh treo (pendant)
d(5) = 0
đỉnh cô lập (isolated)
Bậc của đỉnh trong đồ thị có hướng
Định nghĩa: Bậc ra (out-degree) của một đỉnh x
là số cung coi x là đỉnh đầu; bậc vào (in-
degree) là số cung coi x là đỉnh cuối.
OutDegree(1) = d
+
(1) = 1
InDegree(1) = d
-
(1) = 2
OutDegree(1) = d
+
(1) = 1
InDegree(1) = d
(1) = 2
Mối quan hệ giữa số đỉnh và số cạnh
Định lý: Cho G = (X, E)
a)
b) Số đỉnh bậc lẻ là số
chẵn.
2 ( )
i X
m d i
∈
=
∑
chẵn.
c) ếu G có hướng
( ) ( )
i X i X
m d i d i
− +
∈ ∈
= =
∑ ∑
Chứng minh: (Bài tập)
Bài tập
1. Trong một bữa tiệc, mọi người bắt tay nhau.
CMR số người bắt tay với một số lẻ người
khác là một số chẵn.
2.
Bảng A của môn bóng đá Seagames 24 thi
2.
Bảng A của môn bóng đá Seagames 24 thi
đấu vòng tròn một lượt. CMR tại mọi thời
điểm của giải, luôn có hai đội có số trận đấu
bằng nhau.
Đồ thị đủ K
n
Đ: Đồ thị đủ (complete graph) K
n
là đồ thị đơn vô
hướng, mỗi đỉnh đều kề với các đỉnh còn lại.
K
2
K
3
K
4
Tính chất của K
n
• Bậc mỗi đỉnh: d(x) = n – 1.
• Số cạnh của K
n
: m = n(n – 1)/2.
K
3
K
4
Đồ thị bù
n
G K G
= −
Bài tập
1. Một lớp học có 6 học sinh. CMR luôn có 3
người quen nhau hoặc 3 người không quen
nhau.
2. Bốn người bất kỳ (trong số n>3 người) đều có
một người quen với ba người còn lại. CMR
một người quen với ba người còn lại. CMR
luôn có một người quen với tất cả n – 1 người
còn lại.
3. Trong giải cờ tướng quốc gia (có 20 kỳ thủ)
hiện đã có 21 trận đấu được tiến hành. CMR
có một kỳ thủ đã thi đấu ít nhất 3 trận.
Đẳng cấu
Định nghĩa: G
1
(X
1
,E
1
) ≅ G
2
(X
2
,E
2
) nếu có song ánh ϕ
: X
1
X
2
sao cho
1 2
{ , } { ( ), ( )}
i j E i j E
ϕ ϕ
∈ ⇔ ∈
Ví dụ: hai đồ thị sau đẳng cấu với song ánh
1 DN, 2 CT, 3 BD, 4 AG
Tính chất của sự đẳng cấu
≅
Tính chất: ếu G
1
(X
1
,E
1
) ≅ G
2
(X
2
,E
2
) thì:
1. |X
1
| = |X
2
|: cùng số đỉnh
2. |E
1
| = |E
2
|: cùng số cạnh
3. Cùng số đỉnh với bậc tương ứng.
4. Số đỉnh kề với i
∈
X
1
và
ϕ
(i)
∈
X
2
như nhau.
•Tính chất trên chỉ có
điều kiện cần
•Ví dụ: hai đồ thị sau
không đẳng cấu
?
?
Bài tập
1. Xét sự đẳng cấu của các cặp đồ thị sau. Chỉ ra
song ánh nếu chúng đẳng cấu
Bài tập
2. Một đồ thị đơn G gọi là tự bù nếu nó đẳng cấu
với đồ thị bù của nó.
a) CMR nếu G tự bù thì số đỉnh của G là 4k hay
4k+1 (k nguyên dương)
4k+1 (k nguyên dương)
b) Tìm tất cả các đồ thị tự bù có 4 đỉnh; 5 đỉnh.
Đường đi
Định nghĩa: Cho G = (X, E).
• Đường đi (path) là một dãy các cạnh liên tiếp nhau
(x
0
, x
1
, x
2
, …, x
k
) trong đó x
i
x
i+1
là một cạnh ∈ E. Độ
dài (length) của đường đi = k.
•
Đường đi
đơn (simple)
nếu không có cạnh nào xuất
•
Đường đi
đơn (simple)
nếu không có cạnh nào xuất
hiện quá một lần.
• Đường đi sơ cấp (elementary) nếu không có đỉnh nào
xuất hiện quá một lần.
• Đường đi là chu trình (cycle) nếu đỉnh đầu trùng
đỉnh cuối x
0
= x
k
.
Ví dụ đường đi
• (u, y, w, v) là một đường đi độ dài 3.
• (z, u, y, v, u) là một đường đi đơn nhưng không sơ
cấp.
• (u, y, w, v, u) là một chu trình. Có thể xem chu trình
này như chu trình (w, v, u, y, w).
Định lý
ĐL: ếu mọi đỉnh của một đồ thị G đều có bậc
≥ 2 thì G có ít nhất một chu trình đơn.
Chứng minh (Xem giáo trình)
Tính liên thông của đồ thị
Đ: Hai đỉnh x và y của một đồ thị vô hướng được gọi
là liên thông (connected) với nhau nếu x = y hoặc có
đường đi giữa hai đỉnh x, y.
hận xét:
• Quan hệ liên thông là một quan hệ tương đương.
• Mỗi lớp tương đương là một thành phần liên thông
(component) của G.
• Nếu G chỉ có một thành phần liên thông thì G được
gọi là đồ thị liên thông (luôn có đường đi giữa hai
đỉnh x, y bất kỳ).
Ví dụ tính liên thông
• G liên thông
• H không liên thông
• H có 2 thành phần
liên thông
Khớp
liên thông
Cầu
Đối chu trình
Đ: Cho G = (X,E) và A⊂ X. Đối chu trình của
A, ký hiệu w(A), gồm các cạnh của G có một
đỉnh trong A, một đỉnh ngoài A.
VD:
• Với A = {x, y}, w(A) = {xu, yu, yv, yw}.
• Với B = {x, u}, w(B) = {xy, uz, uv, uy}.
Đối chu trình sơ cấp
Đ: w = w(A) được gọi là đối chu trình sơ cấp (tập
cắt) nếu:
– G – w không liên thông
– G – w’ còn liên thông với mọi tập con w’ của w.
VD: với A = {x, y}, w(A) = {xu,
yu, yv, yw} là một tập cắt.
Với B = {x, u}, w(B) = {xy, uz, uv,
uy} không là một tập cắt vì G –
{uz} không liên thông.
Bài tập (đồ thị G đơn)
1. CMR nếu số cạnh < số đỉnh thì G có một đỉnh
treo hay một đỉnh cô lập.
2. Cho G có bậc nhỏ nhất ≥ k ≥ 2. CMR G có
một chu trình sơ cấp có chiều dài ≥ k.
3.
Giả sử số cạnh
≥
số đỉnh. CMR G có chu
3.
Giả sử số cạnh
≥
số đỉnh. CMR G có chu
trình.
4. Vẽ tất cả đồ thị có 5 đỉnh (không đẳng cấu) và
a) Có 4 cạnh
b) Có 6 cạnh
