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

Question

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

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

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

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

構造のあるパスの存在だけが必要です $i_0 i_1...i_k i_0$ （異なるエッジのシーケンス） $k\geq 1$。

Answer 1

はい。すべてのために$i,j$、 $(A^k)_{ij}>0$、したがって、少なくとも1つの長さの歩行があります $k$ から $v_1$ に $v_2$ 少なくとも1歩の長さがあります $k$ から $v_2$ に $v_1$。から行くこの閉じた指示された散歩$v_1$ に $v_2$ その後、 $v_1$ 自明ではない有向サイクル（つまり、少なくとも2つの長さのサイクル）が含まれている必要があります。