ハミルトン路 Hamiltonian path

ハミルトン路(Hamiltonian path or traceable path)は、無向グラフに含まれる全ての頂点を1度ずつ通るpathのこと。
全ての頂点を1度ずつ通って、再び最初の頂点に戻ってくる閉路のことをハミルトン閉路(Hamiltonian cycle)と言う。

■ハミルトン閉路(Hamiltonian cycle)の例

■正12面体のハミルトン閉路のオブジェ

http://sacredgeometry.tribe.net/thread/52febe0f-ec03-4a3f-af5c-fc0937c0aa89

ハミルトン路が存在するか判定する問題はNP困難であることが知られている。


インターネットでいろいろ調べていたら、ちょっと面白い図があった。
エッシャーの絵画に登場するタイリングパターンのハミルトン路

The Cayley graph of the group [6,4] with a Hamiltonian path
http://www.ams.org/notices/200304/fea-escher.pdf


似ているけど違うものとして、オイラー路(Eulerian trail or Eulerian path )がある。こちらは、全ての「辺」を1度通る路のこと。
オイラー路の有無は、頂点に接続する辺の数を調べることですぐに判定できる。


(Hamiltonian pathと呼ばずにtraceable pathとしてくれたら、どんなpathかすぐにイメージできるのだけど。。)

[参考]
日本語版Wiki:ハミルトン路
英語版Wiki:Hamiltonian path
日本語版Wiki:オイラー路
英語版Wiki:Eulerian path

関連エントリ
グラフ理論の用語

グラフ理論入門離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)グラフ理論入門 (数理科学ライブラリ (2))数学をいかに使うか (ちくま学芸文庫)