世界大百科事典（旧版）内のハミルトン閉路の言及
【アルゴリズム】より
…
[非決定性アルゴリズム]
巡回セールスマン問題に〈すべての都市をちょうど1回ずつ通過し，出発点に戻る〉という条件を追加すると，解が存在しない場合も出てくる。しかしこの条件をみたす経路(いわゆる〈ハミルトン閉路〉)が存在するかどうかは，次のような方針で判定できる。まず最初は指定された出発点にいるとして，次の作業(ア)を繰り返す。…
【数学パズル】より
…図17‐aはアーレンスW.Ahrens著の《数学遊戯》第2巻(1918)にある問題で，かなり複雑そうに見えるけれども，A点とB点だけが奇数の点であることを確認すれば図17‐bのような解が簡単に得られる。一筆書きと似たトポロジーパズルにハミルトン閉路の問題がある。W.R.ハミルトンが考えたもので，その結果を1859年に報告している。…
※「ハミルトン閉路」について言及している用語解説の一部を掲載しています。
出典｜株式会社平凡社「世界大百科事典（旧版）」
Sponserd by 