書記が数学やるだけ#621 ハミルトングラフ

全ての頂点を1度ずつ通ることのできるグラフについて。

問題

説明

全ての頂点を1度ずつ通ることのできる閉路をハミルトングラフといい，必要十分条件がわかっていないなど，オイラーグラフと比べると未解決な部分が多い。また，巡回セールスマン問題はNP困難に属している。

解答

まずは必要条件から。

これの対偶で，ハイミトングラフでない条件を絞ることができる。

次に十分条件，これはオーレの定理（1960年に証明）と呼ばれる条件である。

これはディラックの定理の一般化と言える。

それぞれの条件について，逆は成立しないことを反例により示す。

チェスのナイトを用いたパズルで，全てのマスを訪問し最初のマスに戻れるか考える。全ての手を考えるまでもなく，今までの知識で不可能であることがわかる。

本記事のもくじはこちら：