Exercices (pc 8)

Exercice 1

1. Soit C un circuit maximal dans G ne passant pas deux fois par la même flèche. Le graphe obtenu en supprimant les flèches de C satisfait encore la condition. Soit H une composante connexe de ce graphe. En raisonnant par récurrence, on peut trouver un circuit eulérien D dans H. Les circuits C et D doivent avoir un sommet en commun. Ceci permet de construire un circuit eulérien plus long que C. Donc H est vide.

2.

function EULER(v)
1  chemin ← ∅
2 pour tous les sommets w adjacents à v

et

         toutes les flèches (v, w)
         non encore utilisées

faire

3    marquer (v, w) utilisée
4    chemin ← ((v, w), EULER(w), chemin)

5 end

6 return(chemin)
7 end EULER

euler81mm41mm700calcul d’un circuit