1
Lý thuy t đ thế ồ ị
Ch ng 1: Gi i thi uươ ớ ệ
2
Ch ng 1: Gi i thi uươ ớ ệ

Định nghĩa:
Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp
các đỉnh (vertices) V (V≠Ø) và các cạnh (edges) E.
Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương
ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên
kết hay kề (adjacent) với nhau và e được gọi là tới
các đỉnh v, w. Ký hiệu hay v w.
vwe =
e
3
Ch ng 1: Gi i thi uươ ớ ệ

Các đỉnh: A, B, C, D

Các cạnh: AB, AC, AD,
BD, BC
A
B
C
D
Cạnh không phân biệt thứ tự của đỉnh được gọi
là cạnh vô hướng. Đồ thị bao gồm các cạnh vô
hướng được gọi là đồ thị vô hướng.
4
Ch ng 1: Gi i thi uươ ớ ệ

-
Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub
graph) của đồ thị G = (V, E) nếu V’ ⊂ V và E’
⊂ E.
A
B
CD
E
B’
C’
A’
E’
8
Ch ng 1: Gi i thi uươ ớ ệ
-
Đồ thị có số đỉnh và số cạnh hữu hạn gọi là
đồ thị hữu hạn (finite graph), ngược lại là đồ
thị vô hạn (infinite graph).
9
Ch ng 1: Gi i thi uươ ớ ệ

Biểu đồ
A B
CD
A’
B’
C’
D’
E’
A”

A B C
D
E
F
X
Y
Z
T
G
G’
12
Ch ng 1: Gi i thi uươ ớ ệ
-
Đồ thị mà mọi cặp đỉnh đều kề nhau được
gọi là đồ thị đầy đủ (complete graph). Đồ thị
đầy đủ có n đỉnh được ký hiệu là K
n
.
A
B
CD
E
13
Ch ng 1: Gi i thi uươ ớ ệ
-
Đồ thị bù của một đồ thị G, ký hiệu là G, là
một đồ thị có cùng đỉnh với G và có các cạnh
là những cạnh mà ta phải bổ sung vàođể G
trở thành đầy đủ.
G G

Biểu diễn đồ thị - Danh sách kề
A B B D E
B A A C D E
C C C B D
D A B C E
E A B D
A
B
C
D
E
17
Ch ng 1: Gi i thi uươ ớ ệ

Biểu diễn đồ thị - Ma trận kề:
A B C D E
A 0 2 0 1 1
B 2 0 1 1 1
C 0 1 2 1 0
D 1 1 1 0 1
E 1 1 0 1 0
A
B
C
D
E
18
Ch ng 1: Gi i thi uươ ớ ệ

Định lý 1.2:

2
, , v
k-1
v
k
.
Ký hiệu: P = v
0
v
1
v
k

hay P = v
0
v
1
v
k
k (số cạnh tạo thành P) được gọi là chiều dài
của P. Ký hiệu l(P) = k.
e
1
e
2
e
k
20
Ch ng 1: Gi i thi uươ ớ ệ


ABCA là một chu trình đơn
giản và sơ cấp.

ACB là một đường đi đơn
giản và sơ cấp.

EABCAD là một đường đi
đơn giản nhưng không sơ
cấp.

EACBADE là một chu trình
đơn giản nhưng không sơ
cấp.
A
B
C
E
D
23
Ch ng 1: Gi i thi uươ ớ ệ

Liên thông
Một đồ thị được gọi là liên thông (connected) nếu mọi
cặp đỉnh của nó đều được nối với nhau bởi một
đường đi.
A
B
C
E
D