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

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

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

Βλέπουμε ότι περάσαμε από έξι από τις επτά γέφυρες, μία από τις γέφυρες την προσπεράσαμε. Μπορούμε να δοκιμάσουμε άλλη διαδρομή…

Πάλι περάσαμε μόνο από έξι από τις επτά γέφυρες του Καίνιξμπεργκ. Σχεδόν φαίνεται ότι δεν είναι δυνατό να περάσουμε με έναν περίπατο από κάθε γέφυρα ακριβώς μία φορά. Μια μέρα έπεσε πάνω σε αυτό το πρόβλημα ο γνωστός μαθηματικός Leonhard Euler. Τι γνωστός – ο Euler ήταν αληθινός θρύλος των μαθηματικών, από τον οποίο παίρνει μάλιστα το όνομά του ο αριθμός του Euler. Ο Euler αποφάσισε να λύσει αυτόν τον γρίφο. Ξεκίνησε σημειώνοντας τα επιμέρους νησιά ή τμήματα της πόλης, προς τα οποία και από τα οποία οδηγούσαν οι γέφυρες:

Ο Euler έκανε τώρα την εξής σκέψη: αν σε ένα νησί οδηγεί άρτιος αριθμός γεφυρών, μπορούμε να περάσουμε από αυτές τις γέφυρες σε έναν περίπατο, όπου κι αν ξεκινήσουμε. Με λίγα λόγια, από τη μία γέφυρα φτάνουμε στο νησί, από την άλλη φεύγουμε – ο αριθμός των γεφυρών που μένει ακόμη να διασχίσουμε μειώθηκε κατά δύο. Για να μπορέσουμε να έρθουμε στο νησί από τη μία γέφυρα και να φύγουμε από την άλλη, χρειαζόμαστε δύο γέφυρες. Αν στο νησί οδηγούν έξι γέφυρες, θα επισκεφτούμε το νησί τρεις φορές. Για παράδειγμα, ας φανταστούμε ότι στο νησί B οδηγούσαν τέσσερις γέφυρες ως εξής:

Τότε με έναν κυριακάτικο περίπατο μπορούμε να περάσουμε από όλες τις γέφυρες, όπου κι αν ξεκινήσουμε. Δοκίμασέ το! Στο σχήμα σημείωσα μία διαδρομή. Ας φανταστούμε όμως ότι στο νησί B οδηγούσε ακόμη μία γέφυρα από το νησί D:

Βλέπουμε ότι η διαδρομή που διαλέξαμε δεν μας επιτρέπει να περάσουμε από όλες τις γέφυρες ακριβώς μία φορά. Θα έπρεπε να γυρίσουμε από κάποια γέφυρα στο νησί B και μετά να περάσουμε στο νησί D. Μπορούμε όμως να διαλέξουμε άλλη διαδρομή. Μπορούμε να ξεκινήσουμε τον περίπατό μας από το νησί B και τότε είμαστε σε θέση να περάσουμε από όλες τις γέφυρες ακριβώς μία φορά:

Τον περίπατό μας τον ξεκινήσαμε από το νησί B, πήγαμε πάνω στην περιοχή A, μετά με γέφυρα πίσω στο B, στην περιοχή C, μετά πάλι πίσω στο νησί B και τέλος στο νησί D. Αν λοιπόν ξεκινήσουμε από νησί που έχει περιττό αριθμό γεφυρών, είμαστε σε θέση να περάσουμε από όλες τις γέφυρές του ακριβώς μία φορά. Ή μπορούμε να πάμε εντελώς αντίστροφα – μπορούμε να ξεκινήσουμε από το νησί D και να τελειώσουμε στο νησί B.

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

τότε βλέπουμε ότι κάθε νησί έχει περιττό αριθμό γεφυρών! Το νησί A έχει 3, το B έχει 5, το C έχει 3 και το D έχει επίσης 3. Γι' αυτό ο γρίφος δεν έχει λύση – δεν είναι δυνατό να περάσουμε και από τις επτά γέφυρες ακριβώς μία φορά σε έναν κυριακάτικο περίπατο. Αν γκρεμίζαμε οποιαδήποτε από τις γέφυρες, ξαφνικά ο γρίφος θα είχε λύση. Ας γκρεμίσουμε, για παράδειγμα, μία από τις γέφυρες ανάμεσα στα νησιά B και C:

Βλέπουμε ότι αμέσως το νησί B έχει 4 γέφυρες και το νησί C δύο γέφυρες. Στα νησιά A και D ο αριθμός των γεφυρών δεν άλλαξε. Έχουμε ξαφνικά δύο νησιά με άρτιο αριθμό γεφυρών και δύο νησιά με περιττό αριθμό γεφυρών. Αν ξεκινήσουμε τον περίπατό μας από ένα από τα νησιά που έχουν περιττό αριθμό γεφυρών, μπορούμε να περάσουμε από όλες τις γέφυρες ακριβώς μία φορά. Στο σχήμα ξεκινήσαμε από το νησί A και τελειώσαμε στο νησί D.

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