📂グラフ理論

オイラーグラフ

定義

$G$を連結グラフとしよう。$G$の全てのエッジを含む閉じたトレイルが存在する場合、$G$をオイラーグラフと呼び、そのトレイルをオイラートレイルという。全てのエッジを含むが閉じていないトレイルが存在する場合、$G$をセミオイラーグラフという。

説明

これは、一筆書き問題としても私たちに馴染みのある概念である。

オイラーグラフについての議論は、有名なケーニヒスベルクの橋の問題から始まった。この問題は、街にかかった7つの橋を一度だけ渡り、最初の位置に戻ることができるかどうかについてのものであった。

解を知らなければ、一見、全ての可能性をチェックしなければならない困難な問題に見える。最初は数学の問題のようにも見えず、全てのケースをチェックすれば解けそうに思えるが、実際に試みると簡単ではない。

偉大な数学者オイラーは、これをグラフ問題に変えて見事に解決した。驚くべきことに、この解決策は、グラフ理論が学界の関心を集めていなかった時代で、空間をトポロジカルに見るという発想自体が存在しなかった時の解決策であることである。つまり、オイラーは未来の概念を持ち込んで、未来の方法で問題を解決したのだ。

次に、グラフがオイラーグラフであるための必要十分条件を示す定理である。

定理 ¹

$G$を連結グラフとしよう。

$G$がオイラーグラフであることと$G$の全ての頂点の次数が偶数であることは同値である。

証明

$(\Rightarrow)$

$P$が$G$のオイラートレイルであるとしよう。$P$は、通過する任意の頂点について、その頂点に接続されたエッジを2つ通過する必要がある。全てのエッジは$P$にただ一度だけ含まれるので、各頂点の次数は$2$の和になる。したがって、全ての頂点の次数は偶数でなければならない。

---

$(\Leftarrow)$

補助定理: 有限グラフ$G$の全ての頂点の次数が$2$以上なら、$G$はサイクルを持つ。

$G$の全ての頂点の次数が偶数なので、$2$以上であり、$G$にはサイクル$C$が存在することが保証される。$G$の全てのエッジが$C$に属していれば、証明することはない。今、サイクル$C$が通過するエッジだけを全て取り除いたグラフ$H = G \setminus C$を考える。$H$はサイクル$C$を失っているので連結性を失ったかもしれないが、頂点ごとにエッジが$2$個だけ減っているので、次数は依然として偶数である。また、$H$の各コンポーネントは、少なくとも1つの$C$と共通の頂点を持つ。ヌルグラフになるまで、同じ方法で各コンポーネントで新しいサイクルを見つけて除去する操作を繰り返し、これらのサイクルのシーケンスを$\mathcal{C}_{k}$とする。これらのサイクルは、前に見つかったサイクルと必ず共通の頂点を持つので、全てのサイクルを通過することができ、したがって、全てのエッジを通過するトレイルが存在し、$G$はオイラーグラフである。

■

併せて見る

• 全ての頂点を含む閉じたパスが存在するグラフ：ハミルトングラフ
• オイラートレイルの存在と具体的に見つけることは別の問題である。オイラーグラフであることが保証された時、オイラートレイルを見つけるアルゴリズムとして、フルーリーアルゴリズムが知られている。