オイラーグラフとオイラー閉路

グラフ上の任意の頂点から出発して、すべての辺を使って一筆書きをすることができるようなグラフを準オイラーグラフと呼びます。またそのような一筆書きの順番で頂点を並べたパスをオイラー路と呼びます。ここでは始点と終点が同じ頂点である必要はありません。

これに対して一筆書きができるだけでなく、最初の頂点に戻ることができるようなグラフをオイラーグラフと呼びます。そしてそのような一筆書きの順番で頂点を並べたパスをオイラー閉路と呼びます。

一筆書きが可能かどうかは簡単な方法でわかります。まずすべての頂点が連結していることです。そして各頂点から出ている辺の数が奇数であるものが存在しないか 2個だけである場合です。各頂点から出ている辺の数がすべて偶数の場合、一筆書きが可能であり、始点と終点は同じ頂点になります。奇数である頂点が2つある場合は一方が始点となり、もう片方が終点となります。

頂点が10個あり、以下のような辺を持つグラフがあったとします。

このようなテキストファイルを用意します。1行目が頂点数で、2行目以降がどの頂点同士がつながっているのかを示しています。またこれは無向グラフです。「0 1」ということは 0 から 1 へつながっているとともに 1 から 0 へもつながっています。

example.txt

まずテキストファイルのデータを読み出して、どの頂点がどの頂点につながっているのかを調べます。

EulerGraphクラスの定義

オイラー路を取得する処理をおこなうためのEulerGraphクラスを定義します。オイラー路を取得するまえに、本当にオイラー路が存在するのかを確認しなければなりません。

一筆書きは可能なのか?

一筆書きが可能であるためには、すべての頂点が連結していなければなりません。それを確認するためには、深さ優先探索(幅優先探索でもよい)で任意の頂点から各頂点にたどり着けるかを調べます(厳密には、グラフが準オイラーグラフであるための連結性の条件は「孤立点を除いたグラフが連結である」ですが、ここでは孤立点があるかどうかは考えない)。

次に頂点の次数(頂点から出ている辺の数)が奇数のものを数えます。0なら一筆書きが可能で始点終点は同じなので始点も終点も0にします。2なら一筆書きが可能で一方が始点であり、もう片方が終点なのでstartとgoalは異なる奇数点の番号を格納します。それ以外のときは一筆書きはできないのでfalseを返します。

有向グラフの場合は、すべての頂点において入次数と出次数が同じであるか、(入次数 + 1 = 出次数)のものと(入次数 = 出次数 + 1)がそれぞれひとつずつ存在する場合でないと一筆書きはできません。

深さ優先探索でオイラー路を取得する

始点がどこになるのかが分かったら深さ優先探索でオイラー路を取得します。試しに深さ優先探索で行き止まりになるまで進み続けて取得した結果を表示させてみます。

途中で選択する辺を間違えた場合、選択すべき部分の探索は行き止まりになってから行なわれます。そこでその部分はあとでつなぎかえることにします。

完成させる

GetResultDfsメソッドを定義して、これが返したリストのリストをつなぎかえてオイラー路を取得します。

定義したEulerGraph.GetEulerPathメソッドでオイラー路を表示させてみることにします。