Bài toán Chu trình Hamilton

Giới thiệu

Trong đồ thị vô hướng, đường đi Hamilton là đường đi qua mỗi đỉnh đúng một lần. Chu trình Hamilton (Hamiltonian cycle) là đường đi Hamilton có thêm cạnh từ đỉnh cuối về đỉnh đầu.

Bài toán: xác định đồ thị có chu trình Hamilton hay không, và in ra chu trình nếu có.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề của đồ thị G(V, E). 
Đầu ra: Thuật toán tìm đường đi Hamilton: (0, 1, 2, 4, 3, 0). Đồ thị này có nhiều đường Hamilton khác. Nếu không có, trả về false.

Thuật toán

isValid(v, k)

Đầu vào: Đỉnh v và vị trí k.

Đầu ra: Kiểm tra việc đặt v tại vị trí k có hợp lệ không.

Begin
  nếu không có cạnh giữa node(k-1) và v thì trả về false
  nếu v đã được dùng thì trả về false
  trả về true  // ngược lại hợp lệ
End

cycleFound(node k)

Đầu vào: Đỉnh của đồ thị.

Đầu ra: True nếu tìm thấy chu trình Hamilton, ngược lại false.

Begin
  nếu đã bao gồm tất cả đỉnh thì
    nếu có cạnh giữa đỉnh k và 0 thì trả về true
    ngược lại trả về false
  với mọi đỉnh v trừ đỉnh bắt đầu làm:
    nếu isValid(v, k) thì
      thêm v vào đường đi
      nếu cycleFound(k+1) là true thì trả về true
      ngược lại xóa v khỏi đường đi (backtrack)
  done
  trả về false
End

Ví dụ (C++)

#include <iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
  {0, 1, 0, 1, 0},
  {1, 0, 1, 1, 1},
  {0, 1, 0, 0, 1},
  {1, 1, 0, 0, 1},
  {0, 1, 1, 1, 0},
};

int path[NODE];

void displayCycle() {
  cout << "Cycle: ";
  for (int i = 0; i < NODE; i++) cout << path[i] << " ";
  cout << path[0] << endl;  // in lại đỉnh đầu
}

bool isValid(int v, int k) {
  if (graph[path[k-1]][v] == 0) return false;  // không có cạnh
  for (int i = 0; i < k; i++)  // đỉnh đã dùng thì bỏ qua
    if (path[i] == v) return false;
  return true;
}

bool cycleFound(int k) {
  if (k == NODE) {
    if (graph[path[k-1]][path[0]] == 1) return true;
    else return false;
  }
  for (int v = 1; v < NODE; v++) {
    if (isValid(v, k)) {
      path[k] = v;
      if (cycleFound(k+1) == true) return true;
      path[k] = -1;  // backtrack
    }
  }
  return false;
}

bool hamiltonianCycle() {
  for (int i = 0; i < NODE; i++) path[i] = -1;
  path[0] = 0;  // đỉnh đầu tiên là 0
  if (cycleFound(1) == false) {
    cout << "Solution does not exist" << endl;
    return false;
  }
  displayCycle();
  return true;
}

int main() { hamiltonianCycle(); }

Kết quả đầu ra

Cycle: 0 1 2 4 3 0