Plus court chemin cycle
Bonjour,
Je pense qu'il s'agit d'une question facile, mais je voulais m'assurer que la longueur d'un plus court cycle qui passe par chaque arête dans un graphe est toujours inférieure à deux fois le nombre d'arêtes.
Merci,
Manu
Je pense qu'il s'agit d'une question facile, mais je voulais m'assurer que la longueur d'un plus court cycle qui passe par chaque arête dans un graphe est toujours inférieure à deux fois le nombre d'arêtes.
Merci,
Manu
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
As-tu un argument simple qui permet de dire que l'on pourrait le raccourcir sinon ?
Merci !
1) si l'on doit joindre un ou plusieurs sommets reliés par un seul chemin en impasse, on fait un aller retour jusqu'au bout, on efface le ou les sommets atteints et la ou les arêtes, le reste du graphe est un graphe. Notons que dans ce cas le sommet depuis lequel on est parti pour l'aller retour est forcément raccordé au graphe.
2) si l'on doit joindre un sommet qui n'est pas sur un chemin en impasse, on efface l'arête franchie et éventuellement le sommet quitté si celui ci n'a plus d'arêtes. Le reste du graphe est un graphe.
On peut par exemple raisonner par récurrence sur le nombre $n$ d'arêtes du graphe.
Soit donc à prouver la propriété suivante:
"$\forall n \in \N^*$, tout graphe simple connexe dont le nombre d'arêtes vaut $n$, possède un circuit de longueur inférieure à $2n$ qui parcourt toutes ses arêtes".
La propriété est claire pour $n=1$.
Soit $n >1$ et $G= (V,E)$ un graphe simple connexe tel que $\#E = n$ .$\:\:(V$ est l'ensemble des sommets de $G$, $E$ celui de ses arêtes.$)$
$\bullet$ Si $G$ ne possède aucun cycle ( c'est à dire si $G$ est un arbre), alors: $\:\exists\: a, b \in V$ tels que $\text{deg}(a) = 1$, $\text{deg }(b)>1$ et $\{a,b\} \in E.$
Alors on peut appliquer l'hypothèse de récurrence au graphe $G_1:= \big(V \setminus \{a\}, E \setminus \{a,b\}\big)$ qui est connexe. En insérant un "aller-retour" $b-a-b$ dans le circuit de $G_1$ défini par l'hypothèse de récurrence, on obtient un circuit de $G$ qui possède toutes les propriétés voulues.
$\bullet$ Si $G$ possède au moins un cycle, alors $\exists \:a,b \in V$ tels que $\{a,b\}$ est un élément de ce cycle et on peut appliquer l'hypothèse de récurrence au graphe $G_1:= \big( V, E \setminus \{a,b\}\big)$ qui est encore connexe et on conclut comme dans le cas précédent.
Imaginons maintenant un petit bonhomme dans le graphe ( chambres et couloirs). Quelle stratégie peut il adopter pour être sûr de passer au moins une fois et au plus 2 fois dans chaque couloir ? Il est placé au départ dans une chambre et il ne connait pas les lieux.
1) Avancer (de façon arbitraire, mais sans revenir sur ses pas) jusqu'à atteindre un cul de sac ou une pièce déjà visitée,
2) Revenir sur ses pas jusqu'à atteindre un croisement avec un chemin non visité ou dans la chambre de départ,
3) Si il n'y a pas de chemin non visité, on a fini, sinon, retour à l'étape 1)
On passera alors exactement deux fois dans chaque couloir
Pour que le petit bonhomme ne s'égare pas, il lui suffit de numéroter ses parcours ALLER dans l'ordre, ses trajets RETOUR seront facilités.