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.  funB<>ction EULER(v)
   
   1 		chemin 
   
   2  		pour tous les sommets w adjacents `a v
   
   				et
   
   				toutes les fl`eches (v,w)
   
   				 non encore utilis'ees
   
   		 faiB<>re
   
   3 				marquer (v,w) utilis'ee
   
   4 				chemin  ((v,w), EULER(w), chemin)
   
   5 		end
   
   6 		return(chemin)
   
   7 end EULER
   
   

   euler81mm41mm700calcul d'un circuit