有向閉路グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 02:15 UTC 版)
長さ8の有向閉路グラフ 有向閉路グラフ (英: directed cycle graph) は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。 有向グラフにおいて、それぞれの有向閉路から少なくとも1つの辺（枝）を含んでいる枝集合を帰還枝集合 (feedback arc set) と呼ぶ。同様に、それぞれの有向閉路から少なくとも1つの頂点を含んでいる頂点集合を帰還頂点集合 (feedback vertex set) と呼ぶ。 有向閉路グラフの各頂点は常に入次数が1で、出次数が1である。 有向閉路グラフは、巡回群におけるケイリーグラフである（外部リンクの Trevisan 参照）。 閉路のない有向グラフは有向非巡回グラフ (英: directed acyclic graph) という
※この「有向閉路グラフ」の解説は、「閉路グラフ」の解説の一部です。
「有向閉路グラフ」を含む「閉路グラフ」の記事については、「閉路グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「有向閉路グラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 有向閉路グラフのページへのリンク
