Chương
Chương
4:
4:
LÝ THUY
LÝ THUY
Ế
Ế
T Đ
T Đ
Ồ
Ồ
TH
TH
Ị
Ị
Chương
Chương
4
4
4.3
ĐỒ THỊ EULER
4.4
ĐỒ THỊ HAMILTON
CÂY
4.6
BÀI TOÁN TÌM ĐƯỜNG ĐI
NGẮN NHẤT
4.5
MỞ ĐẦU
4.1

đ
đ
ỉ
ỉ
nh
nh
và tập E các
c
c
ạ
ạ
nh
nh.
v
e
w
V
V
í
í
d
d
ụ
ụ
:
:
4.2 CÁC KHÁI NIỆM CƠ BẢN

Đ
Đ

c
ó
ó
hư
hư
ớ
ớ
ng
ng
g
g
ọ
ọ
i
i
l
l
à
à
cung
cung.
v
e
w
Mỗi cạnh e được liên kết với một cặp đỉnh (v, w)
có thứ tự
V
V
í
í

Nửa bậc: Cho đồ thị có hướng G = (V, E).
+ Nửa bậc ra của đỉnh vV, kí hiệu d
r
(v) là
số cung đi ra từ đỉnh v.
+ Nửa bậc vào của đỉnh vV, kí hiệu d
v
(v)
là số cung đi vào đỉnh v
4.2 CÁC KHÁI NIỆM CƠ BẢN
Đỉnh cô lập có bậc bằng 0
Cho đồ thị G = (V, E). Khi đó:
i. Tổng bậc các đỉnh của đồ thị là số chẵn và
d(v) = 2|E|
ii. Nếu G là đồ thị có hướng thì:
d
v
(v) = d
r
(v) = |E|
MỘT SỐ TÍNH CHẤT
* Tính chất 1:
* Tính chất 2:
Cho đồ thị G(V, E). Khi đó số đỉnh bậc lẻ là số chẵn
* Tính chất 3:
Cho đồ thị đơn G = (V, E) có n đỉnh (n  2) có
ít nhất hai đỉnh cùng bậc.
* Tính chất 4:
Cho đồ thị đơn G = (V, E) có n đỉnh (n > 2) có
đúng 2 đỉnh cùng bậc thì 2 đỉnh này không thể

quá một lần.
 Chu trình sơ cấp là chu trình không đi qua một đỉnh
quá một lần.
 Chu trình là đường đi có đỉnh đầu và đỉnh cuối
trùng nhau.
 Đường đi đơn là đường đi không đi qua một cạnh
quá một lần.
 Đường đi có hướng trong đồ thị có hướng là dãy các
cung nối tiếp nhau (e
1
, e
2
, …, e
n
) thỏa mãn đỉnh cuối của
cung e
i
là đỉnh đầu của cung e
i+1
, i = 1, …, n-1.
 Đường đi đơn (chu trình đơn) có hướng là đường đi
(chu trình) có hướng không đi qua một cung quá một
lần.
 Đường đi (chu trình) có hướng sơ cấp là đường đi
(chu trình) có hướng không đi qua một đỉnh quá một
lần.
 Chu trình có hướng là đường đi có hướng có đỉnh đầu
và đỉnh cuối trùng nhau.
c
b

e
1
e
9
 Đồ thị liên thông là đồ thị mà mọi cặp đỉnh của
nó đều có đường đi nối chúng với nhau.
 Đồ thị con:
Cho đồ thị G = (V, E). Đồ thị G’ = (G’, E’) là
đồ thị con của G nếu:
(i) V’ V và E’ E và
(ii) e = (v,w)  E: e  E’  v, w  V’
 Thành phần liên thông:
Là đồ thị con liên thông tối đại của G.
4.2.3 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY
a. Ma trận kề
 Đồ thị vô hướng
Cho đồ thị vô hướng G = (V, E) có n đỉnh theo thứ
tự v
1
, v
2
, …, v
n
.
Ma trận kề của đồ thị G là ma trận vuông A = (a
ij
)
n
,
trong đó a

v
5
v
4
v
3
v
2
v
1
Vv,aa)v(d
i
n
1j
ji
n
1j
iji



Ví dụ:
Tổng bậc
của v
1
 Đồ thị có hướng
Cho đồ thị có hướng G = (V, E) có n đỉnh theo thứ
tự v
1
, v

4
e
3
e
2
e
1
e
5
e
8
e
7
e
6
000000v
6
100000v
5
110000v
4
001000v
3
001100v
2
000110v
1
v
6
v

Vv,a)v(d
i
n
1j
jiir



số bậc vào của
đỉnh v
i
= tổng
các số trên cột v
i
số bậc ra của đỉnh v
i
=
tổng các số trên hàng v
i
b. Ma trận liên thuộc
 Đồ thị vô hướng
Cho đồ thị G = (V, E) có n đỉnh, V = {v
1
, v
2
, …, v
n
}
và m cạnh E = {e
1

5
v
3
v
2
v
1
e
5
e
4
e
3
e
2
e
1
e
6
e
7
0100000v
5
0110110v
4
1011000v
3
0001101v
2
0000011v

ij
)
nm
. Khi đó:
Số bậc của đỉnh v
i
= tổng
các số trên hàng v
i
 Đồ thị có hướng
Cho đồ thị có hướng G = (V, E) có n đỉnh, V = {v
1
,
v
2
, …, v
n
}, m cạnh E = {e
1
, e
2
, …, e
m
} và không có
khuyên.
Ma trận liên thuộc của đồ thị G là ma trận
A = (a
ij
)
nm