next up previous contents index
suivant: Variations sur les graphes monter: Graphes Eulériens précédent: Parité des sommets   Table des matières   Index

Conditions suffisantes pour un graphe Eulérien

Dans la section précédente, nous avons examiné deux conditions nécessaires pour qu'un graphe soit Eulérien. Mais nous n'avons pas encore de condition suffisante.

Établir des conditions suffisantes est considérablement plus difficile qu'établir des conditions nécessaires, la raison principale étant que les preuves par contradiction sont difficiles à appliquer.

En fait, pour établir des conditions suffisantes, un informaticien préfère une preuve constructive. Essentiellement, une telle preuve indiquera non seulement l'existence d'une chaîne Eulérienne, mais aussi une méthode pour en trouver une. L'informaticien peut alors traduire cette méthode en un algorithme et ultérieurement en un programme pour trouver une telle chaîne.

On s'aperçoit que la réunion des deux conditions nécessaires examinées dans la section précédente forme une condition suffisante. Sans preuve, voici le théorème final :

Théorème 6.3   Un graphe $G$ est Eulérien si et seulement si $G$ est connexe et le nombre de ses sommets impairs est $0$ ou $2$.


next up previous contents index
suivant: Variations sur les graphes monter: Graphes Eulériens précédent: Parité des sommets   Table des matières   Index