Todo dígrafo primitivo tem um ciclo direcionado?

Question

Um dígrafo é um gráfico direcionado.

Um ciclo direcionado ou circuito direcionado simples é um circuito direcionado no qual os únicos vértices repetidos são o primeiro e o último vértices.

Um dígrafo é primitivo se sua matriz de adjacência for primitiva.

Uma matriz quadrada não negativa $A$é dito primitivo se existir um inteiro positivo$k$ de tal modo que $A^k >0$ (todas as entradas de $A^k$ são positivos).

Answer 1

Você pode interpretar $(A^n)_{i,j}$ como o número de caminhos com comprimento $n$ do vértice $i$ ao vértice $j$.

Uma vez que temos $A^k>0$, também temos, para $n\in\mathbb N$, este $A^{nk}>0$.

Portanto, podemos encontrar caminhos de comprimento arbitrário no gráfico, portanto, ele deve conter um ciclo.