모든 원시 digraph에는 방향성주기가 있습니까?

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$, 따라서 적어도 한 걸음의 길이가 있습니다. $k$ ...에서 $v_1$ ...에 $v_2$ 그리고 적어도 한 걸음의 길이가 있습니다 $k$ ...에서 $v_2$ ...에 $v_1$. 이 닫힌 감독 산책은$v_1$ ...에 $v_2$ 그리고 다시 $v_1$ 사소하지 않은 방향성주기를 포함해야합니다 (즉, 길이가 2 이상인주기).