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

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

Το Πρόβλημα

Η πόλη του Königsberg (σημερινό Καλίνινγκραντ στη Ρωσία) χωριζόταν από τον ποταμό Pregel, ο οποίος σχημάτιζε δύο μεγάλα νησιά. Έτσι η πόλη αποτελούνταν από 4 τμήματα ξηράς:

• Οι δύο όχθες του ποταμού

• Δύο νησιά στο μέσον του

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

Το ερώτημα ήταν:

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

---

Η Ιδέα του Euler

Ο Euler σκέφτηκε να αγνοήσει τα γεωμετρικά χαρακτηριστικά (ποτάμι, σχήματα, αποστάσεις) και να κρατήσει μόνο τη δομή των συνδέσεων.

Έτσι:

• Κάθε κομμάτι ξηράς έγινε ένα σημείο (κόμβος).

• Κάθε γέφυρα έγινε μια γραμμή (ακμή) που ενώνει δύο κόμβους.

Με αυτό τον τρόπο δημιούργησε ένα από τα πρώτα παραδείγματα γραφημάτων στην ιστορία.

---

Η Λύση

Ο Euler απέδειξε ότι:

• Για να υπάρχει μια διαδρομή που περνά από κάθε ακμή (γέφυρα) ακριβώς μία φορά, πρέπει το πολύ δύο κόμβοι να έχουν περιττό αριθμό γεφυρών (βαθμό).

• Στο Königsberg, και οι τέσσερις περιοχές είχαν περιττό αριθμό γεφυρών.

Άρα: ❌ Δεν υπάρχει τέτοια διαδρομή.

---

Σημασία

• Το πρόβλημα των επτά γεφυρών είναι το πρώτο θεμελιώδες αποτέλεσμα στη θεωρία γραφημάτων.

• Έδειξε πώς η αφαίρεση από το φυσικό πρόβλημα σε καθαρά μαθηματική δομή μπορεί να αποκαλύψει βαθιές ιδέες.

• Άνοιξε τον δρόμο για την ανάπτυξη της τοπολογίας και πολλών εφαρμογών στη σύγχρονη επιστήμη (δίκτυα, αλγόριθμοι, υπολογιστές).