【オイラー路】一筆書きできるかが一瞬でわかる?オイラー路を学ぶ【グラフ理論】

今回扱うのは「オイラー路」についてです。

これらはグラフ理論で扱われるもので、グラフの頂点を移動したときに特定の条件を満たすとそのグラフは「オイラー路・ハミルトン路を持つ」と言われます。

オイラー路に関してはみなさんが一度は遊んだことがあるであろう一筆書きになっています。

比較的とっつきやすい話題だと思いますので是非最後まで読んでみてください！

グラフについて

グラフ理論の基礎については一度記事にしているので詳しくは下のリンクをご覧ください。

【点つなぎの数学】点を線でつなぐグラフ理論の基礎と応用例【ネットワーク分析】

ここではオイラー路とハミルトン路を理解するのに必要な最低限のことを書いておきますので、ご存知の方は飛ばしてしまって構いません。

まず、こちらがグラフの一例になります。

グラフとは、頂点と辺で構成されたもののことを言います。

ここで頂点とは、上の図でいう数字が書かれた丸のことで、辺はそれらを繋いでいる線のことです。

２つの頂点が直接繋がっているとき、それらの頂点は隣接している、といいます。

上の図でいえば、１と２，２と３、３と４，４と５、５と６、３と６が隣接しています。

２つの頂点を辺を通って移動していく順路のことを経路といい、

同じ辺を通ることのない経路を小道、同じ頂点を通ることのない経路を道といいます。

上の図では、１→２→３→４→５→６→３と移動する経路は小道ではありますが道ではありません。

少し紛らわしい言葉ですので注意してください。

ひとまずはこれだけ分かればオイラー路とハミルトン路の話をしていけます。

オイラー路

それではまずはオイラー路についてです。

冒頭にもある通り、オイラー路とは一筆書きのことです。

一筆書きはすべての線をなぞらないといけないですし、同じ線をもう一度なぞることも禁止ですが、オイラー路も同じです。

つまりオイラー路をグラフ理論の言葉で言えば、「すべての辺をたった一度だけ通るような小道」のことになります。

また、オイラー路で通る最初と最後の頂点が同じとき、そのオイラー路のことをオイラー閉路といいます。

簡単にいえば全部の辺を通って一周して戻ってくる順路ってことです。

ハミルトン路は「すべての頂点をたった一度だけ通るような小道」でしたので、オイラー路とハミルトン路は辺をすべて通るか、頂点をすべて通るかの違いになります。

まずは簡単なグラフを例にしてオイラー路を理解していきましょう。

またまたこのグラフの登場です。

このグラフでのオイラー路は、

• １→２→３→４→５→６→３
• ３→４→５→６→３→２→１

の２つとこれらを逆向きに進んだ経路になります。

また、４，５，６をスタートにするオイラー路は存在しません。

これくらいのグラフだとパット見でもオイラー路を見つけることができますよね。

オイラー閉路

続いてはオイラー閉路について見ていきましょう。

先ほども書きましたが、オイラー閉路とは、最後にスタート位置に戻ってくるオイラー路のことを言います。

下のグラフで考えてみましょう。

このグラフはオイラー閉路を持つグラフになります。

このグラフのオイラー閉路は、

• ３→４→２→１→３→５→６→３
• ３→４→２→１→３→６→５→３
• ３→１→２→４→３→５→６→３
• ３→１→２→４→３→６→５→３

とこれらを逆向きに進んだ経路になります。

このグラフのようにオイラー閉路を持つグラフをオイラーグラフと呼びます。

オイラーグラフの判別

あるグラフを見せられて「このグラフはオイラーグラフですか」と問われれば、頂点数が6程度であればすぐにわかりますが、頂点数が多くなれば判別が困難になってきますよね。

しかし、オイラー閉路を持つかどうかの判別はかなり簡単に行うことができるんです。

そのために、２つだけ言葉の定義を行います。

グラフG内の任意の２頂点間に道が存在しているとき、Gを連結グラフといいます。

簡単に言えば、グラフが切り離されていない、ということです。

また、グラフＧの頂点Ｖに対して、頂点Vに接続されている辺の数をVの次数といいます。

三度このグラフです。

このグラフでみると、

となります。

それでは本題のオイラーグラフの判別についてです。

以下の２つは同値になります。

• グラフGはオイラーグラフである。
• グラフGのすべての頂点の次数は偶数である。

つまり、グラフの頂点の次数がすべて偶数ならそのグラフはオイラーグラフだし、

オイラーグラフのすべての頂点の次数は偶数になります。

先ほどオイラー閉路の例として挙げたグラフを見てみましょう。

このグラフの各頂点を見てみると、

となり、すべての頂点の次数は偶数になっていますね。

次に下のグラフをご覧ください。

頂点数８の少し複雑なグラフを用意してみました。

これくらいになるとオイラーグラフかどうかはぱっと見では分からないかと思います。

各頂点の次数を数えてみると、

となり、すべての頂点の次数は偶数になっているので、このグラフはオイラーグラフになります。

実際に、

５ → ３ → １ → ２ → ３ → ４ → ２ → ６ → ５ → ４ → ７ → ６ → ８ → ７ → ５

はオイラー閉路になっているため、このグラフはオイラーグラフになります。

まとめ

今回はオイラー路について基本的な部分について書きました。

オイラー路は誰もが一度は遊んだことがあるであろう一筆書きを数学的に扱ったものにです。

今回の記事で例に挙げたグラフの規模なら簡単にオイラー路を探すことができるため、かなりとっつきやすい話題だったのではないかと思います。

ハミルトン路が配達などの最短経路問題に使われるように、オイラー路も現実の問題とリンクさせることができます。

とある町全体の道路の検査を行うとなったとき、その検査を効率的に行っていくためには同じ道を通る回数を減らしていくことが重要になるかと思います。

道路と交差点を辺と頂点に見立ててオイラー路を探すことで効率的な検査を行っていくことが期待できます。

もちろん現実の問題はそんな簡単にいくわけないと思いますが、このようなとっつきやすい話も突き詰めれば現実の問題とリンクしていくのが数学の面白い部分だと個人的に思います。

こんなこと何に使うんだよ、と思うことはたくさんあると思いますが、調べてみると面白い活用例が見つかるかもしれませんよ！

今回は以上となります。

最後まで読んでいただきありがとうございました！