Graphe Eulérien

Dans cette section, nous allons élaborer un algorithme pour déterminer si un graphe est Eulérien (voir définition 6.1). Nous allons utiliser uniquement le type abstrait centré-sommets.

Nous savons (théorème 6.3, 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. Nous savons (section 9.2) comment déterminer si un graphe est connexe. On peut utiliser l'algorithme suivant pour calculer le nombre de sommets de degré impair :

Algorithme 9.10    
Entrée : Un graphe $G$.
Sortie : Une valeur booléenne indiquant si le nombre de sommets de degré impair est soit zéro soit deux. Algorithme :

1. initialiser un accumulateur $n$ à $0$,
2. utiliser l'opération NB_NODES(G) pour récupérer le nombre de sommets, $\vert V(G)\vert$, de $G$,
3. pour $i$ allant de $0$ à $\vert V(G)\vert - 1$ faire :
   1. utiliser l'opération NODE(G, i) pour récupérer $s$ le sommet numéroté $i$ de $G$.
   2. utiliser l'opération NB_EDGES(s) pour déterminer le degré $d$ de $s$,
   3. si $d$ et impair, alors incrémenter (additionner $1$ à) $n$,
4. si $n = 0$ ou $n=2$ alors renvoyer ``oui'', sinon renvoyer ``non''

La complexité de l'algorithme 9.10 est $O(\vert V(G)\vert)$.