AcyclicGraphQ

AcyclicGraphQ[g]
グラフ g が非巡回グラフの場合はTrueを,そうでなければFalseを返す.

詳細詳細

  • ある頂点から始まり同じ頂点で終る経路があるグラフは巡回グラフである.

予備知識
予備知識

  • AcyclicGraphQは,グラフに閉路があるかどうかをチェックする.グラフの閉路(閉路が特定の端点がある明示的な経路を使って設定された場合は回路と呼ぶ方がふさわしい)は,経路の最初のノードが最後のノードと一致するような,連結経路を形成するグラフの辺集合の部分集合である.閉路のないグラフは非巡回グラフと呼ばれるのに対し,1つあるいはそれ以上の閉路を含むグラフは巡回グラフと呼ばれる.AcyclicGraphQは非巡回グラフに対してTrueを返し(自己ループは無視される),その他の場合はFalseを返す.
  • 長さ3の閉路を含まない単純グラフはTriangle-Freeグラフと呼ばれ,長さ4の閉路を含まない単純グラフはSquare-Freeグラフと呼ばれる.このため,非巡回単純グラフは,Triangle-FreeかつSquare-Freeである.また,非ハミルトングラフでもある(つまり,ハミルトン閉路を含まない).
  • 非巡回連結グラフはツリーとして知られている.このため,すべてのツリーは定義上非巡回グラフであり,TreeGraphQAcyclicGraphQConnectedGraphQの論理結合に等しい)を使ってグラフがツリーかどうかを調べることができる.ツリーはコンピュータサイエンスの分野で,特にディスク上のファイルとフォルダのストレッジを含むアルゴリズムとデータ構造の実装に,広く使われている.
  • 必ずしも連結されていない非巡回グラフはフォレストとして知られている.有効辺のあるフォレストは,非巡回有効グラフ(DAG)として,よりよく知られているかもしれない.DAGは,したがって, AcyclicGraphQDirectedGraphQの両方がTrueを返すグラフである.DAGは,電子回路,情報のフロー,エベントとタスクのような,多くの種類の情報のモデル化に重要である.
  • FindCycleを使って,非巡回グラフではないグラフ中の1つあるいは複数の閉路を求めることができる(グラフが非巡回グラフの場合は,空リスト が返される).
2010年に導入
(8.0)