Est-ce que tout digraphe primitif a un cycle orienté ?

Question

Un digraphe est un graphe orienté.

Un cycle dirigé ou un circuit dirigé simple est un circuit dirigé dans lequel les seuls sommets répétés sont les premier et dernier sommets.

Un digraphe est primitif si sa matrice d'adjacence est primitive.

Une matrice carrée non négative $A$est dit primitif s'il existe un entier positif$k$tel que$A^k >0$(toutes les entrées de$A^k$sont positifs).

J'ai seulement besoin de l'existence d'un chemin avec la structure$i_0 i_1...i_k i_0$(séquence d'arêtes distinctes) avec$k\geq 1$.

Answer 1

Oui. Pour tous$i,j$,$(A^k)_{ij}>0$, donc il y a au moins une marche de longueur$k$de$v_1$à$v_2$et il y a au moins une marche de longueur$k$de$v_2$à$v_1$. Cette promenade dirigée fermée qui va de$v_1$à$v_2$puis retour à$v_1$doit contenir un cycle dirigé non trivial (c'est-à-dire un cycle de longueur au moins égale à 2).