ハミルトン閉路（読み）はみるとんへいろ

世界大百科事典（旧版）内のハミルトン閉路の言及

【アルゴリズム】より

…
[非決定性アルゴリズム]
　巡回セールスマン問題に〈すべての都市をちょうど1回ずつ通過し，出発点に戻る〉という条件を追加すると，解が存在しない場合も出てくる。しかしこの条件をみたす経路(いわゆる〈ハミルトン閉路〉)が存在するかどうかは，次のような方針で判定できる。まず最初は指定された出発点にいるとして，次の作業(ア)を繰り返す。…

【数学パズル】より

…図17‐aはアーレンスW.Ahrens著の《数学遊戯》第2巻(1918)にある問題で，かなり複雑そうに見えるけれども，A点とB点だけが奇数の点であることを確認すれば図17‐bのような解が簡単に得られる。一筆書きと似たトポロジーパズルにハミルトン閉路の問題がある。W.R.ハミルトンが考えたもので，その結果を1859年に報告している。…

※「ハミルトン閉路」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」