こんにちは！しゅんです！
今回はオイラー路とハミルトン路について解説していきます！
オイラー路とハミルトン路はどちらもグラフ理論で登場する数学用語です。難しく感じるかもしれませんが、これらは実は一筆書きと非常に関係が深い概念です。
ということでこの記事ではオイラー路とハミルトン路が一体どのようなものなのか、そしてこれらが一筆書きとどのように関係しているのかについて説明していきたいと思います。
それでは解説していきましょう！
普段はNBAのデータ分析をしたりしています。
ぜひこちらの記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
オイラー路ってなに？
オイラー路はグラフ中にあるすべての辺を丁度1回通るような路のことを言います。下の図を見てください。
この図を見ると5個の頂点と7本の辺でグラフが構成されています。このグラフの7本の辺をすべて通るようなオイラー路はあるでしょうか。
上図はオイラー路の一例です。この順番で矢印の通りに進んでいけばすべての辺を丁度一度通るようなオイラー路ができますね。
始点と終点が同じ頂点の場合はオイラー閉路という
上の例を見ると左下の頂点からスタートしてオイラー路を通って最終的にスタートと同じ左下の頂点にゴールしていますね。
このようにスタートの点（始点）とゴールの点（終点）が同じオイラー路を特別にオイラー閉路と呼びます。
オイラー路（閉路）ができる条件
オイラー路（閉路）ができる条件を説明する前に次数という用語について説明したいと思います。次数とは頂点と接続している辺の本数のことです。例えば下の図を見てください。
この図は左のグラフの各頂点の次数をまとめたものです。例えば頂点1には4本の辺がくっついていますね。すなわち次数は4になります。他にも頂点2を見ると2本の辺がくっついているため次数は2になります。
次数はよくdegで表し、例えば頂点\(v\)の次数が3のときはdeg(\(v\)) = 3と表します。
オイラー路ができる条件
オイラー路ができる条件は以下の通りです。
次数が奇数の頂点が0個または2個持つ
例えば下のグラフは奇数の頂点が2個なのでこのようなオイラー路が存在します。
下のグラフは次数が奇数の頂点が4つなのでオイラー路は存在しません。
またオイラー閉路ができる条件は以下の通りです。
全ての頂点の次数が偶数である
下のグラフはオイラー閉路を持ちます。
ハミルトン路ってなに？
ハミルトン路はグラフ中にあるすべての頂点を丁度1回通るような路のことを言います。下の図を見てください。
この図を見ると5個の頂点と7本の辺でグラフが構成されています。このグラフの7本の辺をすべて通るようなハミルトン路はあるでしょうか。
上図はハミルトン路の一例です。この順番で矢印の通りに進んでいけばすべての頂点を丁度一度通るようなハミルトン路ができますね。
ハミルトン路の場合はすべての頂点さえ通れば大丈夫なので通らない辺があっても問題ないです。
始点と終点が同じ頂点の場合はハミルトン閉路という
ハミルトン路の中でも特に始点と終点が同じ場合はハミルトン閉路と言います。例えば下のグラフにおいて矢印で表した閉路はハミルトン閉路となります。
ハミルトン閉路ができる条件
オイラー路（閉路）のときとは違ってハミルトン路（閉路）ができるためのちゃんとした条件はありません。（数学用で言うと必要十分条件のこと）
その代わりに、これを満たしてれば少なくともハミルトン閉路を持つっていう条件はいくつかあります。
Oreの定理
グラフの頂点数\(n\)が3以上のときに、繋がっていない2つの頂点\(v\)と\(w\)に対して、
deg(\(v\)) + deg(\(w\)) \( \geq n\)のときにそのグラフはハミルトン閉路を持ちます。ここでの繋がっていないとは辺で直接結ばれていないということです。
このことをOreの定理と言います。例えば下のグラフはOreの定理に当てはまっているのでハミルトン閉路を持ちます。
Diracの定理
グラフの頂点数\(n\)が3以上のとき、グラフ中のすべての頂点\(v\)の次数がdeg(\(v\)) \(\geq \frac{1}{2} n\)を満たすときそのグラフはハミルトン閉路を持ちます。
このことをDiracの定理と言います。例えば下のグラフはDiracの定理に当てはまっているのでハミルトン閉路を持ちます。
ということでハミルトン閉路を持つための条件であるOreの定理とDiracの定理を紹介しましたが、どちらも結局辺がたくさんあればハミルトン閉路を持つよってことを言っています。
一筆書きはオイラー路のこと
最後にこれまで話してきたことと一筆書きの関連性について話したいと思います。結論一筆書きはオイラー路のことです。
オイラー路について復習すると、全ての辺を通るような路がオイラー路でした。これってつまり一筆書きですよね。
つまり一筆書きができるかどうか判断するときは全ての頂点の次数を見て、奇数次数の頂点数が0か2だったら一筆書きで行けるということですね。
おわりに
いかがでしたか。
今回の記事ではオイラー路とハミルトン路について解説していきました。
今後もこのような経営工学に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
