Algorithmes de référence : Cycle eulérien de multigraphe
Définitions et notations :
Un multigraphe est un graphe non-orienté qui peut avoir plusieurs arêtes pour
une même paire de sommets.
Un cycle ou une chaine dans un multigraphe sont dits eulériens quand ils
contiennent exactement une occurrence de chaque arête du multigraphe. N.B. Voir le problème des ponts de Königsberg
(Euler, 1736)
Théorème : Un multigraphe admet un cycle (resp. une chaine)
eulérien si et seulement si tous ses sommets sont de degré pair. N.B. Ceci s'applique aussi aux graphes "unigraphes", cas
particulier avec un seul exemplaire de chaque arête présente.
schéma algorithmique EULERIEN Donnée : un multigraphe G=(V,E). Résultat : un cycle eulérien C de G, s'il en existe.
// C est un ensemble de sommets, on peut utiliser une pile
C← ∅; Si il existe un sommet de V de degré impaire alors Retourner C;
// Atteint est un ensemble d'arêtes
Atteint← ∅; Tantque Atteint≠E faire
Choisir x∈V tel qu'il existe au moins une arête incidente à x dans
(E−Atteint);
Insérer x dans C; Tantque il existe y tel que xy soit une arête de (E−Atteint)
faire
Ajouter xy à Atteint;
Insérer y dans C;
x← y.
Complexité en linéaire si on considère chacune des opérations
comme élémentaire...
N.B. Voir aussi le problème du postier chinois :
passer au moins une fois dans chaque rue en minimisant la distance pacourue.