1
Lý thuy t đ thế ồ ị
Ch ng 2: Đ ng đi và chu trìnhươ ườ
2
Đ ng đi và chu trình Eulerườ
Bài toán “Königsburg Bridges” (Leonhard Euler,
1707-1783)
Xác định một chu trình đi qua tất cả 7 cây cầu,
mỗi cái đúng 1 lần.
3
Đ ng đi và chu trình Eulerườ

Định nghĩa: Xét 1 đồ thị liên thông G.

Một đường đi Euler của G là một đường đi
đơn giản có đỉnh bắt đầu khác đỉnh kết thúc
và qua tất cả các cạnh của G. Khi này G còn
được gọi là một đường đi Euler.

Một chu trình Euler của G là một chu trình
đơn giản đi qua tất cả các cạnh của G. Khi
này G còn được gọi là một chu trình Euler.

Một đồ thị chứa chu trình Euler được gọi là
đồ thị Euler.
4
Đ ng đi và chu trình Eulerườ

Định lý 2.1: (Định lý Euler 1)

Cho 1 đồ thị vô hướng G liên thông và có

2
1 2 3 4 5 6
1
2
3
4
5
6
C = Ø, v = 1
8
Đ ng đi và chu trình Eulerườ
0 0 1 0 0 0
0 0 1 1 1 0
1 1 0 1 0 1
0 1 1 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
1 2 3 4 5 6
1
2
3
4
5
6
1
3
6
4
5
2

0 0 1 0 1 0
1 2 3 4 5 6
1
2
3
4
5
6
1
3
6
4
5
2
C = 1,2,3,1 E ≠ Ø
11
Đ ng đi và chu trình Eulerườ
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 1
0 0 1 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
1 2 3 4 5 6
1
2
3
4
5
6

Đ ng đi và chu trình Eulerườ
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0
1 2 3 4 5 6
1
2
3
4
5
6
1
3
6
4
5
2
C = 1,2,4,3,6, ,3,1
14
Đ ng đi và chu trình Eulerườ
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
1 2 3 4 5 6

6
4
5
2
C = 1,2,4,3,6,5,2,3,1 E = Ø
16
Đ ng đi và chu trình Eulerườ

Định lý 2.2 (Định lý Euler 2):
Cho một đồ thi vô hướng G liên thông và có
hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu
và chỉ nếu G có đúng 2 đỉnh bậc lẻ.
A
B
CD
E
Đường đi Euler:
DEABECBDC,
DEABCEBDC
Tìm chu trình Euler
17
18
Đ ng đi và chu trình Eulerườ

Định lý 2.3 (Định lý Euler 3):
Cho đồ thị có hướng G liên thông và có hơn
1 đỉnh. Khi đó, G có chu trình Euler nếu và
chỉ nếu G cân bằng.
A
B

DEABCEBDC,
DEBCEABDC
Đ nh nghĩa:ị
Một đồ thị liên thông (liên thông yếu đối với đồ
thị có hướng) có chứa một đường đi Euler
được gọi là đồ thị nửa Euler.

Hệ quả: Đồ thị liên thông G là nửa Euler khi
và chỉ khi có đúng hai đỉnh bậc lẻ trong G.
21
Bài t p:ậ

Với giá trị nào của n các đồ thị sau đây có
chu trình Euler ?

Với giá trị nào của m và n các đồ thị phân đôi
đầy đủ K
m,n
có:

a) chu trình Euler ? b) đường đi Euler ?
22
23
Đ ng đi và chu trình Hamilton (1805-ườ
1865)

Định nghĩa:
Xét 1 đồ thị liên thông G có hơn 1 đỉnh

Một đường đi Hamilton của G là một đường