1
Lý thuy t đ thế ồ ị
Ch ng 2: Đ ng đi và chu trìnhươ ườ

2
4.6 Đ 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
4.6 Đ ng đi và chu trình Eulerườ
A B
C
D

4
4.6 Đ 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.


0 1 1 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
1
3
6
4
5
2
1 2 3 4 5 6
1
2
3
4
5
6
C = Ø, v = 1

9
4.6 Đ 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

5
2
C = 1,2,3

11
4.6 Đ ng đi và chu trình Eulerườ
0 0 0 0 0 0
0 0 0 1 1 0
0 0 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
C = 1,2,3,1 E ≠ Ø

12
4.6 Đ ng đi và chu trình Eulerườ
0 0 0 0 0 0

2
3
4
5
6
1
3
6
4
5
2
C = 1,2,4,3, ,3,1

14
4.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