【アルゴリズム】すべての「頂点」を1度だけ巡る！「ハミルトン閉路」｜情報処理問題1000本ノック
アルゴリズムや離散数学における「グラフ理論」。すべての頂点をちょうど1度だけ訪れて元の場所に戻る「ハミルトン閉路」の概念と、関連する重要用語を攻略しましょう。
1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）
【 問題 】 グラフ理論における閉路（スタート地点に戻る経路）に関する記述です。与えられたグラフにおいて、すべての頂点（ノード）をちょうど1度だけ通過して出発点に戻ってくる閉路を何と呼ぶでしょうか？
（ア）ハミルトン閉路（Hamiltonian Cycle）
（イ）オイラー閉路（Eulerian Circuit）
（ウ）最短経路（Shortest Path）
（エ）閉路検出（Cycle Detection）
2. 正解：
正解：（ア）ハミルトン閉路（Hamiltonian Cycle）
3. 解説：「『頂点』を通るのか、『辺』を通るのか？」
ハミルトン閉路（Hamiltonian Cycle）は、数学者ウィリアム・ローワン・ハミルトンにちなんで名付けられたグラフ理論の概念です。
すべての「頂点（点）」を一度だけ踏破する巡路であり、応用問題として有名な**「巡回セールスマン問題（TSP）」**の基礎となる概念でもあります。（※ハミルトン閉路が存在するかどうかを判定する問題は、計算量が膨大になるNP完全問題として知られています。）
| 用語名 | 対象（何を通るか） | 通過条件・特徴 |
|---|---|---|
| （ア）ハミルトン閉路 | すべての「頂点（点）」 | すべての頂点をちょうど1度だけ通ってスタートに戻る。 |
| （イ）オイラー閉路 | すべての「辺（線）」 | すべての辺をちょうど1度だけ通ってスタートに戻る。（一筆書きの完成形） |
1. 理解のコツ: 「観光旅行」と「道路清掃」に例えてみましょう。
・ハミルトン閉路（観光旅行）：全国の「すべての観光都市（頂点）」を重なりなく1回ずつ巡って帰ってくるルートです。使わない道路があっても構いません。
・オイラー閉路（道路清掃）：マップ上の「すべての道路（辺）」を残さず1回ずつ掃除して帰ってくるルート（一筆書き）です。同じ都市（頂点）を何度も通過しても構いません。
2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験の「アルゴリズム」「離散数学」分野で出題されます。
問題文に「すべての頂点を1度だけ」とあれば ➔ ハミルトン閉路
問題文に「すべての辺を1度だけ（一筆書き）」とあれば ➔ オイラー閉路
「頂点」か「辺」かというキーワードを注視して、引っかからずに見分けられるようにしておきましょう！
4. まとめ
グラフ中の「すべての頂点をちょうど1度ずつ通って戻る閉路」がハミルトン閉路です。すべての辺を1度だけ通る「オイラー閉路」との対比を完璧に覚えておきましょう！