Chuyên đề
ĐỒ THỊ
HAMILTON

Khái niệm đường đi Hamilton được xuất
phát từ bài toán:
“Xuất phát từ một đỉnh của khối thập nhị
diện đều, hãy đi dọc theo các cạnh của
khối đó sao cho đi qua tất cả các
đỉnhkhác, mỗi đỉnh đi qua đúng một lần,
sau đó trở về đỉnh xuất phát”
Bài toán này được nhà toán học Hamilton
đưa ra vào năm 1859
Giới thiệu:
Nhà toán học Hamilton

•
Đường đi Hamilton là đường qua
tất cả các đỉnh của đồ thị và đi qua
mỗi đỉnh đúng một lần
Hay đường đi (x[1],x[2],…,x[n])
được gọi là đường đi Hamilton nếu
x[i]≠x[j] (1≤i<j≤n)
Định nghĩa:
a
a
d
d
b
b

Đồ thị nửa Hamilton là đồ thị có chứa một
đường đi Hamilton
Định nghĩa:

a
a
d
d
b
b
c
c
g
g
a
a
d
d
b
b
c
c
e
e
f
f
a
a
b
b

chu trình Hamilton đôi
một không có cạnh
chung.
Định lý về đồ thị Hamilton:
Đồ thị đầy đủ K4