Loading article…
グラフ理論の数学分野において、ハミルトン路（または追跡可能な経路）とは、無向グラフまたは有向グラフにおいて、各頂点をちょうど一度ずつ通過する経路のことです。ハミルトン閉路（またはハミルトン回路）とは、各頂点をちょうど一度ずつ通過する閉路のことです。隣接する頂点から始まり、隣接する頂点で終わるハミルトン路は、辺を1つ追加することでハミルトン閉路にすることができ、ハミルトン閉路から任意の辺を取り除くとハミルトン路になります。このような経路や閉路がグラフに存在するかどうかを判定する計算問題はNP完全問題です。詳細はハミルトン路問題を参照してください。
ハミルトン経路とハミルトンサイクルは、正十二面体の辺グラフにおけるハミルトンサイクルを見つける問題である二十面体ゲーム（現在はハミルトンのパズルとしても知られる）を考案したウィリアム・ローワン・ハミルトンにちなんで名付けられました。ハミルトンはこの問題を、四元数（これもハミルトンが考案）と多くの類似点を持つ、1の根に基づく代数構造である二十面体計算を用いて解決しました。この解法は任意のグラフには一般化できません。
ハミルトンにちなんで名付けられたにもかかわらず、多面体のハミルトン閉路は、その1年前にトーマス・カークマンによっても研究されており、特に彼はハミルトン閉路を持たない多面体の例を示した。[ 1 ]さらに遡ると、チェス盤のナイトのグラフ、ナイトの巡回におけるハミルトン閉路と経路は、9世紀にインドの数学でルドラタによって、またほぼ同時期にイスラムの数学でアル・アドリ・アル・ルーミーによって研究されていた。18世紀のヨーロッパでは、ナイトの巡回はアブラハム・ド・モアブルとレオンハルト・オイラーによって発表された。[ 2 ]
ハミルトン路（またはトレース可能路）とは、グラフの各頂点をちょうど一度ずつ通過する経路のことです。ハミルトン路を含むグラフはトレース可能グラフと呼ばれます。グラフは、任意の2つの頂点間にハミルトン路が存在する場合、ハミルトン連結であると言います。
ハミルトン閉路、ハミルトン回路、頂点巡回、またはグラフ閉路とは、各頂点をちょうど一度ずつ訪れる閉路のことです。ハミルトン閉路を含むグラフは、ハミルトングラフと呼ばれます。
同様の概念は有向グラフにも定義でき、パスまたはサイクルの各エッジ（弧）は一方向にしかたどることができません（つまり、頂点は矢印で接続され、エッジは「始点から終点へ」たどられます）。
ハミルトン分解とは、グラフをハミルトン回路に分解することである。
ハミルトン迷路は、与えられたグラフの中で唯一のハミルトン閉路を見つけることを目的とする論理パズルの一種です。[ 3 ] [ 4 ]
ハミルトン閉路は、その辺の1つを取り除くことでハミルトン路に変換できるが、ハミルトン路をハミルトン閉路に拡張できるのは、その端点が隣接している場合に限られる。
すべてのハミルトングラフは双連結ですが、双連結グラフが必ずしもハミルトングラフであるとは限りません（例えば、ピーターセングラフを参照）。[ 9 ]
オイラーグラフG (すべての頂点の次数が偶数である連結グラフ) は必ずオイラー巡回路、つまりGの各辺をちょうど 1 回通過する閉路を持ちます。この巡回路は線グラフL ( G )のハミルトン閉路に対応するため、すべてのオイラーグラフの線グラフはハミルトン閉路です。線グラフはオイラー巡回路に対応しない他のハミルトン閉路を持つ場合があり、特に、すべてのハミルトングラフGの線グラフL ( G )は、グラフGがオイラーグラフであるかどうかにかかわらず、それ自体がハミルトン閉路です。[ 10 ]
（2つ以上の頂点を持つ）トーナメントは、強連結である場合に限りハミルトン的である。
n個の頂点を持つ完全無向グラフにおける異なるハミルトン閉路の数は ( n − 1)! / 2 であり、 n個の頂点を持つ完全有向グラフにおける異なるハミルトン閉路の数は( n − 1)!です。これらのカウントは、始点以外は同じ閉路は別々にカウントされないことを前提としています。
ハミルトングラフの頂点次数による最適な特徴付けは、1972 年にボンディ・チャヴァタル定理によって提供されました。これは、GA ディラック(1952 年) とオイスタイン・オレによる以前の結果を一般化したものです。ディラックの定理とオレの定理はどちらも、ポサの定理(1962 年) から導出することもできます。ハミルトン性は、グラフ密度、タフネス、禁止部分グラフ、距離などのさまざまなパラメータに関連して広く研究されています。[ 11 ]ディラックとオレの定理は基本的に、十分なエッジがあればグラフはハミルトンであると述べています。
Bondy–Chvátalの定理は、 n個の頂点を持つグラフGの閉包cl( G )に対して作用します。これは、 deg( v ) + deg( u ) ≥ nを満たす隣接していない頂点ペアuとvを結ぶ新しい辺uvを、この性質を持つペアがなくなるまで繰り返し追加することによって得られます。
ボンディ・チャヴァタル定理（1976年）—グラフがハミルトングラフであるのは、その閉包がハミルトングラフである場合に限る。
完全グラフはハミルトングラフであるため、閉包が完全なグラフはすべてハミルトングラフであり、これはディラックとオレによる以下の以前の定理の内容である。
ディラックの定理（1952年）— n個の頂点を持つ単純グラフ（すべての頂点の次数が であれば、 はハミルトン行列である。またはそれ以上。
以下の定理は、方向性のあるバージョンとみなすことができる。
各無向辺は2つの有向弧に対応するため、頂点の数は2倍にする必要があります。したがって、有向グラフにおける頂点の次数は、無向グラフにおける頂点の次数の2倍になります。
Rahman– Kaykobad (2005) — n個の頂点を持つ単純グラフは、隣接しないすべての頂点ペアについて、それらの次数と最短経路長の合計がnより大きい場合にハミルトン経路を持つ。[ 12 ]
上記の定理は、グラフにおけるハミルトン路の存在を認識することはできるが、ハミルトン閉路の存在を認識することはできない。
これらの結果の多くは、バランスのとれた二部グラフにも類似のものが存在します。バランスのとれた二部グラフでは、頂点の次数はグラフ全体の頂点数ではなく、二部グラフの片側の頂点数と比較されます。[ 13 ]
定理— 4連結平面三角形分割はハミルトン閉路を持つ。[ 14 ]
定理— 4連結平面グラフはハミルトン閉路を持つ。[ 15 ]
与えられた重み付き有向グラフ（弧には特定の基底体からの重みが割り当てられている）のハミルトン閉路の代数的表現は、有向グラフのハミルトン閉路の弧の重みの積の和として定義される、その重み付き隣接行列のハミルトン閉路多項式である。この多項式は、有向グラフがハミルトンである場合に限り、弧の重みの関数として恒等的にゼロではない。これを計算する計算複雑度とパーマネントを計算する計算複雑度の関係は、Grigoriy Kogan によって示された。[ 16 ]
