FindHamiltonianCycle

FindHamiltonianCycle[g]
グラフ g のハミルトン(Hamilton)閉路を求める.

FindHamiltonianCycle[g,k]
最大 k 個のハミルトン閉路を求める.

詳細とオプション詳細とオプション

予備知識
予備知識

  • FindHamiltonianCycle は,他と区別できる1つ以上のハミルトン(Hamilton)閉路(ハミルトン回路と呼ばれることもある)を見付けようと試みる.ハミルトン閉路は,辺リストのリストとして,あるいは見付からない場合にはとして返される.ハミルトン閉路(閉路が特定の端点を持つ明示的な経路を使って識別される場合には,より正しくはハミルトン回路と呼ばれる)は,最初と最後の辺が端点で繋がり,各頂点が厳密に1度だけ現れるような,互いに区別の付く辺の連続する列である.このため,ハミルトン閉路は,長さ のグラフ閉路である.ここで は,グラフ内のノードの数である.ハミルトン閉路は,ゲノム配列を再構築したり,ゲーム(ハミルトンの世界一周ゲーム(Icosian Game)が最も有名)を解いたり,チェス盤上のナイトの巡回を求めたり,正規グラフの魅力的な円状の埋込みを求めたりするのに使われる.ハミルトン閉路を含むグラフはハミルトングラフとして知られる.
  • FindHamiltonianCycle[g,k]は,k 個のハミルトン回路を求めようと試みる.回数指定 k は省略する(その場合には1であると見なされる)場合も,正の整数の場合も,あるいはAllになる場合もある.
  • ハミルトン閉路を求めることは,NP完全問題である.しかし,ハミルトン閉路を非常に素早く求めることができる(ただしいつもそうであるとは限らない)さまざまな発見的アルゴリズムが存在する.このことから,グラフ内の頂点を置換するだけで,FindHamiltonianCycleのランタイムが大きく異なる場合がある.数多くのMethodオプションをFindHamiltonianCycleに指定(デフォルトはAutomatic)できることがある.
  • グラフがハミルトン経路かどうかはHamiltonianGraphQを使って調べることができる.FindShortestTourは,グラフ(より一般的にいうなら指定された頂点集合)上の単一のハミルトン経路を求めようと試みる別の関数である.この関数はFindHamiltonianCycleよりも速く成功することがある点で有利である.
  • 個のノードを持つグラフ内のハミルトン閉路は,長さ の閉路に対応するが,任意長の閉路はFindCycleを使って求められる場合がある.ハミルトン閉路はすべての頂点を訪れるが,すべての辺を通るとは限らない.すべての辺を厳密に1度だけ通る閉路は,オイラー(Euler)回路であり,FindEulerianCycleを使って求めることができる.
2010年に導入
(8.0)
| 2014年に修正
(10.0)