Comprendre les circuits eulériens dans la théorie des graphiques

Un circuit eulérien est une promenade fermée qui traverse chaque bord d'un graphique exactement une fois et revient au vertex de départ. Le concept provient du fameux problème des Sept Ponts de Königsberg posé par Leonhard Euler en 1736. Euler a prouvé qu'un tel circuit n'existe que si chaque vertex du graphique a un degré égal et le graphique est connecté (en ignorant des sommets isolés).

Pour le préciser formellement : Que G[ = (V[, E soit un graphique non dirigé. Un circuit eulérien existe si et seulement si chaque vertex v -Va un degré égal, et le graphique est connecté lorsqu'on considère seulement les sommets avec un degré non nul.

Qu'est-ce que Hierholzer est Algorithme?

Hierholzer , publié par le mathématicien allemand Carl Hierholzer en 1873, est une méthode efficace pour construire un circuit eulérien lorsque les conditions nécessaires sont remplies. Il construit le circuit en trouvant une série de cycles et en les fusionnant. L'algorithme fonctionne dans le temps linéaire O(E[) par rapport au nombre de bords, ce qui le rend optimal pour les graphiques denses et clairs.

Concepts clés

  • Détection du cycle:[ À partir d'un vertex, suivre les bords inutilisés jusqu'à revenir au vertex de départ.
  • Cycles de fusion: Lorsqu'un vertex sur le circuit de courant a encore des bords inutilisés, un nouveau cycle est formé à partir de ce vertex et inséré dans le circuit.
  • Désorption des bords : Comme les bords sont utilisés, ils sont marqués ou enlevés pour éviter de les revisiter.

Description étape par étape de Hierholzer , Algorithme

L'algorithme peut être mis en œuvre de façon récursive ou itérative. L'idée principale est de construire un circuit en étendant à plusieurs reprises les sous-circuits.

Étape 1: Choisissez un Vertex de départ

Sélectionnez n'importe quel vertex avec au moins un bord. Puisque le graphique est connecté et tous les degrés sont égaux, n'importe quel vertex fonctionnera. Typiquement, l'algorithme commence à vertex v.

Étape 2: Traverser un cycle

De la partie du vertex actuel, suivez n'importe quel bord inutilisé vers un voisin. Continuez à suivre les bords inutilisés, en marquant chaque bord comme utilisé, jusqu'à ce que vous retourniez au vertex de départ. Cela produit un cycle C. Si le cycle contient tous les bords du graphique, l'algorithme se termine – nous avons un circuit eulérien.

Étape 3: Trouver des sommets avec des bords inutilisés

Scanner le circuit courant pour tout vertex u qui a encore des bords non utilisés. Si aucun n'existe, l'algorithme est complet. Sinon, laissez u être un tel vertex.

Étape 4: Construire un nouveau cycle à partir de u

À partir de u, répéter le processus de recherche du cycle parmi les bords inutilisés. Cela crée un nouveau cycle C′ qui commence et se termine à u.

Étape 5 : Fusionner le nouveau cycle dans le circuit principal

Insérer C′ dans le circuit principal à la position de u. La marche résultante est toujours un circuit (fermé) et couvre tous les bords visités jusqu'à présent. Retour à l'étape 3.

Parce que chaque vertex a un degré pair, le processus ne se bloque jamais : chaque fois que vous entrez dans un vertex, il y aura toujours un bord inutilisé à partir, jusqu'à ce que le degré vertex , est zéro. L'algorithme garantit que la marche finale inclut chaque bord exactement une fois.

Exemple: Construction d'un circuit eulérien

Considérez un graphique non dirigé avec les sommets A, B, C, D et E. Bords: AB, AC, AD, BC, BD, CE, DE. (Ce graphique est un petit graphique où chaque sommet a même degré: deg(A)=3, deg(B)=3, deg(C)=2, deg(D)=3, deg(E)=1? Cela ne satisfait pas une condition de degré uniforme. Let=S correct: Utilisez un graphique où tous les degrés sont égaux: A–B, B–C, C–D, D–A, plus A–C et B–D. Cela donne chaque sommet degré 3? Ce qui est étrange. En fait un simple exemple de degré pair: un triangle avec chaque sommet degré 2? Non intéressant. Let=S utilise un exemple plus typique: les sommets 1,2,3,4.5 avec les bords: 1‐2, 2‐3, 3‐1, 3‐4, 4‐5, 5‐3. Degrés: 1 (deg 2), 2 (deg 2), 3 (deg 4), 4 (deg 2), 5 (deg 2).

Exécuter Hierholzer , Algorithme :

  • Commencez par le vertex 1. Suivez les bords : 1‐2 (utilisation), 2‐3 (utilisation), maintenant à 3. Choisissez le bord inutilisé 3‐4 (utilisation), 4‐5 (utilisation), 5‐3 (utilisation). Retourner à 3, mais le point de départ initial était 1. Nous n'avons pas encore retourné à 1. En fait, l'algorithme doit former un cycle qui retourne au vertex de départ. Let=s trace correctement : Commencez à 1, aller 1‐2, 2‐3, maintenant à partir de 3 nous pouvons aller 3‐1 (inutilisé) – qui donne cycle 1‐2‐3‐1. Cela signifie cycle C1. Après cela, les bords gauche : 3‐4, 4‐5, 5‐3.
  • Scan C1 : le vertex 3 a des bords inutilisés. Commencez un nouveau cycle à 3: 3‐4, 4‐5, 5‐3. Cycle C2 = 3‐4‐5‐3.
  • Fusionner le C2 en C1 au sommet 3: circuit résultant: 1‐2‐3‐4‐5‐3‐1. Tous les bords utilisés, le circuit est eulérien.

Cet exemple illustre l'élégance de l'algorithme : les cycles sont découverts et combinés sans heurts.

Complexité et considérations liées à la mise en œuvre

Hierholzer=S Algorithm fonctionne dans O(V + E) le temps d'utilisation d'une représentation de liste d'adjacence et de structures de données efficaces pour l'enlèvement des bords (p. ex., en utilisant des itérateurs ou des listes liées). L'algorithme est optimal parce que chaque bord est traité exactement une fois. Le dessus de la mémoire est O[V + E) pour stocker le graphique et le circuit.

Pour les graphiques dirigés, la même approche fonctionne à condition que le graphique soit eulérien (en degré égal au degré hors-degré à chaque sommet). L'algorithme , l'exigence de degrés égaux, se traduit aussi dans le cas dirigé.

Comparaison avec Fleury , Algorithme

Un autre algorithme bien connu pour trouver les circuits eulériens est Fleury="s Algorithm, qui fonctionne en traversant les bords tout en assurant que le graphique restant reste connecté (c'est-à-dire en évitant les ponts).L'algorithme Fleury="s court dans O[E]2, car il doit vérifier la connectivité à chaque étape.L'algorithme Hierholzer="s est généralement préféré pour sa complexité linéaire et sa mise en œuvre plus simple.Le seul inconvénient est que Hierholzer="s exige que le graphique soit eulérien (même degrés) alors que Fleury="s peut également gérer des graphiques semi-eulériens (lorsque exactement deux sommets ont un degré étrange, produisant un sentier eulérien).

Applications de Hierholzer , Algorithme

La capacité de trouver un circuit eulérien efficacement a de nombreuses utilisations réelles.

Problème de poste chinois

Dans le problème Postman chinois (inspection de la route), le but est de trouver la marche la plus courte fermée qui couvre chaque bord au moins une fois. Pour les graphiques qui sont déjà eulériens, la solution est simplement le circuit eulérien. L'algorithme Hierholzer , fournit ce circuit. Pour les graphiques non eulériens, le problème réduit à dupliquer les bords pour rendre tous les degrés, puis appliquer Hierholzer , .

Routage réseau et conception de circuits

Les circuits eulériens sont utilisés pour concevoir des itinéraires efficaces pour les balayeurs de rue, la collecte des ordures et la transmission de paquets réseau où chaque liaison doit être traversée exactement une fois. L'algorithme aide à minimiser les déplacements redondants.

Assemblée de fragments d'ADN

En biologie computationnelle, l'approche du graphe de Bruijn pour l'assemblage du génome repose sur la recherche de chemins ou de circuits eulériens à travers des graphes k-mer. L'algorithme de Hierholzer est un élément central de nombreux assembleurs, permettant la reconstruction de séquences contiguës à partir de lectures courtes.

Graphisme informatique et génération de labyrinthes

Les pistes eulériennes sont utilisées pour générer des labyrinthes et dans certains algorithmes de dessin graphe où les bords doivent être tracés sans soulever le stylo. L'algorithme fournit une construction optimale.

Essais intégrés de circuits

Dans la conception de l'intégration à très grande échelle (VLSI), les essais de toutes les connexions peuvent être modélisés comme un problème de circuit eulérien, minimisant ainsi le mouvement du testeur.

Lecture supplémentaire et ressources externes

Pour approfondir votre compréhension des circuits eulériens et de l'algorithme Hierholzer, les ressources suivantes sont recommandées :

Conclusion

Hierholzer , Algorithm reste la pierre angulaire de la traversée du graphe pour son élégance, sa vitesse et son applicabilité étendue. En décomposé le problème en trouvant et en fusionnant des cycles, il offre une solution simple et optimale pour la construction de circuits eulériens. Que vous conçoyiez des itinéraires réseau, assembliez des génomes ou résolviez des énigmes, la compréhension de cet algorithme vous équipe d'un puissant outil pour manipuler des graphes avec des sommets à degrés réguliers.