Détecteur de Chemin Eulérien

Pseudocode

Le test d'existence est un pur comptage et tient en une passe. Ce n'est que s'il réussit que tu construis le parcours, avec Hierholzer plutôt qu'un retour sur trace naïf.

// Existence, graphe non oriente connexe:
//   0 sommet de degre impair -> circuit eulerien
//   2 sommets de degre impair -> chemin eulerien
//   tout autre cas            -> ni l un ni l autre

Hierholzer(graphe, depart):
    pile = [depart]; parcours = []

    tant que la pile est non vide:
        u = pile.sommet
        si u a une arete incidente inutilisee (u,v):
            marquer cette arete comme utilisee
            pile.empiler(v)
        sinon:
            parcours.ajouter(pile.depiler())

    inverser(parcours)

Hierholzer fonctionne parce qu'il n'a jamais à deviner. Il avance jusqu'à se bloquer, ce qui dans un graphe à degrés tous pairs ne peut arriver qu'au sommet de départ, puis greffe des détours depuis les sommets ayant encore des arêtes inutilisées. Chaque sommet est entré et quitté le même nombre de fois, ce que garantit exactement le degré pair, si bien que les morceaux fusionnent toujours en un unique parcours fermé.

Exemple détaillé, étape par étape

Construis un circuit eulérien sur deux triangles partageant un unique sommet, en prenant les voisins par ordre alphabétique.

Graphe d'exemple: Arêtes non orientées A-B, B-C, C-A formant un triangle, et C-D, D-E, E-C formant un second, reliés par C.

1. Vérifier d'abord les degrés. A est de degré 2, B de 2, C de 4, D de 2 et E de 2. Tous les degrés sont pairs et le graphe est connexe, un circuit eulérien existe donc et peut commencer n'importe où.
2. Avancer jusqu au blocage. Depuis A prends A-B, puis B-C, et depuis C prends C-A. Te voilà de retour en A dont les deux arêtes sont utilisées, la marche est donc bloquée. Note qu'elle s'est bloquée au sommet de départ, ce que les degrés pairs rendent inévitable.
3. Greffer le second triangle. En dépilant on atteint C, qui conserve les arêtes inutilisées C-D et C-E. Parcours C-D, puis D-E, puis E-C, et C est désormais épuisé lui aussi.
4. Dérouler jusqu au parcours. Aucune arête inutilisée ne subsistant nulle part, la pile se vide dans l'ordre et le résultat inversé constitue le circuit.

Le circuit eulérien est A vers B vers C vers D vers E vers C vers A, utilisant les six arêtes exactement une fois et revenant au départ. Note que C apparaît deux fois dans le parcours, ce qui est autorisé et attendu: un parcours eulérien peut revisiter librement les sommets, la seule chose interdite est de réutiliser une arête. C'est toute la différence avec un chemin hamiltonien, qui visite chaque sommet une fois et ne se soucie pas des arêtes.

Complexité et son origine

Temps: O(V + E) · Espace: O(V + E)

Le comptage des degrés est une passe sur les arêtes en O(E), et la vérification de connexité un parcours en O(V + E). Hierholzer empile et dépile chaque occurrence de sommet une fois et marque chaque arête utilisée exactement une fois, il est donc en O(E) à condition que chaque sommet conserve un pointeur dans sa liste d'adjacence au lieu de la reparcourir depuis le début. Sans ce pointeur, la recherche interne dégénère en O(V·E). L'espace tient aux marques d'arêtes utilisées ainsi qu'à la pile et au parcours, qui contiennent O(E) entrées. Le contraste avec les chemins hamiltoniens mérite d'être noté: l'eulérien est linéaire, l'hamiltonien est NP-complet, uniquement parce que les arêtes se comptent localement par degré alors que les sommets non.

Quand utiliser Chemin Eulérien (Graphe Non Dirigé), et quand l'éviter

Les problèmes eulériens sont faciles; les problèmes hamiltoniens, superficiellement semblables, ne le sont pas. Vérifie lequel tu as réellement.

Pièges fréquents

• Oublier l exigence de connexité. Les degrés pairs ne suffisent pas à eux seuls. Un graphe formé de deux triangles disjoints a tous ses degrés pairs et aucun circuit eulérien, car aucun parcours ne peut sauter entre composantes. Toutes les arêtes doivent appartenir à une unique composante connexe, et les sommets isolés de degré zéro peuvent être ignorés sans problème.
• Confondre eulérien et hamiltonien. L'eulérien utilise chaque arête une fois et peut répéter des sommets; l'hamiltonien visite chaque sommet une fois et peut ignorer des arêtes. Les noms se ressemblent et les difficultés sont radicalement différentes: linéaire contre NP-complet.
• Reparcourir les listes d adjacence dans Hierholzer. Si la recherche d'une arête inutilisée repart à chaque fois du début de la liste du sommet, l'algorithme devient quadratique. Conserve par sommet un itérateur qui n'avance que vers l'avant, puisqu'une arête utilisée ne resservira jamais.
• Appliquer la règle des degrés non orientée à un graphe orienté. Les graphes orientés exigent que le degré entrant égale le degré sortant en chaque sommet pour un circuit, ou exactement un sommet avec sortant moins entrant égal à 1 et un autre avec entrant moins sortant égal à 1 pour un chemin. Compter le degré total donne la mauvaise réponse.
• Commencer un chemin au mauvais sommet. Lorsque exactement deux sommets sont de degré impair, le parcours doit commencer à l'un et finir à l'autre. Partir d'ailleurs revient à se bloquer avec des arêtes restantes.

Questions fréquentes

Qu'est-ce qu'un chemin eulérien?

Un chemin eulérien est un parcours qui utilise chaque arête d'un graphe exactement une fois. Il peut visiter des sommets plusieurs fois. S'il revient en outre à son sommet de départ, on l'appelle circuit eulérien. L'idée vient d'Euler résolvant le problème des sept ponts de Konigsberg en 1736, ce qui fonda la théorie des graphes.

Quand un chemin eulérien existe-t-il?

Dans un graphe non orienté connexe, un circuit eulérien existe lorsque tous les sommets sont de degré pair, et un chemin eulérien existe lorsque exactement deux sommets sont de degré impair, auquel cas le chemin doit commencer à l'un et finir à l'autre. Tout autre nombre de sommets de degré impair signifie qu'aucun des deux n'existe. Toutes les arêtes doivent en outre appartenir à une seule composante connexe.

Quelle est la différence entre chemins eulériens et hamiltoniens?

Un chemin eulérien utilise chaque arête une fois et peut revisiter des sommets; un chemin hamiltonien visite chaque sommet une fois et peut ignorer des arêtes. L'écart de difficulté est spectaculaire: décider de l'existence d'un chemin eulérien coûte O(V + E) par comptage des degrés, tandis que la question hamiltonienne est NP-complète.

Comment fonctionne l'algorithme de Hierholzer?

Il avance le long d'arêtes inutilisées jusqu'à se bloquer, ce qui dans un graphe à degrés pairs ne peut se produire qu'au sommet de départ. Il dépile ensuite, et chaque fois qu'il trouve un sommet ayant des arêtes inutilisées, il parcourt depuis là une nouvelle boucle fermée et la greffe. Vider la pile fournit le parcours complet en ordre inverse, et l'exécution entière est en O(E).

Quelle est la complexité temporelle de la recherche d'un chemin eulérien?

O(V + E). Compter les degrés est en O(E), vérifier la connexité est un parcours, et Hierholzer marque chaque arête utilisée exactement une fois. Le détail d'implémentation essentiel est un pointeur par sommet dans la liste d'adjacence pour que les recherches d'arêtes inutilisées ne reparcourent jamais, ce qui maintient l'algorithme linéaire plutôt que quadratique.