Est-ce que chaque digraphe primitif a un cycle dirigé?

Question

Un digraphe est un graphe orienté.

Un cycle dirigé ou 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 de contiguïté 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).

Answer 1

Vous pouvez interpréter $(A^n)_{i,j}$ comme le nombre de chemins avec la longueur $n$ du sommet $i$ au sommet $j$.

Depuis que nous avons $A^k>0$, nous avons aussi, pour $n\in\mathbb N$, cette $A^{nk}>0$.

Par conséquent, nous pouvons trouver des chemins de longueur arbitraire dans le graphe, il doit donc contenir un cycle.