Pythonでオイラー回路を構成するために追加すべき最小の辺数を求めるアルゴリズム

問題概要

オイラー回路（Euler Circuit）とは、グラフ上のすべての辺をちょうど1回ずつ通過し、最終的に出発点へ戻ることができる閉路のことです。

ここでは、b 個のノードと a 本の辺からなる無向グラフが与えられたとき、このグラフにオイラー回路を構成するために追加すべき最小の辺数を求める問題を考えます。

たとえば、次のようなグラフが入力として与えられた場合を考えてみましょう。

この場合、答えは 1 となります。

解法のポイント：オイラー回路の成立条件

連結グラフがオイラー回路を持つための必要十分条件は、すべての頂点の次数（接続されている辺の数）が偶数であることです。したがって、この問題は次の2つの観点から考えることができます。

• 奇数次の頂点を偶数化する：1本の辺を追加すると、その両端にある2つの頂点の次数の偶奇が同時に変化します。つまり、奇数次の頂点が k 個ある連結成分には、最低でも k / 2 本の辺が必要です。
• 連結成分同士をつなぐ：すべての次数がすでに偶数になっている成分（オイラー回路を既に持つ成分）が複数存在する場合は、それらを互いにつなぐために、成分ごとに1本の辺が必要です。

アルゴリズムの手順

DFS関数の定義

まず、連結成分ごとにグラフを探索し、奇数次の頂点の数を数えるための dfs() 関数を定義します。引数は g（隣接リスト）、visit（訪問済みフラグ）、odd_vert（各連結成分の奇数次頂点数）、degree（各頂点の次数）、comp（連結成分の番号）、v（現在の頂点）です。

1. visit[v] := 1 として、頂点 v を訪問済みにする
2. degree[v] が奇数であれば、odd_vert[comp] を +1 する
3. 頂点 v に隣接するすべての頂点 u について、未訪問であれば再帰的に dfs() を呼び出す

メイン処理

1. サイズ n+1 の空リストからなる隣接リスト g を作成する
2. 偶数次のみで構成される成分を格納するリスト e と、奇数次の頂点を含む成分を格納するリスト o を用意する
3. degree・visit・odd_vert を、サイズ n+1 のゼロで初期化されたリストとして作成する
4. m 本の辺それぞれについて、隣接リストに双方向の辺を登録し、両端の頂点の次数を +1 する
5. ans := 0、comp := 0 で初期化する
6. 頂点 1 から n まで順に調べ、未訪問の頂点が見つかったら comp を +1 して DFS を開始する。探索終了後、その成分の odd_vert[comp] が 0 であれば e へ、そうでなければ o へ成分番号を追加する
7. o が空で、かつ e のサイズが 1 であれば 0 を返す（グラフ全体がすでにオイラー回路を持っている状態）
8. o が空であれば len(e) を返す（偶数次のみの成分同士をつなぐために必要な辺数）
9. e が空でなければ ans += len(e) を加算する
10. o の各成分について ans += odd_vert[i] // 2（整数部分のみ）を加算する
11. ans を返す

Pythonでの実装例

それでは、実際の実装を見てみましょう。

def dfs(g, visit, odd_vert, degree, comp, v):
    visit[v] = 1
    if (degree[v] % 2 == 1):
        odd_vert[comp] += 1
    for u in range(len(g[v])):
        if (visit[u] == 0):
            dfs(g, visit, odd_vert, degree, comp, u)

def solve(n, m, s, d):
    g = [[] for i in range(n + 1)]
    e = []
    o = []
    degree = [0] * (n + 1)
    visit = [0] * (n + 1)
    odd_vert = [0] * (n + 1)
    for i in range(m):
        g[s[i]].append(d[i])
        g[d[i]].append(s[i])
        degree[s[i]] += 1
        degree[d[i]] += 1
    ans = 0
    comp = 0
    for i in range(1, n + 1):
        if (visit[i] == 0):
            comp += 1
            dfs(g, visit, odd_vert, degree, comp, i)
            if (odd_vert[comp] == 0):
                e.append(comp)
            else:
                o.append(comp)
    if (len(o) == 0 and len(e) == 1):
        return 0
    if (len(o) == 0):
        return len(e)
    if (len(e) != 0):
        ans += len(e)
    for i in range(len(o)):
        ans += odd_vert[i] // 2
    return ans

b = 3
a = 2
source = [1, 2]
destination = [2, 3]
print(solve(b, a, source, destination))

入力

b = 3, a = 2, source = [1, 2], destination = [2, 3]

出力

1

まとめ

このアルゴリズムでは、DFSによって各連結成分に含まれる奇数次の頂点の数を集計し、「奇数次の頂点を偶数化するために必要な辺数」と「複数の連結成分をつなぐために必要な辺数」を合計することで、オイラー回路の構成に必要な最小の追加辺数を求めています。計算量は DFS が O(n + m) であるため、グラフ全体の処理も O(n + m) で完了し、非常に効率的です。