เส้นทางและวงจรออยเลอร์ (Eulerian Path and Circuit)

เส้นทางออยเลอร์ (Euler Path) คือเส้นทางที่ผ่านทุกเส้นเชื่อม (Edge) เพียงครั้งเดียว สามารถใช้โหนด (Vertices) ซ้ำได้ วงจรออยเลอร์ (Euler Circuit) เป็นกรณีพิเศษที่โหนดเริ่มต้นและโหนดสิ้นสุดเชื่อมต่อกัน

เงื่อนไขในการตรวจสอบ:

• กราฟต้องเชื่อมต่อ (Connected)
• มีโหนดองศาคี่อยู่ที่ 2 โหนดพอดี → เป็น Euler Path
• ไม่มีโหนดองศาคี่เลย → เป็น Euler Circuit

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
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

Output: The graph has an Eulerian path.

อัลกอริทึม

traverse(u, visited) - DFS สำหรับตรวจสอบการเชื่อมต่อ

isConnected(graph) - ตรวจสอบว่ากราฟเชื่อมต่อหรือไม่

isEulerian(Graph) - ตรวจสอบประเภทออยเลอร์

Begin
  if isConnected() เป็น false then return 0
  
  นับองศาของแต่ละโหนด
  oddDegree := 0
  for ทุกโหนด i do
    for ทุกโหนด j ที่ติดกับ i do เพิ่มองศา
    if องศาของ i เป็นคี่ then oddDegree++
  done
  
  if oddDegree > 2 then return 0
  if oddDegree = 0 then return 2  // Euler Circuit
  else return 1  // Euler Path
End

ตัวอย่างโค้ด (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}
};

void traverse(int u, bool visited[]) {
  visited[u] = true;
  for(int v = 0; v < NODE; v++)
    if(graph[u][v] && !visited[v])
      traverse(v, visited);
}

bool isConnected() {
  bool *vis = new bool[NODE];
  for(int u = 0; u < NODE; u++) {
    for(int i = 0; i < NODE; i++) vis[i] = false;
    traverse(u, vis);
    for(int i = 0; i < NODE; i++)
      if(!vis[i]) return false;
  }
  return true;
}

int isEulerian() {
  if(!isConnected()) 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]++;
    if(degree[i] % 2 != 0) oddDegree++;
  }
  
  if(oddDegree > 2) return 0;
  return (oddDegree) ? 1 : 2;
}

int main() {
  int 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;
  }
}

ผลลัพธ์

The graph has an Eulerian path.