有向グラフのオイラー回路とは？成立条件とC++による判定アルゴリズムを解説

オイラー路（Euler Path）とは、グラフ上のすべての辺をちょうど1回ずつ通過する経路のことです。このとき、同じ頂点を何度訪れても構いません。オイラー回路（Euler Circuit）はオイラー路の特殊な形態で、経路の始点と終点が同じ頂点でつながっている、すなわち「同じ頂点から出発して同じ頂点へ戻る閉じた経路」を指します。この概念は、18世紀の「ケーニヒスベルクの橋の問題」をきっかけにレオンハルト・オイラーが考察したもので、グラフ理論の原点ともいえる考え方であり、「一筆書き」が可能かどうかの判定にも応用されます。

オイラー回路の成立条件

有向グラフがオイラー回路を持つかどうかを判定するには、次の2つの条件を確認します。

• グラフが連結であること： 辺をもつすべての頂点同士が互いに到達可能（強連結）でなければなりません。連結でない場合、すべての辺を1本の経路で辿ることができません。
• すべての頂点で入次数と出次数が等しいこと： 各頂点に入ってくる辺の本数と出ていく辺の本数が一致していれば、その頂点を通過するたびに「入った分だけ出られる」ため、閉じた経路が成立します。

入力と出力

入力：グラフの隣接行列
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

出力：
Euler Circuit Found.

アルゴリズム

判定は「深さ優先探索（DFS）による連結性の確認」と「各頂点の入次数・出次数の比較」という2段階で行います。以下に擬似コードを示します。

traverse(u, visited)

入力： 探索の開始ノード u、訪問済みノードを記録する配列 visited
出力： u から到達可能なすべての頂点を探索する

Begin
   u を訪問済みとしてマークする
   u に隣接するすべての頂点 v について
      v が未訪問であれば
         traverse(v, visited) を呼び出す
   繰り返し終了
End

isConnected(graph)

入力： 対象のグラフ
出力： グラフが連結であれば true、そうでなければ false

Begin
   visited 配列を用意する
   グラフ内のすべての頂点 u について
      すべてのノードを未訪問状態に戻す
      traverse(u, visited) を実行する
      未訪問のノードがまだ残っている場合は
         false を返す
   繰り返し終了
   true を返す
End

isEulerCircuit(graph)

入力： 判定対象のグラフ
出力： オイラー回路が存在すれば true

Begin
   isConnected() の結果が false であれば
      false を返す
   各ノードの入辺数・出辺数を格納するリストを用意する

   グラフ内のすべての頂点 i について
      sum := 0
      i に接続するすべての頂点 j について
         頂点 j の入辺数を 1 増やす
         sum を 1 増やす
      繰り返し終了
      頂点 i の出辺数 := sum
   繰り返し終了

   入辺リストと出辺リストが完全に一致すれば
      true を返す
   そうでなければ false を返す
End

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

// u から到達可能な頂点を再帰的に探索する
void traverse(int u, bool visited[]) {
   visited[u] = true;     // u を訪問済みとしてマーク

   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {
         if(!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;
}

// オイラー回路の存在を判定する
bool isEulerCircuit() {
   if(isConnected() == false) {     // グラフが非連結の場合
      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]++;     // 行き先頂点 j の入辺数を増やす
            sum++;           // 出ていく辺の数を数える
         }
      }
      outward[i] = sum;
   }

   if(inward == outward)     // 全頂点で入次数と出次数が一致
      return true;
   return false;
}

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

実行結果

Euler Circuit Found.

計算量

隣接行列を用いたこの実装では、1回の深さ優先探索に O(V²) の時間がかかり、連結性の判定ではこれを全頂点 V 回繰り返すため O(V³) となります。次数の集計には O(V²) 必要であり、全体の時間計算量は O(V³)、追加で必要な記憶領域は O(V) です。なお、隣接リストを用いれば連結性の判定を O(V×(V+E)) まで改善できます。