ハミルトン路 Hamiltonian path
ハミルトン路(Hamiltonian path or traceable path)は、無向グラフに含まれる全ての頂点を1度ずつ通るpathのこと。
全ての頂点を1度ずつ通って、再び最初の頂点に戻ってくる閉路のことをハミルトン閉路(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
関連エントリ
・グラフ理論の用語