ハミルトン閉路（全頂点を1回）
全頂点をちょうど1回ずつ巡る閉路。オイラー（辺）との違いを体感。
頂点をクリック／タップして巡回路を伸ばす。隣の頂点（辺で結ばれた未訪問の頂点）にだけ進める。
いまの路（クリックした順）
—
訪問した頂点
0 / 0
閉路か
—
存在判定
未判定
頂点をクリックして巡回路を作ってみよう。
出発点
訪問済み
未訪問
全探索の解
ハミルトン閉路とは、グラフのすべての頂点をちょうど1回ずつ通って出発点に戻る閉じた道のことです。
辺の有無に従って頂点をたどれるので、隣り合う頂点へだけ進めます。
まず頂点をクリックして自分で巡回路を組み立て、全頂点を1回ずつ巡って戻れるかを試してください。 「全探索」ボタンを押すと、バックトラックでそのグラフにハミルトン閉路が存在するかをコンピュータが判定します。
まず頂点をクリックして自分で巡回路を組み立て、全頂点を1回ずつ巡って戻れるかを試してください。 「全探索」ボタンを押すと、バックトラックでそのグラフにハミルトン閉路が存在するかをコンピュータが判定します。
いま何が起きている？
ここがポイント
- 全「頂点」を1回ずつ＝ハミルトン閉路 ── 各頂点をちょうど1回通り、最後に出発点へ戻る。
- オイラー閉路とは別問題 ── オイラーは全「辺」を1回ずつ通る。対象が頂点か辺かで全く違う。オイラーは次数を見るだけで判定できる。
- 一般には判定が難しい（NP困難） ── ハミルトン閉路の存在判定に効率的な公式はなく、ここでは全パターンをバックトラックで試している。
- 巡回セールスマン問題（TSP）の基礎 ── 各都市を1回ずつ回って戻る最短経路を探す TSP は、重み付きのハミルトン閉路探しそのもの。