¿Todo dígrafo primitivo tiene un ciclo dirigido?

Question

Un dígrafo es un gráfico dirigido.

Un ciclo dirigido o circuito dirigido simple es un circuito dirigido en el que los únicos vértices repetidos son el primero y el último vértice.

Un dígrafo es primitivo si su matriz de adyacencia es primitiva.

Una matriz cuadrada no negativa $A$se dice que es primitivo si existe un entero positivo$k$ tal que $A^k >0$ (todas las entradas de $A^k$ son positivas).

Answer 1

Puedes interpretar $(A^n)_{i,j}$ como el número de caminos con longitud $n$ desde el vértice $i$ al vértice $j$.

Desde que tenemos $A^k>0$, también tenemos, para $n\in\mathbb N$, ese $A^{nk}>0$.

Por lo tanto, podemos encontrar caminos de longitud arbitraria en el gráfico, por lo que debe contener un ciclo.