x
y
x
y
b
y
c
d
b
a
MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ
THỊ
I. MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
1. Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các
loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ
thị.
Giả sử V là tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E) được gọi là
đồ thị hữu hạn. Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u = (x,y) của E được gọi
là một cạnh của đồ thị G = (V,E).
Xét một cạnh u của E khi đó tồn tại hai đỉnh x, y của V sao cho u = (x,y), ta nói rằng
x nối với y hoặc x và y phụ thuộc u.
- Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề
nhau.
- Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
- Nếu u = (x,y) mà x, y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u
là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào.
- Khi giữa cặp đỉnh (x,y) có nhiều hơn một cạnh thì ta nói rằng những cạnh cùng cặp
đỉnh là những cạnh song song hay là cạnh bội.
a) b) c)
Hình 1.1

Thí dụ 2.
Hình 2. Sơ đồ máy tính là đơn đồ thị vô hướng
Trong trường hợp giữa hai máy tính nào đó thường xuyên phải tải nhiều thông tin
người ta phải nối hai máy này bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy
được cho trong hình 3.
Hình 3. Sơ đồ mạng máy tính với đa kênh thoại
Định nghĩa 2. Đa đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ
các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e
1
và
e
2
được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.
l
b
a
g
c
d
k
i
h
e
c
d
l
k
i
h
ge

1
, e
2
tương
ứng cùng với một cặp đỉnh được gọi là cung lặp.
Trong các phần tử tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và
đơn đồ thị có hướng. Vì vậy, để ngắn gọn, ta bỏ qua tính từ đơn khi nhắc đến chúng.
2. Các thuật ngữ cơ bản
Trong phần này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị.
Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng.
Định nghĩa 1. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v)
là cạnh của đồ thị G. Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên thuộc với
hai đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v
sẽ được gọi là các đỉnh đầu của cạnh (u,v).
Để có thể biết có bao nhiêu cạnh liên thuộc với một cạnh, ta đưa vào định nghĩa sau.
Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc
với nó và sẽ ký hiệu là deg(v).
Hình 1. Đồ thị vô hướng G
Thí dụ 1. Xét đồ thị trong hình 1 ta có.
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0.
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong ví dụ trên đỉnh g là
đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có các tính chất sau:
d
e
cb
a
∑
∈
=

+
(v)(deg
-
(v)).
Hình 2. Đồ Thị có hướng G
Thí dụ 3. Xét đồ thị cho trong hình 2. Ta có
deg
-
(a) = 1, deg
-
(b) = 2, deg
-
(c) = 2, deg
-
(d) = 2, deg
-
(e) = 2.
deg
+
(a) = 3, deg
+
(b) = 1, deg
+
(c) = 1, deg
+
(d) = 2, deg
+
(e) = 2.
Do mỗi cung (u,v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần
trong bán bậc ra của đỉnh u nên ta có:

Trong đó u = x
0
, v = x
n
, v = (x
i
, x
i+1
)
∈
E, i = 0,1,2,…, n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:
(x
0
,x
1
), (x
1
,x
2
),…, (x
n-1
,x
n
).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu
trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi
là đơn nếu như không có cạnh nào bị lặp lại.
Thí dụ 1. Trên đồ thị vô hướng cho hình 1: a, d, c, f, e là đường đi đơn độ dài 4.
Còn d, e, c, a không là đường đi, do (e,c) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là

e
c
b
a
G
H2 H3
H1
H
(x
0
, x
1
), (x
1
, x
2
), (x
n-1
, x
n
).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu
trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi
là đơn nếu như không có cạnh nào bị lặp lại.
Thí dụ 2. Trên đồ thị có hướng cho ở hình 3: a
→
d
→
c
→

Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi
và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.
Thí dụ 3. Trong hình 2: Đồ thị G là liên thông, còn đồ thị H là không liên thông.
Hình 2. Đồ thị liên thông G và đồ thị H gồm 3
thành phần liên thông H
1
, H
2
, H
3
.
II. MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
1 Thuật toán tìm kiếm trên đồ thị
1.1 Tìm kiếm theo chiều sâu trên đồ thị