この用語はまだ監査を通っていません（未確認）。
ハミルトン路
はみるとんろ ／ ハミルトン経路 1対1で対応Hamiltonian path
名詞 ・話し言葉・書き言葉 別の言い方 Hamilton path
定義
グラフのすべての頂点をちょうど 1 回ずつ通る経路のこと。始点に戻るものはハミルトン閉路という。
A path in a graph that visits every vertex exactly once. If it also returns to its starting vertex, it is called a Hamiltonian cycle.
例文
話し言葉 An Euler trail uses every edge once, but a Hamiltonian path visits every vertex once, and that's a much harder thing to check. 一筆書きはすべての辺を 1 回ずつ通るが、ハミルトン路はすべての頂点を 1 回ずつ通る。こちらのほうがずっと判定が難しい。
書き言葉・答案 Does the graph below have a Hamiltonian path? If so, list the vertices in order. If not, explain why. 下のグラフにハミルトン路はあるか。あれば通る頂点を順に書き、なければその理由を説明せよ。
言い間違えやすいところ
- 一筆書き（Euler trail）は辺を、ハミルトン路は頂点を 1 回ずつ通る。取り違えやすい。
- 一筆書きには頂点の次数で判定できる簡単な条件があるが、ハミルトン路があるかどうかを判定する簡単な条件は知られていない。
- 人名なので大文字の H で書く。用例コーパスでは Hamiltonian path が話し言葉（MIT OCW）・書き言葉（MIT の講義ノート）とも使われる。Levin の本は Hamilton path と書く（18 件。Hamiltonian path は 1 件、2.4 Euler Trails and Circuits）。