すべての原始有向グラフには有向サイクルがありますか？

Question

有向グラフは有向グラフです。

有向サイクルまたは単純向け回路だけ繰り返さ頂点が最初と最後の頂点であるに向け回路です。

有向グラフは原始的で、その隣接行列が原始的である場合。

正方形の非負行列 $A$正の整数が存在する場合、原始的であると言われます$k$ そのような $A^k >0$ （のすべてのエントリ $A^k$ ポジティブです）。

Answer 1

あなたは解釈することができます $(A^n)_{i,j}$ 長さのあるパスの数として $n$ 頂点から $i$ 頂点へ $j$。

私たちが持っているので $A^k>0$、私たちも持っています、 $n\in\mathbb N$、 それ $A^{nk}>0$。

したがって、グラフ内で任意の長さのパスを見つけることができるため、サイクルが含まれている必要があります。