ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON

Định nghĩa. Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là
đường đi Hamilton. Chu trình bắt đầu tại một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh
đúng một lần sau đó quay trở lại v được gọi là chu trình Hamilton. Đồ thị được gọi là đồ thị
Hamilton nếu nó chứa chu trình Hamilton. Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửa
Hamilton.
void Hamilton( int k) {
/* Liệt kê các chu trình Hamilton của đồ thị bằng cách phát triển dãy đỉnh
(X[1], X[2],..., X[k-1] ) của đồ thị G = (V, E) */
for y∈ Ke(X[k-1]) {
if (k==n+1) and (y == v0) then
Ghinhan(X[1], X[2],..., X[n], v0);
else {
X[k]=y; chuaxet[y] = false;
Hamilton(k+1);
chuaxet[y] = true;
}
}
}
Chương trình chính được thể hiện như sau:
{
for (v∈V ) chuaxet[v] = true; /*thiết lập trạng thái các đỉnh*/
X[1] = v0; (*v0 là một đỉnh nào đó của đồ thị*)
chuaxet[v0] = false;
Hamilton(2);
}