WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

FindHamiltonianCycle[g]

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

詳細とオプション
Details and Options Details and Options
例題  
例  
オプション  
MaxIterations  
RandomSeed  
アプリケーション  
特性と関係  
考えられる問題  
関連項目
テクニカルノート
関連するガイド
引用書式
GraphUtilities`
GraphUtilities`

FindHamiltonianCycle

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

FindHamiltonianCycle[g]

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

詳細とオプション

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

例題

すべて開く すべて閉じる

例  (2)

Wolfram Language code: Needs["GraphUtilities`"]

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

Wolfram Language code: g = {1 -> 3, 1 -> 2, 1 -> 4, 2 -> 3, 2 -> 4};
Wolfram Language code: GraphPlot[g, VertexLabeling -> True]
Wolfram Language code: FindHamiltonianCycle[g]

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

Wolfram Language code: g = UndirectedGraph[Graph[{1 -> 3, 1 -> 2, 1 -> 4, 2 -> 3, 2 -> 4}]]
Wolfram Language code: FindHamiltonianCycle[g][[1, All, 1]]

オプション  (2)

MaxIterations  (1)

Wolfram Language code: Needs["Combinatorica`"]

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

Wolfram Language code: FindHamiltonianCycle[GridGraph[8, 8], MaxIterations -> 5]//Timing
Wolfram Language code: FindHamiltonianCycle[GridGraph[8, 8]]//Timing
Wolfram Language code: FindHamiltonianCycle[GridGraph[8, 8], MaxIterations -> 5]//Timing

RandomSeed  (1)

Wolfram Language code: Needs["Combinatorica`"]

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

Wolfram Language code: FindHamiltonianCycle[GridGraph[10, 10], RandomSeed -> 123]
Wolfram Language code: FindHamiltonianCycle[GridGraph[10, 10]]

アプリケーション  (1)

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

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: g = Flatten[Map[(If[MemberQ[CountryData["SouthAmerica"], #[[1]]] && MemberQ[CountryData["SouthAmerica"], #[[2]]], #, {}])&, Flatten[Thread[# -> CountryData[#, "BorderingCountries"]]& /@ CountryData["SouthAmerica"]]]];
Wolfram Language code: c = FindHamiltonianCycle[g]

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

Wolfram Language code: cs = Transpose[{c, RotateRight[c]}];GraphPlot[g, EdgeRenderingFunction -> (If[MemberQ[cs, #2] || MemberQ[cs, Reverse[#2]], {Red, Thickness[.01], Line[#1]}, {Black, Line[#1]}]&), VertexLabeling -> True, MultiedgeStyle -> False]

特性と関係  (1)

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

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

Wolfram Language code: SeedRandom[123]; g = RandomGraph[500, 0.3];
Wolfram Language code: FindHamiltonianCycle[g]//Short//Timing
Wolfram Language code: HamiltonianCycles[g]//Short//Timing

考えられる問題  (1)

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

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: Needs["Combinatorica`"]
Wolfram Language code: FindHamiltonianCycle[GridGraph[10, 10]]
Wolfram Language code: HamiltonianCycles[GridGraph[10, 10]]
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_2026_findhamiltoniancycle, author="Wolfram Research", title="{FindHamiltonianCycle}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html}", note=[Accessed: 10-August-2026]}

BibLaTeX

@online{reference.wolfram_2026_findhamiltoniancycle, organization={Wolfram Research}, title={FindHamiltonianCycle}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/FindHamiltonianCycle.html}, note=[Accessed: 10-August-2026]}