Chu trình Hamilton

Một đường đi hamilton là một đường đi trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ đi qua đúng 1 lần

Một chu trình hamilton là một đường đi hamilton có điểm đầu trùng với điểm cuối !

Đồ thị Hamilton là đồ thị có chứa ít nhất một chu trình Hamilton.

Đường đi x₀,x₁,...,x_n-1,x_n là đường đi Hamilton nếu V = {x₀,x₁,...,x_n-1,x_n} x_i!=x_j , 0 ≤ i < j ≤ n

Chu trình x₀,x₁,...,x_n,x₀ là chu trình Hamilton nếu x₀,x₁,...,x_n,x₀ là đường đi Hamilton