Chu trình Euler trong đồ thị có hướng

Đường đi Euler (Euler path) là một đường đi, qua đó ta có thể thăm mọi cạnh đúng một lần. Ta có thể sử dụng cùng các đỉnh nhiều lần. Chu trình Euler (Euler Circuit) là một loại đặc biệt của đường đi Euler. Khi đỉnh bắt đầu của đường đi Euler cũng kết nối với đỉnh kết thúc của đường đi đó, thì nó được gọi là Chu trình Euler.

Để kiểm tra xem một đồ thị có phải Euler hay không, ta phải kiểm tra hai điều kiện:

• Đồ thị phải liên thông.
• Bậc vào (in-degree) và bậc ra (out-degree) của mỗi đỉnh phải bằng nhau.

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

Đầu vào: Ma trận kề của đồ thị.
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 0 0 0 0
0 0 1 0 0
Đầu ra: Tìm thấy Chu trình Euler.

Thuật toán

traverse(u, visited)

Đầu vào: Nút bắt đầu u và nút visited để đánh dấu nút nào đã thăm.

Đầu ra: Duyệt qua tất cả các đỉnh kết nối.

Bắt đầu
  đánh dấu u là đã thăm
  với mọi đỉnh v, nếu nó kề với u, thực hiện
    nếu v chưa được thăm thì
      traverse(v, visited)
  kết thúc
Kết thúc

isConnected(graph)

Đầu vào: Đồ thị.

Đầu ra: True nếu đồ thị liên thông.

Bắt đầu
  định nghĩa mảng visited
  với mọi đỉnh u trong đồ thị, thực hiện
    làm cho tất cả nút chưa thăm
    traverse(u, visited)
    nếu còn nút nào chưa thăm thì
      trả về false
  kết thúc
  trả về true
Kết thúc

isEulerCircuit(Graph)

Đầu vào: Đồ thị cho trước.

Đầu ra: True khi tìm thấy một chu trình Euler.

Bắt đầu
  nếu isConnected() là false thì
    trả về false
  định nghĩa danh sách đếm cạnh vào và cạnh ra cho mỗi nút
  với mọi đỉnh i trong đồ thị, thực hiện
    sum := 0
    với mọi đỉnh j kết nối với i, thực hiện
      cạnh vào cho đỉnh i tăng lên
      tăng sum
    kết thúc
    số cạnh ra của đỉnh i là sum
  kết thúc
  nếu danh sách cạnh vào và cạnh ra giống nhau thì
    trả về true
  ngược lại trả về false
Kết thúc

Ví dụ (C++)

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

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

void traverse(int u, bool visited[]) {
  visited[u] = true; // đánh dấu v là đã thăm
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]) {
      if(!visited[v])
        traverse(v, visited);
    }
  }
}

bool isConnected() {
  bool *vis = new bool[NODE];
  // với mọi đỉnh u làm điểm bắt đầu, kiểm tra xem tất cả nút có nhìn thấy được không
  for(int u; u < NODE; u++) {
    for(int i = 0; i < NODE; i++)
      vis[i] = false; // khởi tạo như không nút nào được thăm
    traverse(u, vis);
    for(int i = 0; i < NODE; i++) {
      if(!vis[i]) // nếu có nút không được thăm bởi duyệt, đồ thị không liên thông
        return false;
    }
  }
  return true;
}

bool isEulerCircuit() {
  if(isConnected() == false) {
    // khi đồ thị không liên thông
    return false;
  }
  
  vector<int> inward(NODE, 0), outward(NODE, 0);
  
  for(int i = 0; i < NODE; i++) {
    int sum = 0;
    for(int j = 0; j < NODE; j++) {
      if(graph[i][j]) {
        inward[j]++; // tăng cạnh vào cho đỉnh đích
        sum++; // số cạnh ra bao nhiêu
      }
    }
    outward[i] = sum;
  }
  
  if(inward == outward) // khi số cạnh vào và cạnh ra cho mỗi nút giống nhau
    return true;
  
  return false;
}

int main() {
  if(isEulerCircuit())
    cout << "Euler Circuit Found.";
  else
    cout << "There is no Euler Circuit.";
}

Đầu ra

Euler Circuit Found.