WOLFRAM

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

FindCycle[g]

グラフ g 中の閉路を求める．

FindCycle[g,k]

グラフ g 中で長さが最高で k の閉路を求める．

FindCycle[g,{k}]

長さが厳密に k である閉路を求める．

FindCycle[g,{kmin,kmax}]

長さが kminから kmaxまでである閉路を求める．

FindCycle[g,kspec,s]

最高で s 本の閉路を求める．

FindCycle[{g,v},…]

頂点 vを含む閉路を求める．

FindCycle[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細
Details and Options Details and Options
予備知識
例題  
例  
スコープ  
指定  
一覧  
アプリケーション  
特性と関係  
考えられる問題  
関連項目
関連するガイド
履歴
引用書式

FindCycle

FindCycle[g]

グラフ g 中の閉路を求める．

FindCycle[g,k]

グラフ g 中で長さが最高で k の閉路を求める．

FindCycle[g,{k}]

長さが厳密に k である閉路を求める．

FindCycle[g,{kmin,kmax}]

長さが kminから kmaxまでである閉路を求める．

FindCycle[g,kspec,s]

最高で s 本の閉路を求める．

FindCycle[{g,v},…]

頂点 vを含む閉路を求める．

FindCycle[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細

  • 閉路は，巡回あるいはループとしても知られている．
  • 閉路は，始点と終点以外で頂点あるいは辺を繰り返すことがない経路のことである．
  • FindCycleは閉路のリストを与える．各閉路は辺のリストとして与えられる．
  • FindCycleは閉路がない場合は空リストを返す．
  • FindCycle[g,kspec,All]はすべての閉路を求める．
  • 重み付きのグラフについては，FindCycle[g,k]は，重みの合計が k より小さいすべての閉路を与える．
  • FindCycleは，無向グラフ，有向グラフ，多重グラフに使うことができる．

予備知識

  • FindCycleは，グラフ内の1つ以上の他と異なる閉路を見付けようと試みる．閉路は，辺リストのリストとして，あるいは見付からない場合には{}として返される．グラフの閉路（閉路が特定の端点を持つ明示的な経路を使って識別される場合には，より正しくは回路と呼ばれる）は，最初と最後の辺が端点で繋がる，互いに区別の付く辺の連続する列である．閉路の列挙は，数多くの状況（地下鉄，道路マップ等）での巡回経路を計画したり，電気回路の電圧や電流を計算したり，コンピュータプログラムにおける無限ループを発見したりするのに使える．
  • 一般に，FindCycle[g,kspec,s]は，長さ kspec の s 個の閉路を求めようと試みる．回数指定 s は，省略する（その場合には1であるとみなされる）場合も，正の整数の場合も，あるいはAllになる場合もある．長さの指定 kspec は，正の整数 k（その場合には，長さが k 以下の閉路を表す），Infinity，リスト{k}内の正の整数（その場合は長さが厳密に k である閉路を表す），2つの正の整数のリスト{kmin,kmax}（その場合は，長さが kmin から kmax までの閉路を表す）のいずれかである．
  • FindCycle[g,{3}]が{}を返すグラフは，三角形を持たないグラフであり，FindCycle[g,{4}]が{}を返すグラフは，正方形を持たないグラフである．長さ n の閉路（n はグラフの頂点数）はハミルトン(Hamiltonian)閉路であり，そのような閉路を持つグラフはハミルトングラフである．
  • 閉路を持たないグラフは，非巡回グラフと呼ばれ，AcyclicGraphQを使って調べることができる．
  • FindCycleは単純な閉路を返し，FindHamiltonianCycle，FindEulerianCycle，FindFundamentalCyclesは特定のタイプの閉路を返す．FindPathは，2つの特定の頂点間の経路（端点が一緒ではない辺の集合）を求めるのに使われ，結果は経路に沿った連続する頂点の集合として返される．

例題

すべて開く すべて閉じる

例  (2)

グラフ中の閉路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: FindCycle[g]

閉路をハイライトする：

Wolfram Language code: HighlightGraph[g, %]

グラフ中のすべての閉路を求める：

Wolfram Language code: g = WheelGraph[4];
Wolfram Language code: FindCycle[g, Infinity, All]

スコープ  (12)

指定  (6)

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

Wolfram Language code: FindCycle[[image]]

有向グラフに使う：

Wolfram Language code: FindCycle[[image]]

重み付きグラフ：

Wolfram Language code: FindCycle[[image]]

多重グラフ：

Wolfram Language code: FindCycle[[image]]

規則を使ってグラフを指定する：

Wolfram Language code: FindCycle[{2 -> 1, 1 -> 4, 3 -> 2, 2 -> 5, 6 -> 3, 5 -> 4, 4 -> 7, 6 -> 5, 8 -> 5, 6 -> 9, 7 -> 8, 7 -> 10, 9 -> 8, 11 -> 8, 12 -> 9, 10 -> 11, 12 -> 11}]

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

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: FindCycle[g]//Short//Timing

一覧  (6)

長さが厳密に8の閉路：

Wolfram Language code: FindCycle[[image], {8}]

長さが最高で6の閉路：

Wolfram Language code: FindCycle[[image], 6]

長さが3から5までの閉路：

Wolfram Language code: FindCycle[[image], {3, 5}]

指定された頂点を含む閉路：

Wolfram Language code: FindCycle[{[image], 8}]

すべての閉路を求める：

Wolfram Language code: FindCycle[[image], Infinity, All]//Short

FindCycleは，閉路がない場合は空リストを返す：

Wolfram Language code: FindCycle[[image]]

アプリケーション  (4)

各頂点を厳密に1回訪れるハミルトン(Hamiltonian)閉路を求める：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"]
Wolfram Language code: FindCycle[g, {VertexCount[g]}]

閉路を示す：

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

指定された特性を持つ閉路を求める：

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

頂点を含ませる：

Wolfram Language code: FindCycle[{g, 1}]

辺を含ませる：

Wolfram Language code: cycles = FindCycle[g, Infinity, All];
Wolfram Language code: Select[cycles, MemberQ[#, 52 | 25]&]//Short

韓国釜山の地下鉄の，最長ループを求める：

Wolfram Language code: busan = [image];

最長ループの長さ：

Wolfram Language code: allloops = FindCycle[busan, Infinity, All];
Wolfram Language code: Max[Length /@ allloops]

ループを求める：

Wolfram Language code: Short[loop = Select[allloops, (Length[#] == %)&]]
Wolfram Language code: HighlightGraph[busan, loop]

犬の散歩コースを計画する：

Wolfram Language code: g = [image];

指定された出発点のノードについて，長さが最低でも20で，危険な犬がいる通りを避けた，5通りの散歩コースを求める：

Wolfram Language code: walks = FindCycle[{EdgeDelete[g, {1216, 23, 1318, 2127}], "Home"}, {20, Infinity}, 5]
Wolfram Language code: HighlightGraph[g, walks[[1]]]

特性と関係  (3)

FindHamiltonianCycleを使って各頂点を厳密に1回訪れる閉路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: FindHamiltonianCycle[g]

これは，次と等価である：

Wolfram Language code: FindCycle[g, {VertexCount[g]}]

EdgeCycleMatrixはすべての閉路の基底を与える：

Wolfram Language code: g = WheelGraph[4]
Wolfram Language code: basis = Pick[EdgeList[g], #, 1] & /@ EdgeCycleMatrix[g]

すべての閉路を構築する：

Wolfram Language code: addedges[edges_] := Cases[Tally[Flatten[edges]], {e_, _ ? OddQ} :> e]
Wolfram Language code: cycles = addedges[Pick[basis, #, 1]]& /@ Most[Tuples[{1, 0}, 3]]

FindCycleからすべての閉路を求める：

Wolfram Language code: FindCycle[g, Infinity, All]

FindCycleは，非巡回グラフについては空リストを与える：

Wolfram Language code: g = GraphData[{"CayleyTree", {3, 4}}]
Wolfram Language code: AcyclicGraphQ[g]
Wolfram Language code: FindCycle[g]

考えられる問題  (1)

FindCycleは自己ループを無視する：

Wolfram Language code: g = [image];
Wolfram Language code: FindCycle[g]
Wolfram Research (2014), FindCycle, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindCycle.html （2015年に更新）.

テキスト

Wolfram Research (2014), FindCycle, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindCycle.html （2015年に更新）.

CMS

Wolfram Language. 2014. "FindCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindCycle.html.

APA

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

BibTeX

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

BibLaTeX

@online{reference.wolfram_2026_findcycle, organization={Wolfram Research}, title={FindCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindCycle.html}, note=[Accessed: 01-November-2026]}