Skip to content →

オイラーグラフの特徴付けと証明

全ての辺をちょうど一回通る回路が存在するとき、そのグラフはオイラーグラフであるといいます。また、そのような回路をオイラー回路といいます(慣習的にオイラー閉路と呼ばれることがありますが、閉路は各頂点の次数が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)\) でオイラー回路が構築できます。

関連記事

参考文献

[1] A First Course in Graph Theory
[2] ​グラフ理論(R. Diestel)

Euler の名前が冠されていますが、彼が示したのは必要性(\(\Rightarrow\))だけでした。十分性(\(\Leftarrow\))を示したのは、Hierholzerです[1]。Euler & Heirholzerグラフと呼ぶべきかもしれません。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA