Κατανόηση των Ευληρικών Κύκλων στη Θεωρία των Γραφών

Ένα ευληριανό κύκλωμα είναι μια κλειστή βόλτα που διασχίζει κάθε άκρη ενός γραφήματος ακριβώς μία φορά και επιστρέφει στην αρχή κορυφή. Η έννοια προέρχεται από το περίφημο επτά γέφυρες του Königsberg πρόβλημα που τίθεται από Leonhard Euler το 1736. Euler απέδειξε ότι ένα τέτοιο κύκλωμα υπάρχει μόνο αν κάθε κορυφή του γράφηματος έχει ομοιόμορφο βαθμό και το γράφημα είναι συνδεδεμένο (αναγνώριση απομονωμένων κορυφών). Αυτό το θεμελιώδες αποτέλεσμα έθεσε τα θεμέλια για τη θεωρία γραφημάτων και παραμένει ζωτικής σημασίας στην ανάλυση δικτύων, το σχεδιασμό κυκλωμάτων, και τη συνδυαστική βελτιστοποίηση.

Για να το δηλώσετε επίσημα: Ας είναι G[] = ([V, E]]) ένα ευληριανό κύκλωμα υπάρχει αν και μόνο εάν κάθε vertex v ⁇ V έχει ένα άρτιο βαθμό, και το γράφημα συνδέεται όταν εξετάζει μόνο vertices με μη μηδενικό βαθμό. Για κατευθυνόμενα γραφήματα, οι συνθήκες είναι ότι κάθε vertex έχει ίσο βαθμό και βαθμό και το υποκείμενο μη κατευθυνόμενο γράφημα συνδέεται.

Τι Είναι ο Αλγόριθμος του Ιεροχόλζερ;

Ο Αλγόριθμος του Hierholzer, που εκδόθηκε από τον Γερμανό μαθηματικό Carl Hierholzer το 1873, είναι μια αποτελεσματική μέθοδος για την κατασκευή ενός κυκλώματος Eulerian όταν πληρούνται οι απαραίτητες προϋποθέσεις. Κατασκευάζει το κύκλωμα με την εύρεση μιας σειράς κύκλων και τη συγχώνευσή τους. Ο αλγόριθμος τρέχει σε γραμμικό χρόνο O(E]) σε σχέση με τον αριθμό των ακμών, καθιστώντας τον βέλτιστο τόσο για τα πυκνά όσο και τα αραιά γραφήματα.

Βασικές έννοιες

  • Ανίχνευση κυκλικού: Ξεκινώντας από μια κορυφή, ακολουθήστε αχρησιμοποίητες άκρες μέχρι την επιστροφή στην αρχή της κορυφής. Αυτό σχηματίζει έναν απλό κύκλο.
  • Κύκλοι σύσφιξης: Όταν μια κορυφή στο τρέχον κύκλωμα έχει ακόμα αχρησιμοποίητες άκρες, σχηματίζεται ένας νέος κύκλος από την κορυφή αυτή και εισάγεται στο κύκλωμα.
  • Αφαίρεση ιχνοστοιχείων: Καθώς χρησιμοποιούνται ακμές, σημειώνονται ή αφαιρούνται για να αποφευχθεί η επαναξιολόγηση τους.

Βήμα-βήμα Περιγραφή του Αλγόριθμου του Hierholzer

Ο αλγόριθμος μπορεί να εφαρμοστεί αναδρομικά ή επαναληπτικά. Η βασική ιδέα είναι να κατασκευαστεί ένα κύκλωμα επεκτείνοντας επανειλημμένα υποκυκλώματα. Παρακάτω είναι μια λεπτομερής ανάλυση.

Βήμα 1: Επιλέξτε ένα αρχικό vertex

Επιλέξτε οποιαδήποτε κορυφή με τουλάχιστον ένα άκρο. Δεδομένου ότι το γράφημα είναι συνδεδεμένο και όλοι οι βαθμοί είναι ίσοι, οποιαδήποτε κορυφή θα λειτουργήσει. Τυπικά ο αλγόριθμος ξεκινά από vertex v.

Βήμα 2: Περιστροφή ενός Κύκλου

Από την τρέχουσα κορυφή, ακολουθήστε κάθε αχρησιμοποίητο άκρο σε ένα γείτονα. Συνεχίστε να κινείστε κατά μήκος αχρησιμοποίητων ακμών, σημειώνοντας κάθε άκρο όπως χρησιμοποιείται, μέχρι να επιστρέψετε στην αρχή κορυφή. Αυτό παράγει έναν κύκλο C. Αν ο κύκλος περιέχει όλες τις άκρες του γραφήματος, ο αλγόριθμος τερματίζει ⁇ έχουμε ένα Ευληριανό κύκλωμα.

Βήμα 3: Βρείτε Στίχοι με Άχρηστες Ακρές

Σαρώστε το τρέχον κύκλωμα για οποιαδήποτε κορυφή u[] που έχει ακόμα τις προσβολές αχρησιμοποίητες άκρες. Αν δεν υπάρχει, ο αλγόριθμος είναι πλήρης. Διαφορετικά, αφήστε u να είναι μια τέτοια κορυφή.

Βήμα 4: Φτιάξτε έναν νέο κύκλο από u

Ξεκινώντας από u, επαναλάβετε τη διαδικασία αναζήτησης του κύκλου μεταξύ των αχρησιμοποίητων ακμών. Αυτό δημιουργεί έναν νέο κύκλο C ⁇ που ξεκινά και τελειώνει στο [u].

Βήμα 5: Συγχώνευση του Νέου Κύκλου στο Κεντρικό Κύκλωμα

Εισαγωγή C ⁇ στο κύριο κύκλωμα στη θέση u. Η προκύπτουσα βάδην είναι ακόμα κύκλωμα (κλειστό) και καλύπτει όλες τις άκρες που επισκέπτονται μέχρι στιγμής. Επιστροφή στο Βήμα 3.

Επειδή κάθε κορυφή έχει ομοιόμορφο βαθμό, η διαδικασία δεν κολλάει ποτέ: όποτε μπαίνεις σε μια κορυφή, θα υπάρχει πάντα ένα αχρησιμοποίητο άκρο για να φύγει, μέχρι ο βαθμός της κορυφής να γίνει μηδέν. Ο αλγόριθμος εγγυάται ότι η τελική βόλτα περιλαμβάνει κάθε άκρη ακριβώς μία φορά.

Παράδειγμα: Κατασκευή ενός Ευληριανού Κυκλώματος

Εξετάστε ένα μη κατευθυνόμενο γράφημα με κορυφές A, B, C, D, και E. Εδάφια: AB, AC, AD, BC, BD, CE, DE. (Αυτό είναι ένα μικρό γράφημα όπου κάθε κορυφή έχει ομοιόμορφο βαθμό: deg(A)=3, deg(B)=3, deg(C)=2, deg(D)=3, deg(E)=1; Αυτό δεν ικανοποιεί ακόμη και την κατάσταση του βαθμού. Ας είναι σωστό: Χρησιμοποιήστε ένα γράφημα όπου όλες οι μοίρες είναι ακόμη: A ⁇ B, B ⁇ C, C ⁇ D, D ⁇ A, συν A ⁇ C και B ⁇ D. Αυτό δίνει κάθε vertex βαθμό 3; Αυτό είναι περίεργο. Στην πραγματικότητα ένα απλό ομοιόμορφο παράδειγμα: ένα τρίγωνο με κάθε vertex βαθμό 2; Δεν είναι ενδιαφέρουσα. Αφήνει τη χρήση ενός πιο τυπικού παραδείγματος: vertices, 1,24,5 με ακμές: 1 ⁇ 3, 4, 4, 4, (π.χ. 2).

Εκτέλεση Αλγόριθμου του Hierholzer:

  • Ξεκινήστε από την κορυφή 1. Ακολουθήστε τις άκρες: 1 ⁇ 2 (χρησιμοποιήστε), 2 ⁇ 3 (χρησιμοποιήστε), τώρα σε 3. Επιλέξτε αχρησιμοποίητο άκρο 3 ⁇ 4 (χρησιμοποιήστε), 4 ⁇ 5 (χρησιμοποιήστε), 5 ⁇ 3 (χρησιμοποιήστε). Επιστρέψτε στο 3, αλλά το αρχικό σημείο εκκίνησης ήταν 1. Δεν έχουμε επιστρέψει στο 1 ακόμα. Στην πραγματικότητα ο αλγόριθμος πρέπει να σχηματίσει έναν κύκλο που επιστρέφει στην αρχή της κορυφή. Ας εντοπίσουμε σωστά: Ξεκινήστε στο 1, πάμε 1 ⁇ 2, 2 ⁇ 3, τώρα από το 3 μπορούμε να πάμε 3 ⁇ 1 (χρησιμοποιηθούν) ⁇ που δίνει τον κύκλο 1 ⁇ 2 ⁇ 3 ⁇ 1. Αυτό είναι ο κύκλος C1. Μετά από αυτό, οι άκρες αριστερά: 3 ⁇ 4, 4 ⁇ 5, 5 ⁇ 3.
  • Σάρωση C1: η κορυφή 3 έχει αχρησιμοποίητες άκρες. Ξεκινήστε νέο κύκλο σε 3: 3-3, 4-5, 5-3. Κύκλος C2 = 3,4 ⁇ 5 ⁇ 3.
  • Συγχώνευση C2 σε C1 στην κορυφή 3: προκύπτοντα κυκλώματα: 1 ⁇ 2 ⁇ 3 ⁇ 4 ⁇ 5 ⁇ 3 ⁇ 1. Όλες οι άκρες που χρησιμοποιούνται, κύκλωμα είναι Eulerian.

Αυτό το παράδειγμα απεικονίζει την κομψότητα του αλγορίθμου: ανακαλύπτονται κύκλοι και συνδυάζονται απρόσκοπτα.

Σύνθετες και Υλοποιημένες Συνεκτάσεις

Ο Αλγόριθμος του Hierholzer τρέχει σε ]O(V + E]) χρόνο κατά τη χρήση μιας αναπαράστασης καταλόγου και αποδοτικών δομών δεδομένων για την αφαίρεση άκρων (π.χ. με τη χρήση πλάστιγγες ή συνδεδεμένων καταλόγων). Ο αλγόριθμος είναι βέλτιστος επειδή κάθε άκρος έχει επεξεργαστεί ακριβώς μία φορά. Το πάνω μέρος της μνήμης είναι O](]V + E) για την αποθήκευση του γραφήματος και του κυκλώματος.

Για τα κατευθυνόμενα γραφήματα, η ίδια προσέγγιση έργα υπό την προϋπόθεση ότι το γράφημα είναι Eulerian (σε ⁇ βαθμό ισούται με out ⁇ βαθμό σε κάθε κορυφή). Η απαίτηση του αλγόριθμου για ζυγούς βαθμούς μεταφράζεται στην κατευθυνόμενη περίπτωση, καθώς και.

Σύγκριση με τον Αλγόριθμο του Φλερύ

Ένας άλλος γνωστός αλγόριθμος για την εύρεση των κυκλωμάτων του Ευλερίου είναι ο Αλγόριθμος του Φλερύ, ο οποίος λειτουργεί διασχίζοντας τις άκρες ενώ εξασφαλίζει ότι το υπόλοιπο γράφημα παραμένει συνδεδεμένο (δηλαδή, αποφεύγοντας γέφυρες). Ο αλγόριθμος του Φλερύ τρέχει σε ]O(]E[2]) χρόνο επειδή χρειάζεται να ελέγξει τη συνδεσιμότητα σε κάθε βήμα. Ο αλγόριθμος του Ιεροχόλζερ προτιμάται γενικά για τη γραμμική του πολυπλοκότητα και την απλούστερη εφαρμογή. Η μόνη κάτω πλευρά είναι ότι ο Hierholzer απαιτεί το γράφημα να είναι Eulerian (ακόμα μοίρες) ενώ ο Fleury’s μπορεί επίσης να χειριστεί ημι-Ευουλριανά γραφήματα (όταν ακριβώς δύο vertices έχουν περίεργο βαθμό, παράγουν ένα Eulerian track). Ωστόσο, Hierholzer’s μπορεί να προσαρμοστεί σε δύο γραφικά σημεία για την κατασκευή του κυκλώματος, ενώ το κύκλωμα του Ευλερ, μπορεί να χειριστεί να χειριστεί

Εφαρμογές του Αλγόριθμου του Ιεροχόλζερ

Η ικανότητα να βρεις ένα Ευληριανό κύκλωμα αποτελεσματικά έχει πολλές πραγματικές ⁇ παγκόσμιες χρήσεις.

Κινέζικο πρόβλημα ταχυδρόμου

Για τα γραφήματα που είναι ήδη Eulerian, η λύση είναι απλά το Eulerian κύκλωμα. Ο αλγόριθμος Hierholzer παρέχει ότι το κύκλωμα. Για μη-Ευλαβικά γραφήματα, το πρόβλημα μειώνεται σε διπλασιάζοντας τις άκρες για να κάνει όλους τους βαθμούς ομοιόμορφα, και στη συνέχεια εφαρμόζοντας Hierholzer του.

Σχεδιασμός και κυκλώματος δικτύου

Τα κυκλώματα του Eulerian χρησιμοποιούνται για τον σχεδιασμό αποτελεσματικών διαδρομών για τους σκούπες του δρόμου, τη συλλογή απορριμμάτων και τη μετάδοση πακέτων δικτύου όπου κάθε σύνδεσμος πρέπει να διασχίζεται ακριβώς μια φορά.

Συναρμολόγηση τμημάτων DNA

Στην υπολογιστική βιολογία, η προσέγγιση γραφημάτων του ντε Μπρουίν στη συναρμολόγηση γονιδιώματος βασίζεται στην εύρεση Ευλερικών μονοπατιών ή κυκλωμάτων μέσω γραφημάτων k ⁇ mer. Ο αλγόριθμος του Χιερχόλζερ είναι ένα βασικό συστατικό πολλών συναρμολογητών, επιτρέποντας την ανακατασκευή των συνεχόμενων ακολουθιών από σύντομες αναγνώσεις.

Γραφικά υπολογιστών και παραγωγή λαβύρινθων

Τα μονοπάτια του Eulerian χρησιμοποιούνται για την παραγωγή λαβύρινθων και σε ορισμένους αλγόριθμους σχεδίασης γραφημάτων όπου πρέπει να σχεδιαστούν οι άκρες χωρίς να σηκώνεται η πένα. Ο αλγόριθμος παρέχει μια βέλτιστη κατασκευή.

Δοκιμή ολοκληρωμένου κυκλώματος

Στο σχεδιασμό Πολύ Μεγάλη ⁇ Scale Integration (VLSI), δοκιμή όλες οι συνδέσεις μπορούν να μοντελοποιηθούν ως πρόβλημα κυκλώματος Eulerian, ελαχιστοποιώντας την κίνηση του ελεγκτή.

Περαιτέρω ανάγνωση και εξωτερικοί πόροι

Για να εμβαθύνετε την κατανόησή σας για τα Ευληριακά κυκλώματα και τον αλγόριθμο του Hierholzer, συνιστώνται οι ακόλουθοι πόροι:

Συμπέρασμα

Ο Αλγόριθμος του Hierholzer παραμένει ένας ακρογωνιαίος λίθος του διαγράμματος για την κομψότητα, την ταχύτητα και την ευρεία εφαρμογή του. Αποσυνθέοντας το πρόβλημα στην εύρεση και συγχώνευση κύκλων, παρέχει μια απλή και βέλτιστη λύση για την κατασκευή των Ευληριακών κυκλωμάτων. Είτε σχεδιάζετε διαδρομές δικτύου, συναρμολογώντας γονιδιώματα, είτε λύνοντας παζλ, η κατανόηση αυτού του αλγόριθμου σας εξοπλίζει με ένα ισχυρό εργαλείο για τον χειρισμό γραφημάτων με βερτικές άρτιους βαθμούς. Η γραμμική πολυπλοκότητα του χρόνου και η απλή αναδρομική δομή του το καθιστούν ένα αγαπημένο μεταξύ των ενθουσιωδών αλγορίθμων και των επαγγελματιών.