Graphe fortement connexe et circuits
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
(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.
Un graphe est fortement connexe ssi il existe un circuit préhamiltonien