GraphUtilities`
GraphUtilities`

FindHamiltonianCycle

バージョン10で，GraphUtilitiesパッケージの機能すべてがWolframシステムに組み込まれた． »

FindHamiltonianCycle[g]

ハミルトン閉路を見付けようとする．

詳細とオプション

  • FindHamiltonianCycleの機能はWolfram言語の組込み関数FindHamiltonianCycleで利用できるようになった．
  • FindHamiltonianCycleを使うためには，まずグラフユーティリティパッケージをロードしなくてはならない．それにはNeeds["GraphUtilities`"]を実行する必要がある．
  • FindHamiltonianCycle[g]はハミルトン閉路が見付からないときは空のリストを返す．
  • FindHamiltonianCycleは入力グラフを無向グラフとみなす．
  • FindHamiltonianCycleではハミルトン閉路を見付けるのにヒューリスティックスを使うので，たとえハミルトン閉路があったとしてもそれが見付かるという保証はない．

例題

すべて開くすべて閉じる

例  (2)

以下で小さいグラフを定義し，そのグラフのハミルトン閉路を見付ける：

この関数の代わりにWolframシステムのFindHamiltonianCycleが使われるようになった：

オプション  (2)

MaxIterations  (1)

次は，ハミルトン閉路を見付けようと試みる最大反復回数を制限する：

RandomSeed  (1)

以下はハミルトン閉路を見付けようとする，デフォルトとは異なるランダムシードを指定する：

アプリケーション  (1)

南米の隣接する国々で構成されているグラフの中で，可能なハミルトン閉路をすべて見付ける：

これら2つの閉路のうちの最初のものを示す．2つ目の閉路は最初の閉路の逆になっているだけである：

特性と関係  (1)

FindHamiltonianCycleはHamiltonianCyclesと異なりヒューリスティックスを使うため，たとえハミルトン閉路があったとしてもそれが見付けられるという保証はない．しかし，大きいグラフでは，1つの閉路を見付けるのにFindHamiltonianCycleの方が速いこともある．

以下で頂点が500個のグラフを定義し，ハミルトン閉路を見付けるのにこの2つの関数を使う：

考えられる問題  (1)

FindHamiltonianCycleはヒューリスティックスを使うため，ハミルトン閉路が存在しても見付けられるという保証はない．

Wolfram Research (2007), FindHamiltonianCycle, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html.

テキスト

Wolfram Research (2007), FindHamiltonianCycle, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html.

CMS

Wolfram Language. 2007. "FindHamiltonianCycle." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html.

APA

Wolfram Language. (2007). FindHamiltonianCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html

BibTeX

@misc{reference.wolfram_2024_findhamiltoniancycle, author="Wolfram Research", title="{FindHamiltonianCycle}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findhamiltoniancycle, organization={Wolfram Research}, title={FindHamiltonianCycle}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html}, note=[Accessed: 18-November-2024 ]}