¿Todo dígrafo primitivo tiene un ciclo dirigido?

Question

Un dígrafo es un grafo 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.

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 positivos).

Solo necesito la existencia de un camino con la estructura.$i_0 i_1...i_k i_0$(secuencia de bordes distintos) con$k\geq 1$.

Answer 1

Sí. Para todos$i,j$,$(A^k)_{ij}>0$, por lo que hay al menos un paseo de longitud$k$de$v_1$a$v_2$y hay al menos un paseo de longitud$k$de$v_2$a$v_1$. Este paseo dirigido cerrado que va desde$v_1$a$v_2$y luego de vuelta a$v_1$debe contener un ciclo dirigido no trivial (es decir, un ciclo de al menos 2).