全ての辺をちょうど一回通る回路が存在するとき、そのグラフはオイラーグラフであるといいます。また、そのような回路をオイラー回路といいます(慣習的にオイラー閉路と呼ばれることがありますが、閉路は各頂点の次数が2ですから語義としては誤りです)。
オイラーグラフであることの必要十分条件は、次の通りです:
オイラーグラフ \(\Leftrightarrow\) 連結かつ全ての頂点の次数が偶数
証明しましょう。
(\(\Rightarrow\)の証明)オイラー回路の辺を辿って一周すると、頂点を通り抜けるたびに入る辺と出る辺を1つずつ使います(始点・終点はペアにする)。従って、各頂点の次数は偶数です。また、回路は連結なので、元のグラフ \(G\) も連結です。
(\(\Leftarrow\)の証明)辺の数 \(||G||\) に対する数学的帰納法で示します。\(||G||=0\) つまり辺が存在しなければ、1頂点のオイラー回路が取れます。\(||G||\geq 1\) とします。各頂点の次数が偶数なので、DFSにより回路 \(W\) が取れます。\(G-W\)の各頂点は次数が偶数なので、帰納法の仮定より、各連結成分でオイラー回路が取れます。元のグラフ \(G\) の連結性より、各連結成分のオイラー回路は、回路 \(W\) と繋ぎ合わせることで、一つの回路にできます。これはオイラー回路そのものです。
この証明はオイラー回路を求めるアルゴリズムも示しています。DFSで極大な回路として \(W\) を取ると、通った辺の全てを \(W\) に使えます(まだ通っていない辺が接続している限り、小道を閉じずにその辺を通ります)。各辺を一度しか通らず、回路の合体も \(O(1)\) なので、\(O(E)\) でオイラー回路が構築できます。
関連記事
- Noga Alon の二部グラフの辺彩色
- オイラー回路が一つのカギになったアルゴリズムです。
参考文献
[1] A First Course in Graph Theory
[2] グラフ理論(R. Diestel)
Euler の名前が冠されていますが、彼が示したのは必要性(\(\Rightarrow\))だけでした。十分性(\(\Leftarrow\))を示したのは、Hierholzerです[1]。Euler & Heirholzerグラフと呼ぶべきかもしれません。
Comments