Οι Γέφυρες του Κένιγκσμπεργκ: Γέννηση της Θεωρίας Γράφων

Στην παλιά πόλη του Κένιγκσμπεργκ, στον ποταμό Πρεγκελιά, υπήρχαν τέσσερις περιοχές γης που συνδέονταν με επτά γέφυρες:

Οι κάτοικοι αναρωτιούνταν κάτι πολύ απλό στην εκφώνηση, αλλά εξαιρετικά δύσκολο στην επίλυση:

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

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

Ο Όιλερ απέδειξε ότι **δεν είναι δυνατό** να διασχίσουμε κάθε γέφυρα μία φορά και μόνο. Το πρόβλημα μετατράπηκε σε **γράφο**, όπου οι περιοχές είναι κόμβοι και οι γέφυρες ακμές. Αν ένας τέτοιος «περίπατος» είναι εφικτός, τότε κάθε κόμβος πρέπει να έχει **ζυγό πλήθος ακμών**, εκτός από 0 ή 2 κόμβους (αρχή και τέλος). Στο Κένιγκσμπεργκ, **όλοι οι κόμβοι έχουν περιτμό βαθμό**, άρα η βόλτα είναι **αδύνατη**.