Graphe fortement connexe et circuits

aoraki · September 2013

Bonjour,

Quelqu'un peut-il me dire si l'affirmation ci-dessous est vraie ou fausse :

Un graphe est fortement connexe si et seulement si il existe un circuit passant par tous les sommets ?

(je crois que l'on appelle un tel circuit un circuit pré-hamiltonien, car il passe par tous les sommets, mais éventuellement plusieurs fois par un sommet donné, alors qu'un circuit hamiltonien passe une seule fois par chaque sommet)

Merci d'avance.

Foys · September 2013

Soit $(E,V)$ un graphe orienté (E fini).

(1) S'il existe un circuit passant par tous les sommets de $E$, et $x,y$ sont dans $E$, il suffit de suivre le circuit à partir de $x$ pour finir par tomber sur $y$.

(2) Si $(E,V)$ est fortement connexe, notons $E=\{x_1,...,x_n\}$. Soit $C_i$ un chemin reliant $x_i$ à $x_{i+1}$ pour $i \leq n-1$ et $C_n$ un chemin reliant $x_n$ à $x_1$. la concaténation de $C_1,...,C_n$ est un circuit parcourant $E$ tout entier.