ハミルトン閉路とは？
はみるとんへいろ
ハミルトン閉路とは、グラフ理論においてすべての頂点をちょうど一度ずつ通り、出発点に戻ってくる経路のことです。
ハミルトン閉路（ハミルトン回路）とは、グラフ理論における概念で、グラフ内のすべての頂点をちょうど一度ずつ訪問し、最終的に出発点に戻ってくるような閉じた経路（サイクル）のことを指します。アイルランドの数学者ウィリアム・ローワン・ハミルトンにちなんで命名されました。
ハミルトン閉路が存在するかどうかを判定する問題は「ハミルトン閉路問題」と呼ばれ、計算量理論においてNP完全問題に分類されます。これは、頂点数が増えると総当たり以外の効率的な解法が現在のところ知られていないことを意味します。
関連する重要な概念として次のものがあります。
- ハミルトン路：すべての頂点を一度ずつ通るが出発点に戻らない経路
- オイラー閉路：すべての辺を一度ずつ通る閉路（ハミルトン閉路とは異なる）
- 巡回セールスマン問題（TSP）：重み付きグラフで最小コストのハミルトン閉路を求める最適化問題
ハミルトン閉路の概念は、物流の配送ルート最適化・回路基板の配線設計・ゲノム解析（DNA配列の組み立て）など、実用的な問題に深く結びついています。
使い方・例文
複数の都市を一度ずつ訪問して出発地に戻る最短ルートを求める「巡回セールスマン問題」は、ハミルトン閉路の典型的な応用例です。都市の数が増えるにつれて計算が爆発的に難しくなるため、実用上は近似アルゴリズムが活用されます。
この用語をシェア
最終更新: