Οι επτά γέφυρες του Κέινγκσμπεργκ

Ανάλυση του Euler

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

→ →

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

Στη συνέχεια, ο Euler παρατήρησε ότι (εκτός από τα τελικά σημεία του περιπάτου), κάθε φορά που κάποιος εισέρχεται σε μια κορυφή μέσω μιας γέφυρας, φεύγει από την κορυφή μέσω μιας γέφυρας. Σε κάθε περίπατο του γραφήματος, ο αριθμός των φορών που εισέρχεται κανείς σε μια κορυφή ισούται με τον αριθμό των φορών που την εγκαταλείπει. Εάν κάθε γέφυρα έχει διασχίσει ακριβώς μία φορά, προκύπτει ότι, για κάθε μάζα γης (εκτός από αυτές που επιλέχθηκαν για την αρχή και τον τερματισμό), ο αριθμός των γεφυρών που αγγίζουν αυτή τη μάζα γης πρέπει να είναι ζυγός. Αυτό συμβαίνει επειδή αν υπάρχουν n γέφυρες, διασχίζεται ακριβώς 2n φορές. Ωστόσο, και οι τέσσερις χερσαίες μάζες του αρχικού προβλήματος αγγίζονται από μονό αριθμό γεφυρών (η μία αγγίζεται από 5 γέφυρες και καθεμία από τις άλλες τρεις αγγίζεται από 3). Υπάρχουν το πολύ δύο μάζες που μπορούν να είναι τα τελικά σημεία ενός περιπάτου. Έτσι, η πρόταση ενός περιπάτου που διασχίζει κάθε γέφυρα μία φορά οδηγεί σε αντίφαση.

Στη σύγχρονη γλώσσα, ο Euler δείχνει ότι το αν είναι δυνατή ή όχι μια διαδρομή μέσα σε ένα γράφημα που διασχίζει κάθε ακμή μία φορά εξαρτάται από τους βαθμούς των κόμβων. Ο βαθμός ενός κόμβου είναι ο αριθμός των ακμών που τον αγγίζουν. Ο Euler δείχνει ότι απαραίτητη προϋπόθεση για τον περίπατο είναι το γράφημα να είναι συνδεδεμένο και να έχει ακριβώς μηδέν ή δύο κόμβους περιττού βαθμού. Αυτό το αποτέλεσμα που δήλωσε ο Euler αποδείχθηκε αργότερα από τον Carl Hierholzer. Ένας τέτοιος περίπατος καλείται τώρα μονοπάτι του Euler ή περίπατος του Euler. Εάν υπάρχουν κόμβοι περιττού βαθμού, τότε κάθε μονοπάτι Euler θα ξεκινά από τον έναν από αυτούς και θα καταλήγει στον άλλο. Δεδομένου ότι το γράφημα που αναπαριστά το ιστορικό Königsberg έχει τέσσερις κόμβους περιττού βαθμού, δεν μπορεί να έχει ένα Ευλεριανό μονοπάτι.

Το έργο του Euler παρουσιάστηκε στην Ακαδημία της Αγίας Πετρούπολης στις 26 Αυγούστου 1735. Δημοσιεύθηκε ως Solutio problematis ad geometriam situs pertinentis (Η λύση ενός προβλήματος που αφορά τη γεωμετρία της θέσης) στο περιοδικό Commentarii academiae scientiarum Petropolitanae το 1741. Διατίθεται στα αγγλικά στο The World of Mathematics.

Σημασία στην ιστορία των μαθηματικών

Στην ιστορία των μαθηματικών, η λύση του Euler για το πρόβλημα της γέφυρας του Königsberg θεωρείται το πρώτο θεώρημα της θεωρίας γραφημάτων. Η θεωρία γραφημάτων είναι ένα θέμα που σήμερα θεωρείται γενικά ως κλάδος της συνδυαστικής.

Παρούσα κατάσταση των γεφυρών

Δύο από τις επτά αρχικές γέφυρες καταστράφηκαν κατά τον βομβαρδισμό του Königsberg στον Β' Παγκόσμιο Πόλεμο. Δύο άλλες κατεδαφίστηκαν αργότερα. Αντικαταστάθηκαν από έναν σύγχρονο αυτοκινητόδρομο. Οι άλλες τρεις γέφυρες παραμένουν, αν και μόνο δύο από αυτές είναι από την εποχή του Euler (η μία ξαναχτίστηκε το 1935). Έτσι, από το 2000, υπήρχαν πέντε γέφυρες στο Καλίνινγκραντ.

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

Σχετικές σελίδες

• Icosian παιχνίδι
• Χαμιλτονιανή διαδρομή
• Νερό, φυσικό αέριο και ηλεκτρικό ρεύμα
• Πρόβλημα του πλανόδιου πωλητή