Τι είναι η Θεωρία Γραφημάτων και πώς ορίζεται ένα γράφημα ως τέτοιο;

Το 1736, με βάση το έργο του Ελβετού φυσικού-μαθηματικού Leonhard Euler (1707-1783), παρατηρήθηκε ότι μια διαδοχή κορυφών ορίζει μια διαδρομή, ωστόσο, εάν η εν λόγω διαδρομή αποτελείται από διαφορετικές κορυφές χωρίς επαναλαμβανόμενες ακμές, ονομάζεται μονοπάτι ή μονοπάτι Eulerian? εάν επιπλέον φτάσουμε στο σημείο εκκίνησης, διασχίζοντας κάθε άκρη μόνο μία φορά, τότε έχουμε έναν κύκλο (κύκλωμα) Euler.

Προσφορά (APA)

Αλέξανδρος Μπαράζα | Ιούλ. 2022
Πτυχίο φυσικής

Από την πλευρά του, ορίζουμε ένα γράφημα ως ένα διατεταγμένο ζεύγος (ΠΑΕΙ) όπου v δηλώνει το (μη κενό) σύνολο όλων των κορυφών ή κόμβων ενός γραφήματος, ενώ ΕΝΑ δηλώνει το σύνολο (μπορεί να είναι κενό) όλων των ακμών ή των γραμμών που ενώνουν τις κορυφές ενός γραφήματος. Τα στοιχεία του συνόλου ΕΝΑ μπορεί να οριστεί ως ένα μη ταξινομημένο ζεύγος {v, w} όπου τα v και w είναι στοιχεία (κόμβοι ή κορυφές) του v, με αυτόν τον τρόπο λέγεται τότε ότι οι v και w είναι γειτονικές κορυφές (ενώνονται με μια ακμή).

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

Το πρόβλημα των επτά γεφυρών του Königsberg

Ο Euler μοντελοποίησε το Königsberg ως γράφημα όπου κάθε σημείο (κορυφή ή κόμβος) αντιπροσωπεύει μια γέφυρα και κάθε γραμμή (ακμή) μια διαδρομή στην ξηρά:

Ποια είναι η λύση σε αυτό το πρόβλημα;

δεν υπάρχει ένα λύση που πληροί τις επιβαλλόμενες προϋποθέσεις, αφού, όπως έδειξε ο Euler, οι κορυφές δεν είναι άρτιου βαθμού, δηλαδή ένας ζυγός αριθμός γραμμών δεν επηρεάζει κάθε σημείο _[3]. Δεν φαίνεται ότι μπορούμε να κάνουμε πολλά με μια δομή που ορίζεται τόσο απλά όπως αυτή, ωστόσο, όπως συμβαίνει συχνά σε μαθηματικά, Μερικές φορές τα πράγματα δεν είναι όπως φαίνονται. Έτσι, ένας από τους πιο παραγωγικούς, εγκάρσιους και διεπιστημονικούς τομείς _[4] της ανθρώπινης γνώσης, θεωρία γραφημάτων.

Γραφήματα Eulerian ή με Eulerian τροχιά;

Τα παρακάτω γραφήματα έχουν όλα Eulerian μονοπάτια _[5]. Έχουν όλοι κύκλους Eulerian;

Ας πάρουμε το τρίτο γράφημα:

Ας αριθμήσουμε τις κορυφές:

Βλέπουμε λοιπόν ότι το μονοπάτι που ορίζεται από την ακολουθία {3,4,6,2,1,3,7,6,5,4,2} είναι ένα μονοπάτι του Euler, αφού διατρέχει ολόκληρο το γράφημα χωρίς επαναλαμβανόμενες ακμές, αλλά δεν είναι κύκλος Eulerian, αφού δεν φτάνει στο σημείο εκκίνησης. Τι θα είχε συμβεί αν αριθμούσαμε διαφορετικά τις κορυφές; Όχι πολλά, εκτός από το ότι τώρα η διαδρομή θα καθοριζόταν από μια διαφορετική διαδοχή. Τι θα είχε συμβεί αν ακολουθούσαμε διαφορετικούς δρόμους από εκείνους που προτείναμε στην αρχική μας λύση; Αυτή η ερώτηση είναι λίγο πιο περίπλοκη για να απαντηθεί και περιλαμβάνει αλγόριθμους με τους οποίους οι μηχανικοί λογισμικού συνήθως χαίρονται. προγραμματισμός.

Για μια πιο αυστηρή απόδειξη αυτού που εκτίθεται εδώ, πρέπει να αναφερθούμε στο ακόλουθο αποτέλεσμα:

"Είναι σολ ένα συνδεδεμένο γράφημα _[6]. Τότε ναι σολ έχω ένα κύκλωμα Euler, ο βαθμός κάθε κορυφής είναι άρτιος, ενώ αν σολ έχει μονοπάτι Euler, το G έχει ακριβώς δύο κορυφές περιττού βαθμού _[7] (ακριβώς οι κορυφές όπου ξεκινά και τελειώνει το μονοπάτι)".

Μπορούμε στη συνέχεια να επαληθεύσουμε ότι, στην πραγματικότητα, στο γράφημα που παίρνουμε, μόνο οι κορυφές 3 και 6 έχουν περιττό βαθμό (αυτό θα εμφανιζόταν ακόμα κι αν η αρίθμηση των κορυφών ήταν διαφορετική), επομένως το εν λόγω γράφημα έχει μια διαδρομή Ευλεριανός _[8]. Για τα υπόλοιπα γραφήματα μπορούμε να προχωρήσουμε με ανάλογο τρόπο και να επαληθεύσουμε αν όντως έχουν μονοπάτια και Κύκλοι Eulerian, ή με άλλο τρόπο, μπορούμε να σχεδιάσουμε τέτοια γραφήματα χωρίς να σηκώσουμε το μολύβι και να επαναλάβουμε γραμμές; Η απάντηση σε αυτό το ερώτημα μπορεί να συναχθεί από όσα έχουν ήδη εξηγηθεί μέχρι τώρα, ωστόσο, αποτελεί άσκηση ενδιαφέρον όσον αφορά τις λεπτές κινητικές δεξιότητες, την εφευρετικότητα και την υπομονή, καλώ τον αναγνώστη να βρει και να σχεδιάσει γραφήματα 6 ή περισσότερων κορυφές με τροχιά Ο Eulerian.

Υπάρχουν άλλα είδη γραφημάτων; Η θεωρία γραφημάτων έχει εφαρμογές στον «πραγματικό» κόσμο;

Αυτά τα γραφήματα που εξετάσαμε πολύ σύντομα, είναι μόνο ένας από τους πολλούς τύπους γραφημάτων που βρίσκουμε στη θεωρία γραφημάτων. Μπορούμε επίσης να βρούμε γραφήματα όπως δέντρα, πολύ αντιπροσωπευτικά σε σύνολα όπου τα στοιχεία τους μπορούν να ταξινομηθούν σε ιεραρχίες και σε υπολογισμούς μέτρησης και πιθανότητα_[9], διγραφήματα, γραφήματα Hamiltonian _[10], και τα λοιπά.

Image of Graphic Models and Networks in Psycho., by Ruiz, Ana María.

Αυτά τα αινίγματα, αν θέλουμε να τα ονομάσουμε έτσι, έχουν τεράστια εφαρμογή στον σημερινό κόσμο, σε τόσο διαφορετικές καταστάσεις όπως: βιολογία μοριακός _[11], χρήση υπολογιστή_[12], τηλεπικοινωνιών _[13] και ανάλυση δικτύου _[14]. Αξίζει να ρωτήσετε λοιπόν: Δεν είναι τουλάχιστον περίεργο ότι ένα πρόβλημα σχεδόν τετριμμένος θα καταλήξει να είναι ένα από τα πιο ενδιαφέροντα και εμφανή αποτελέσματα των μαθηματικών; Ίσως, γι' αυτό, ήταν απαραίτητη η συμβολή ενός από τα πιο επιφανή μυαλά της ανθρωπότητας.