Đường đi Euler và Chu trình Euler

Đườ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.

Để phát hiện đường đi và chu trình, ta phải tuân theo các điều kiện sau:

Đồ thị phải liên thông.
Khi đúng hai đỉnh có bậc lẻ, đó là Đường đi Euler.
Khi không đỉnh nào của đồ thị vô hướng có bậc lẻ, đó là Chu trình Euler.

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

Đầu vào: Ma trận kề của một đồ thị.
0 1 1 1 0
1 0 1 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 0
Đầu ra: Đồ thị có đường đi 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

isEulerian(Graph)

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

Đầu ra: Trả về 0 khi không phải Euler, 1 khi có đường đi Euler, 2 khi tìm thấy chu trình Euler.

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

Ví dụ (C++)

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

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

/* int graph[NODE][NODE] = {
  {0, 1, 1, 1, 1},
  {1, 0, 1, 0, 0},
  {1, 1, 0, 0, 0},
  {1, 0, 0, 0, 1},
  {1, 0, 0, 1, 0}
}; */
// bỏ comment để kiểm tra Chu trình Euler

/* int graph[NODE][NODE] = {
  {0, 1, 1, 1, 0},
  {1, 0, 1, 1, 0},
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 1},
  {0, 0, 0, 1, 0}
}; */
// Bỏ comment để kiểm tra Đồ thị không Euler

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;
}

int isEulerian() {
  if(isConnected() == false) // khi đồ thị không liên thông
    return 0;
  
  vector<int> degree(NODE, 0);
  int oddDegree = 0;
  
  for(int i = 0; i < NODE; i++) {
    for(int j = 0; j < NODE; j++) {
      if(graph[i][j])
        degree[i]++; // tăng bậc khi tìm thấy cạnh kết nối
    }
    if(degree[i] % 2 != 0) // khi bậc của đỉnh là lẻ
      oddDegree++; // đếm đỉnh bậc lẻ
  }
  
  if(oddDegree > 2) // khi đỉnh bậc lẻ lớn hơn 2
    return 0;
  
  return (oddDegree) ? 1 : 2; // khi oddDegree là 0, là Euler circuit, khi 2, là Euler path
}

int main() {
  int check;
  check = isEulerian();
  switch(check) {
    case 0: cout << "The graph is not an Eulerian graph."; break;
    case 1: cout << "The graph has an Eulerian path."; break;
    case 2: cout << "The graph has a Eulerian circuit."; break;
  }
}

Đầu ra

The graph has an Eulerian path.