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

1


Đườ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.
2


Đường đi và chu trình Euler
D

A

B

C

3


Đường đi và chu trình Euler




DEABCEBD
5


Đường đi và chu trình Euler


Thuật toán tìm chu trình Euler của đồ thị
G(V, E)
Kết quả sẽ cho ra C là một chu trình Euler
bao gồm thứ tự các cạnh của chu trình.

6


7


Đường đi và chu trình Euler
1 2 3 4 5 6

1

3

2

4
5


0
0
0

1
0
0
0
1

0
1
0
1
0

C = Ø, v = 1
8


Đường đi và chu trình Euler
1 2 3 4 5 6

1

3

2

4

1
1
0
0
0

1
0
0
0
1

0
1
0
1
0

C = 1,2
9


Đường đi và chu trình Euler
1 2 3 4 5 6

1

3

2

1

1
1
0
0
0

1
0
0
0
1

0
1
0
1
0

C = 1,2,3
10


Đường đi và chu trình Euler
1 2 3 4 5 6

1

3

0
0
1
0
1

1
1
0
0
0

1
0
0
0
1

0
1
0
1
0

E≠Ø
11


Đường đi và chu trình Euler
1 2 3 4 5 6

0
1
0

0
0
1
0
1

0
1
0
0
0

1
0
0
0
1

0
1
0
1
0

,3,1
12

0

0
0
0
1
0

0
0
0
0
1

0
0
0
0
0

1
0
0
0
1

0
1
0
1

0
0
0

0
0
0
1
0

0
0
0
0
0

0
0
0
0
0

1
0
0
0
1

0
0

0
0
0
0
0

0
0
0
1
0

0
0
0
0
0

0
0
0
0
0

1
0
0
0
0


5
6

0 0 0 0 0 0
0
0
0
0
0

0
0
0
0
0

0
0
0
0
0

0
0
0
0
0

0
0

Đường đi Euler:
DEABECBDC,
DEABCEBDC

17


Đườ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
E

B

Chu trình Euler:
DEABCEBD
D

C

18


Đường đi và chu trình Euler


Đường đi và chu trình Hamilton (18051865)






Đị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
đi sơ cấp qua tất cả các đỉnh của G.
Một chu trình Hamilton của G là một chu trình
sơ cấp qua tất cả các đỉnh của G.

21


Đường đi và chu trình Hamilton
A

E

Đường đi Hamilton: ABECD

B

D

E


23


Đường đi và chu trình Hamilton

1.

2.

3.

4.

Qui tắc tìm chu trình Hamilton
Nếu tồn tại 1 đỉnh của G có bậc ≤ 1 thì G không
có chu trình Hamilton.
Nếu đỉnh x có bậc 2 thì cả 2 cạnh tới x đều phải
thuộc chu trình Hamilton.
Chu trình Hamilton không chứa bất kỳ chu trình
con thực sự nào.
Trong quá trình xây dựng chu trình Hamilton, sau
khi đã lấy 2 cạnh tới 1 đỉnh x đặt vào chu trình rồi
thì không thể lấy thêm cạnh nào tới x nữa. Do đó
có thể xóa mọi cạnh còn lại tới x trong G.
24


Đường đi và chu trình Hamilton
5