WOLFRAM

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

FindHamiltonianPath[g]

グラフ g 中の最短のハミルトン(Hamilton)路を求める．

FindHamiltonianPath[g,s,t]

s から t までの最短のハミルトン路を求める．

詳細とオプション
Details and Options Details and Options
例題  
例  
スコープ  
オプション  
DistanceFunction  
アプリケーション  
特性と関係  
関連項目
関連するガイド
履歴
引用書式

FindHamiltonianPath

FindHamiltonianPath[g]

グラフ g 中の最短のハミルトン(Hamilton)路を求める．

FindHamiltonianPath[g,s,t]

s から t までの最短のハミルトン路を求める．

詳細とオプション

  • FindHamiltonianPathは，ハミルトン路問題としても知られている．
  • ハミルトン路は各頂点を厳密に1度訪れる．
  • FindHamiltonianPathは，ハミルトン路が存在しない場合はリスト{}を返す．

例題

すべて開く すべて閉じる

例  (2)

グラフ中の頂点を通るハミルトン路を求める：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindHamiltonianPath[g]

経路をハイライトする：

Wolfram Language code: HighlightGraph[g, PathGraph[%]]

グラフ中の2つの別々の頂点間のハミルトン路を求める：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindHamiltonianPath[g, 1, 5]

経路をハイライトする：

Wolfram Language code: HighlightGraph[g, PathGraph[%]]

スコープ  (3)

FindHamiltonianPathは無向グラフに使うことができる：

Wolfram Language code: FindHamiltonianPath[[image]]

重み付きグラフ：

Wolfram Language code: FindHamiltonianPath[[image]]

FindHamiltonianPathは大きいグラフに使うことができる：

Wolfram Language code: g = RandomGraph[{1000, 5000}];
Wolfram Language code: Timing[FindHamiltonianPath[g]]//Short

オプション  (1)

DistanceFunction  (1)

次は，6点間の疎な距離行列を定義する：

Wolfram Language code: d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1, {5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} -> 10, {3, 5} -> 1, {5, 3} -> 1, {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} -> 1}, {6, 6}, Infinity];
Wolfram Language code: g = [image];

ハミルトン路を求める：

Wolfram Language code: path = FindHamiltonianPath[g, DistanceFunction -> (d[[#1, #2]]&)]

経路をハイライトする：

Wolfram Language code: HighlightGraph[g, PathGraph[path]]

アプリケーション  (2)

8×8のチェス盤上で，各正方形を厳密に1度訪れるチェスの駒のナイトの連続する動きを求める：

Wolfram Language code: g = KnightTourGraph[8, 8];
Wolfram Language code: path = FindHamiltonianPath[g]

ナイトの動き：

Wolfram Language code: checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 8}, {j, 8}], ColorRules -> {1 -> RGBColor[0, .55, .77], 0 -> RGBColor[.67, .9, .99]}, Frame -> False, DataRange -> {{1, 8}, {1, 8}}];
Wolfram Language code: Show[{checkerboard, HighlightGraph[g, PathGraph[path], GraphHighlightStyle -> "DehighlightHide", EdgeStyle -> Directive[Thick, Red]]}]

ヨーロッパのギリシャからドイツまでのハミルトン路を求める：

Wolfram Language code: europe = CountryData["Europe"];

地理的中心の経緯度：

Wolfram Language code: pos = GeoPosition[CountryData[#, "CenterCoordinates"]]& /@ europe;

ヨーロッパの重み付きグラフを構築する：

Wolfram Language code: adj = Table[QuantityMagnitude@GeoDistance[i, j], {i, pos}, {j, pos}] /. Quantity[0., _] -> Infinity;
Wolfram Language code: g = WeightedAdjacencyGraph[europe, adj];
Wolfram Language code: FindHamiltonianPath[g, Entity["Country", "Greece"], Entity["Country", "Germany"]]//Shallow

ツアーを示す：

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[%]}]

特性と関係  (2)

ハミルトン路を含むグラフがハミルトン閉路を含まないことがある：

Wolfram Language code: g = [image];
Wolfram Language code: FindHamiltonianPath[g]
Wolfram Language code: HamiltonianGraphQ[g]

ハミルトン閉路を含むグラフはハミルトン路を含む：

Wolfram Language code: g = GraphData["Foster038A"]
Wolfram Language code: HamiltonianGraphQ[g]
Wolfram Language code: FindHamiltonianPath[g]
Wolfram Research (2015), FindHamiltonianPath, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

テキスト

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

CMS

Wolfram Language. 2015. "FindHamiltonianPath." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

APA

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

BibTeX

@misc{reference.wolfram_2026_findhamiltonianpath, author="Wolfram Research", title="{FindHamiltonianPath}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}", note=[Accessed: 16-August-2026]}

BibLaTeX

@online{reference.wolfram_2026_findhamiltonianpath, organization={Wolfram Research}, title={FindHamiltonianPath}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}, note=[Accessed: 16-August-2026]}