1/55
CHƯƠNG 7
CHU TRÌNH EULER VÀ
CHU TRÌNH HAMILTON
2/55
NỘI DUNG
Chu trình Euler
Điều kiện tồn tại chu trình Euler
Chu trình Hamilton\
Điều kiện tồn tại chu trình Hamilton
3/55
7.1. CHU TRÌNH EULER
Bài toán 7 cây cầu
Định nghĩa chu trình Euler
Điều kiện tồn tại chu trình Euler vô hướng
Điều kiện tồn tại chu trình Euler có hướng
Thuật toán tìm chu trình Euler
4/55
BÀI TOÁN 7 CÂY CẦU
Sông Pregel và cù lao Kneiphof chia thành phố Konigsberg ở
nước CH Litva thành 4 vùng đất.
7 cây cầu nối giữa các vùng đất.
B
A
D
Pregel
C
5/55
BÀI TOÁN 7 CÂY CẦU (tiếp)
Bài toán:Liệu có thể đi qua cả 7 cây cầu, mỗi cầu
đúng một lần, rồi quay về chỗ xuất phát được hay
không?
Bài toán đã làm say mê cư dân của thành phố. Họ háo
hức đi thử nhưng không thành công.
