Todo dígrafo primitivo tem um ciclo direcionado?

Question

Um dígrafo é um grafo 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 ser primitivo se existe um inteiro positivo$k$de tal modo que$A^k >0$(todas as entradas de$A^k$são positivos).

Preciso apenas da existência de um caminho com a estrutura$i_0 i_1...i_k i_0$(sequência de arestas distintas) com$k\geq 1$.

Answer 1

Sim. Para todos$i,j$,$(A^k)_{ij}>0$, então há pelo menos uma caminhada de comprimento$k$a partir de$v_1$para$v_2$e há pelo menos uma caminhada de comprimento$k$a partir de$v_2$para$v_1$. Esta caminhada dirigida fechada que vai de$v_1$para$v_2$e depois de volta para$v_1$deve conter um ciclo direcionado não trivial (ou seja, um ciclo de comprimento de pelo menos 2).