Plus court chemin cycle

Un cycle de longueur minimale utilise une arête au plus une fois, sinon on pourrait le raccourcir, donc sa longueur ne dépasse pas le nombre d'arêtes.

En effet, pour recouvrir un T (graphe à quatre sommets, un « au centre » relié aux trois autres), il va être difficile d'aller visiter tous les sommets en utilisant au plus une fois chaque arête, sans parler de revenir.

On doit pouvoir le prouver avec une stratégie minimale des déplacements.

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.

Bonjour,

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.

Algorithme simple :

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