Luận văn tốt nghiệp Phan Thanh Long
Chơng 1
một số vấn đề cơ bản của đồ thị
I. Các định nghĩa đồ 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ử X là tập hữu hạn, không rỗng các phần tử nào đó và U XìX. Bộ G =
<X, U> đợc gọi là đồ thị hữu hạn. Mỗi phần tử xX gọi là một đỉnh và mỗi
phần tử u = (x,y) U gọi là một cạnh của đồ thị G = <X, U>.
Xét một cạnh u U khi đó tồn tại 2 đỉnh x, y X sao cho u = (x, y), ta nói
rằng x nối với y hoặc x và y 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 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)
a. Tại đỉnh y có một khuyên b. Một cung có hớng từ x sang y
c. Cặp đỉnh (x, y) có 2 cạnh song song
Hình 1.1
Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để
biểu diễn, nh sơ đồ một mạng máy tính, sơ đồ mạng lới giao thông, sơ đồ thi
công một công trình.
9
x
y
x

C
D
A
B
C
D
A
B
C
D
Luận văn tốt nghiệp Phan Thanh Long
Đồ thị G=<X,U> đợc gọi là đồ thị vô hớng nếu tất cả các cạnh e U mà cặp
đỉnh thuộc nó e = (x,y) X không phân biệt thứ tự. Đồ thị vô hớng là đồ thị
không có bất kỳ một cung nào.
Ví dụ: nh hình 1.3.a là biểu diễn của một đồ thị vô hớng.
2. Đồ thị có hớng
Đồ thị G = <X, U> đợc gọi là đồ thị có hớng nếu tất cả các cạnh e U mà cặp
đỉnh thuộc nó e = (x, y) X có phân biệt thứ tự. Đồ thị có hớng là đồ thị mà
mọi e = (x, y) X đều là cung.
Hình 2.1 Đồ thị có hớng
3. Đồ thị hỗn hợp
Đồ thị G=<X,U> vừa có cạnh vô hớng, vừa có cạnh có hớng thì nó đợc gọi là
đồ thị hỗn hợp, loại đồ thị này rất ít khi đợc dùng tới.
Chú ý rằng vấn đề phân chia đồ thị và các thuật ngữ về đồ thị chỉ mang tính
tơng đối, hiện nay vẫn còn cha mang tính thống nhất chuẩn trên nhiều tài liệu.
III. Một số khái niệm và tính chất cơ bản của đồ thị
1. Bậc đồ thị
1.1 Bậc đồ thị vô hớng
Cho đồ thị vô hớng G = <X,U>. Xét 1 đỉnh x X đặt m(x) là số cạnh thuộc
đỉnh x khi đó m(x) đợc gọi là bậc của đỉnh x. Nếu x có một khuyên thì m(x) đợc

(x) là bậc ra của đỉnh x.
- Nếu m
+
(x) + m
-
(x) = 0 thì đỉnh x đợc gọi đỉnh là cô lập
- Nếu m
+
(x) + m
-
(x) = 1 thì đỉnh x đợc gọi là đỉnh treo
Ta đặt
Khi đó m(G) đợc gọi là bậc của đồ thị có hớng G = <X,U>.
Trong đồ thị có hớng thì m
+
(x) = m
-
(x) = U
Ví dụ:
- Xét đồ thị vô hớng nh trong hình 1.3.a ta có:
m(G) = m(A) + m(B) + m(C) + m(D) = 2 + 5 + 2 + 1 = 10
- Xét đồ thị có hớng trong hình 2.1 ta có:
m(G) = [m
+
(A) + m
+
(B) + m
+
(C) ] + [m
-


+==
B xA xX x
m(x) m(x) m(x) 2m
Luận văn tốt nghiệp Phan Thanh Long
2. đờng đi và chu trình
2.1 Đờng đi
Xét đồ thị G = <X,U> với
- Tập đỉnh X = {x
1
,x
2
,...,x
n
}
- Tập cạnh U = {u
1
,u
2
,...,u
m
}
Tập hợp các đỉnh kề nhau từ x
i
đến x
j
đợc gọi là 1 đờng đi, kí hiệu
x
i
x

. Nếu x
i
x
j
thì đờng đi này đợc gọi là một chu trình.
Nh vậy chu trình là một đờng đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau.
Chú ý rằng đờng đi trong đồ thị có hớng không đợc đi ngợc chiều mũi tên
- Đờng đi (chu trình) đợc gọi là đơn nếu nó đi qua mỗi cạnh không quá một
lần.
- Đờng đi (chu trình) đợc gọi là sơ cấp nếu nó đi qua mỗi đỉnh đúng một lần
Hình 3.1
Ví dụ nh ở hình 3.1 ADBE là một đờng đi sơ cấp từ A đến E độ dài 3;
ABCDBE là đờng đi không sơ cấp ( qua B 2 lần) từ A đến E độ dài 5; ABDAB
là một đờng đi không đơn (chứa cạnh AB 2 lần) từ A đến B độ dài 4; ABDA Là
1 chu trình đơn và sơ cấp độ dài 3; CC là đờng đi độ dài 0.
Xét đồ thị có hớng nh hình 2.1 thì ABCB là một đờng đi độ dài 3; CBA không
là một đờng đi vì không có cung đi từ B đến A.
Định lý:
Nếu trong đồ thị G = <X,U> các đỉnh đều có bậc không nhỏ hơn 2 ( x X |
m(x) 2 ) thì trong G tồn tại ít nhất một chu trình.
Chứng minh:
Xét tất cả các đờng đi đơn. Vì đồ thị là hữu hạn cho nên số các đờng đi đơn là
hữu hạn. Chọn một đờng đi là dài nhất nào đó ví dụ từ x
i1
đến x
ij +1
(xem hình vẽ
13
A
B

, U
1
> và G
2
= <X
2
, U
2
>
Trong đó: X
1
X
2
=
và U
1
U
2
=
Khi đó: X = X
1
X
2
U = U
1
U
2
Thì G = <X,U> là đồ thị có 2 thành phần liên thông G
1
, G

, U
3
> với X
3
= {F} và U
3
=
Cho đồ thị có hớng G = <X, U>
- G đợc gọi là đồ thị liên thông yếu nếu đồ thị vô hớng tơng ứng với nó là liên
thông
- G là liên thông một chiều nếu với hai đỉnh x,y khác nhau bất kỳ của G luôn
có đờng đi x - y hoặc đờng đi y - x.
14
x
i0
x
i1
x
i2
x
i3
x
ij
x
ij+1
A
B
F
C
ED