Οι επτά γέφυρες του Κένισμπεργκ, ένα περιπατητικό πρόβλημα...

           
     Η παλαιά πόλη του Κένισμπεργκ (σημερινό Καλίνινγκραντ) βρίσκεται δίπλα στον ποταμό Πρέγκελ και έχει δυο νησάκια που επικοινωνούσαν με την πόλη μέσω επτά γεφυρών. Το ποτάμι ρέει γύρω από τα δυο νησάκια. Όλα τα γεφύρια, εκτός από ένα, συνδέουν τις όχθες με τις νησίδες, ενώ το άλλο ένα συνδέει τα δυο νησάκια μεταξύ τους. 

 

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

  Όμως αυτός που έμελε να το λύσει,ήταν ο Ελβετός μαθηματικός Λ. Οιλερ, ο άνθρωπος που υπολόγιζε με την ίδια ευκολία που οι αετοί ζυγιάζονται στον αέρα κατά τον ιστορικό των μαθηματικών Φρανσουά Αραγκό. Εκείνη την εποχή ο Οιλερ βρισκόταν στην υπηρεσία της Ρωσίδας Τσαρίνας Αικατερίνης της μεγάλης, στην Αγία Πετρούπολη.

   

 

Λέοναρντ  Όιλερ(1707-1783)

   

 Το 1736, σε ένα από τα ταξίδια του,ο Οιλερ  σταμάτησε στο Κένισμπεργκ κι άκουσε για το πρόβλημα,γράφει σχετικά:

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

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

 Ο Οιλερ έκανε ένα σχέδιο της πόλης και από αυτό έφτιαξε μια απλοποιημένη αναπαράσταση στην όποια τα κομμάτια ξηράς τα αντικατέστησε με  σημείο και τις γέφυρες τις παρέστησε με γραμμές.     

 Στην συνέχεια,παρατήρησε ότι για να πετύχει κανείς αυτό το ταξίδι, να περάσει δηλαδή από κάθε γέφυρα μια μόνο φορά, έπρεπε κάθε σημείο  να συνδέεται με άρτιο αριθμό γραμμών διότι ,όταν ο περιπατητής περνά από  ένα κομμάτι ξηράς,πρέπει να μπει  από μια γέφυρα  και να βγει από μια διαφορετική.Υπάρχουν όμως μόνο δυο εξαιρέσεις  σε αυτόν τον κανόνα: όταν ο περιπατητής αρχίζει ή τελειώνει το ταξίδι. Στην αρχή του ταξιδιού, ο περιπατητής αφήνει ένα κομμάτι ξηράς και χρειάζεται μια και μοναδική γέφυρα για να βγει, και στο τέλος ο περιπατητής φτάνει σε ένα κομμάτι ξηράς και  χρειάζεται μόνο μια γέφυρα για να μπει .Αν το ταξίδι αρχίζει και τελειώνει σε διαφορετικές τοποθεσίες,τότε οι δυο αυτές εκτάσεις επιτρέπεται να έχουν περιττό αριθμό γεφυρών.Αν όμως το ταξίδι αρχίζει και τελειώνει  στο ίδιο μέρος, τότε το σημείο αυτό, όπως και όλα τα αλλά σημεία, πρέπει να έχει άρτιο αριθμό γεφυρών.Έτσι ο ‘Οιλερ κατέληξε στο γενικό συμπέρασμα ότι για οποιοδήποτε δίκτυο γεφυρών, ένα πλήρες ταξίδι-περίπατο,διασχίζοντας κάθε γέφυρα μια φορά μόνο, είναι δυνατόν μόνο στην περίπτωση που όλες οι εκτάσεις ξηράς  έχουν άρτιο αριθμό γεφυρών, ή όταν δυο  ακριβώς εκτάσεις ξηράς έχουν περιττό αριθμό γεφυρών. Στην περίπτωση του Κενιγκσπεργκ υπάρχουν συνολικά τέσσερις εκτάσεις ξηράς και όλες συνδέονται με περιττό αριθμό γεφυρών.Τρία σημεία έχουν τρεις γέφυρες και ένα πέντε γέφυρες.Σήμερα, στο παλαιποτε Κένισμπεργκ έχουν απομείνει μόνο τρεις από τις επτά γέφυρες.

  

“Die fürstliche Hauptt Statt Konigsbergk in Preussen”, γενική άποψη του  Κένισμπεργκ επιχρωματισμένη χαλκογραφία από το Civitates Orbis Terrarum”, των Braun & Hogenberg, Κολωνία 1585.

Σχετικό βίντεο από το TED

                

Συναφές προβληματάκι