next up previous contents index
suivant: Cas centré-sommets monter: Programmation sur les graphes précédent: Cas centré-arêtes   Table des matières   Index

Graphe Eulérien

Nous avons vu Section 6.4 que pour qu'un graphe soit Eulérien, il doit être connexe et le nombre de ses sommets de degré impair doit être zéro ou deux (théorème 6.3).

Nous allons écrire une fonction eulerian(G) qui retourne 1 (vrai) si le graphe G est Eulérien et 0 (faux) sinon.

Nous disposons déjà de la fonction connected(G) pour déterminer si le graphe est connexe. Si le graphe n'est pas connexe on peut immédiatement renvoyer 0. Sinon, il ne reste plus qu'à examiner le nombre de sommets impairs de G. On va les compter. Dès qu'on en a compté strictement plus de 2 on peut renvoyer 0. Si la boucle se termine sans qu'on ait renvoyé 1 alors n contient le nombre total de sommets impairs et on est sûr que n vaut 0 ou 2 puisque le nombre de sommets impairs est forcément pair. Il suffit donc de renvoyer 1.



Sous-sections