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)

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

閉路をハイライトする：

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

スコープ  (12)

指定  (6)

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

有向グラフに使う：

重み付きグラフ：

多重グラフ：

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

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

一覧  (6)

長さが厳密に8の閉路：

長さが最高で6の閉路：

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

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

すべての閉路を求める：

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

アプリケーション  (4)

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

閉路を示す：

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

頂点を含ませる：

辺を含ませる：

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

最長ループの長さ：

ループを求める：

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

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

特性と関係  (3)

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

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

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

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

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

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

考えられる問題  (1)

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

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_2024_findcycle, author="Wolfram Research", title="{FindCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindCycle.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

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