オイラー路とオイラー回路とは？グラフの判定条件とC++での実装方法を解説

オイラー路とオイラー回路の概要

オイラー路（Euler Path）とは、グラフ内のすべての辺をちょうど1回ずつ通過できる経路のことです。このとき、頂点は何度通っても構いません。

一方、オイラー回路（Euler Circuit）は、オイラー路の特別なケースです。オイラー路の始点となる頂点が、同時にその経路の終点とも接続されている場合、つまり「スタート地点に戻ってくる」ような経路が存在するとき、それをオイラー回路と呼びます。

オイラー路・オイラー回路の判定条件

グラフがオイラー路またはオイラー回路を持つかどうかを判定するには、以下の条件に従います。

• グラフは連結である必要があります。
• 次数が奇数である頂点がちょうど2つ存在する場合、そのグラフはオイラー路を持ちます。
• 無向グラフにおいて、奇数次数の頂点が1つも存在しない場合、そのグラフはオイラー回路を持ちます。

逆に、奇数次数の頂点が3つ以上ある場合は、オイラー路もオイラー回路も存在しません。

入力と出力の例

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

出力：
このグラフはオイラー路を持ちます。

アルゴリズム

traverse(u, visited) ― 深さ優先探索による連結チェック用の走査

入力：開始ノード u と、訪問済みノードを記録するための visited 配列。

出力：u から到達可能なすべての頂点を走査します。

Begin
    mark u as visited
    for all vertex v, if it is adjacent with u, do
        if v is not visited, then
            traverse(v, visited)
    done
End

isConnected(graph) ― グラフの連結性判定

入力：対象となるグラフ。

出力：グラフが連結であれば true を返します。

Begin
    define visited array
    for all vertices u in the graph, do
        make all nodes unvisited
        traverse(u, visited)
        if any unvisited node is still remaining, then
            return false
    done
    return true
End

isEulerian(Graph) ― オイラー性の判定

入力：与えられたグラフ。

出力：オイラー性がない場合は 0、オイラー路を持つ場合は 1、オイラー回路を持つ場合は 2 を返します。

Begin
    if isConnected() is false, then
        return false
    define list of degree for each node
    oddDegree := 0

    for all vertex i in the graph, do
        for all vertex j which are connected with i, do
            increase degree
        done
        if degree of vertex i is odd, then
            increase oddDegree
    done

    if oddDegree > 2, then
        return 0
    if oddDegree = 0, then
        return 2
    else
        return 1
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}
};

/* 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}
};
*/      // コメントを解除するとオイラー回路のチェックができます

/* 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}
};
*/      // コメントを解除すると非オイラーグラフのチェックができます

void traverse(int u, bool visited[]) {
    visited[u] = true;     // v を訪問済みとしてマーク

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

bool isConnected() {
    bool *vis = new bool[NODE];
    // すべての頂点 u を起点として、全ノードが訪問可能かどうかを確認
    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() == false)     // グラフが非連結の場合
        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)     // 奇数次数の頂点が2より多い場合
        return 0;

    return (oddDegree)?1:2;     // oddDegree が 0 ならオイラー回路、2 ならオイラー路
}

int main() {
    int check;
    check = isEulerian();

    switch(check) {
        case 0: cout << "このグラフはオイラーグラフではありません。";
            break;
        case 1: cout << "このグラフはオイラー路を持ちます。";
            break;
        case 2: cout << "このグラフはオイラー回路を持ちます。";
            break;
    }
}

実行結果

このグラフはオイラー路を持ちます。

まとめ

オイラー路・オイラー回路の判定は、グラフの連結性と奇数次数の頂点の個数という2つの要素だけで決まります。計算量は隣接行列を用いた場合 O(V²) となり、非常に効率的な判定が可能です。この問題は、18世紀にオイラーがケーニヒスベルクの橋渡し問題を解いたことに由来する、グラフ理論における最も古典的なテーマの一つです。