Đạ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.

∈
=
∑
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.

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
≅

(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

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}.