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

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$.

따라서 그래프에서 임의의 길이의 경로를 찾을 수 있으므로 순환을 포함해야합니다.