アルゴリスト

アルゴリズムについてのブログ

オイラーグラフ - グラフ理論入門4

連結グラフGのすべての辺を含む閉じたtrailがあるとき、Gはオイラーグラフという。

補題: Gの点の次数がすべて2以上ならGには閉路がある。

証明: Gにループや多重辺があるときに閉路があることは自明なので、Gは単純グラフと仮定できる。vがGの任意の点とすると、vに隣接する v_1を選び、同様に i \geq 1に対して v_iに隣接する v_{i+1} を選び、walkを作る。Gの点は有限なので、いずれは前に選んだ点をもう一度選ぶことになる。このような点 v_kは、walk上の2つの v_kの間の部分を閉路とする。□

定理: 連結グラフGがオイラーグラフであるための必要十分条件は、Gの点の次数がすべて偶数であること。

証明: 各点の次数が偶数とする。Gは連結なので、次数はどの点も2以上で、補題より閉路Cを含む。CにGのすべての辺が含まれているなら証明が終わるので、そうでない場合を考える。GからCの辺を除去して得られるグラフHの辺数はより少なくなり、どの点の次数も偶数である。帰納法により、各成分にはオイラー小道がある。Gの連結性より、Hの各成分はCと1つ以上の点を共有するので、Gのオイラー小道が次のように作れる。Cの辺をたどり、Hの孤立点でない点が現れたらその点を含むHの成分のオイラー小道を辿ってその点に戻り、またCの辺をたどることを続けて、Hの他の成分の点が現れたら同じことをする。これを繰り返し、終了したときに出発点に戻る。□

系: 連結グラフがオイラーグラフであるための必要十分条件は、その辺集合が互いに素な閉路に分割できること。

系: 連結グラフが半オイラーグラフであるための必要十分条件は、ちょうど2個だけ奇数次の点があること。

定理 (Fleuryのアルゴリズム): Gはオイラーグラフとする。以下のアルゴリズムは実行可能で、結果としてGのオイラー小道を作る。

  1. たどった辺は除去する。もし孤立点が生じたらそれも除去する。
  2. どの段階でも、他にたどる辺がない場合は橋をたどらない。

証明: まずどの段階でもアルゴリズムが実行可能であることを示す。 点vに到達したと仮定する。v ≠ uならば、残っている部分グラフHは連結でuとvだけ奇数次。次の辺を除去してもHが非連結にならないことを示すことで続行可能と示せる。そうでないと仮定すると、橋vwがあり、H-vwのwを含む成分Kにはuを含まない。点wはKにおいて奇数次なので、Kには他にも奇数次の点があることになり矛盾。v=uの場合も同様。次にオイラー小道が得られることを示す。uに接続している最期の辺が用いられるとき、Gにはたどられていない辺が残っていない。残っていたとすると、これらの辺に隣接している辺で以前にたどられた辺のあるものを除去したとき、そのグラフは非連結になったはずで、矛盾。□

参考