 |
Το Ιστορικό Πλαίσιο
Φανταστείτε την πόλη του Κένιγκσμπεργκ (σημερινό Καλίνινγκραντ της Ρωσίας) τον 18ο αιώνα. Η πόλη ήταν χτισμένη γύρω από τον ποταμό Πρέγκελ, ο οποίος χώριζε την ξηρά σε τέσσερις περιοχές: δύο μεγάλες νησιωτικές περιοχές και δύο ηπειρωτικές ακτές. Αυτές οι τέσσερις περιοχές συνδέονταν μεταξύ τους με επτά γέφυρες.
Ο κόσμος του Κένιγκσμπεργκ είχε μια συνήθεια: ήθελαν να βρουν έναν τρόπο να περπατήσουν μέσα στην πόλη, διασχίζοντας κάθε μία από τις επτά γέφυρες ακριβώς μία φορά και επιστρέφοντας στο σημείο εκκίνησης (ή απλώς να περάσουν από όλες). Φαίνεται απλό, έτσι δεν είναι; Ωστόσο, κανείς δεν τα κατάφερνε. Πολλοί προσπάθησαν, πολλοί απογοητεύτηκαν.
Η Επέμβαση του Λέοναρντ Όιλερ
Εδώ έρχεται ο Λέοναρντ Όιλερ (Leonhard Euler), ένας από τους μεγαλύτερους μαθηματικούς όλων των εποχών. Το 1736, ο Όιλερ ασχολήθηκε με το πρόβλημα και, αντί να προσπαθήσει να βρει μια λύση διασχίζοντας τις γέφυρες, αποφάσισε να αλλάξει τον τρόπο προσέγγισης. Αυτή η αλλαγή οπτικής ήταν επαναστατική.
Ο Όιλερ αντιλήφθηκε ότι η ακριβής μορφή των γεφυρών ή οι αποστάσεις μεταξύ των περιοχών δεν είχαν καμία σημασία. Το μόνο που είχε σημασία ήταν οι συνδέσεις. Μετέτρεψε το πρόβλημα από ένα γεωγραφικό σε ένα αφηρημένο πρόβλημα.
Αντιπροσώπευσε κάθε περιοχή ξηράς (τις δύο όχθες και τα δύο νησιά) ως ένα σημείο ή κορυφή (vertex).
Αντιπροσώπευσε κάθε γέφυρα ως μια γραμμή ή ακμή (edge) που συνδέει τις αντίστοιχες κορυφές.
Με αυτόν τον τρόπο, το πρόβλημα μετατράπηκε σε ένα γράφημα (graph):
Σε αυτό το γράφημα, οι τέσσερις κορυφές αναπαριστούν τις περιοχές της ξηράς και οι επτά ακμές τις γέφυρες.
Η Λύση και η Θεωρία Γράφων
Ο Όιλερ αναζητούσε έναν «περίπατο» στο γράφημα που να διασχίζει κάθε ακμή ακριβώς μία φορά. Τέτοιους περιπάτους τους ονομάζουμε σήμερα μονοπάτια Όιλερ (Eulerian paths) ή κύκλους Όιλερ (Eulerian circuits) αν ξεκινούν και καταλήγουν στην ίδια κορυφή.
Η βασική του παρατήρηση ήταν η εξής:
Αν ξεκινάτε και τελειώνετε τον περίπατο στην ίδια κορυφή (κύκλος Όιλερ), τότε κάθε κορυφή πρέπει να έχει άρτιο βαθμό (δηλαδή, να συνδέεται με άρτιο αριθμό ακμών). Γιατί; Γιατί κάθε φορά που μπαίνετε σε μια κορυφή μέσω μιας ακμής, πρέπει να μπορείτε να φύγετε από αυτήν μέσω μιας άλλης ακμής.
Αν ξεκινάτε και τελειώνετε τον περίπατο σε διαφορετικές κορυφές (μονοπάτι Όιλερ), τότε ακριβώς δύο κορυφές πρέπει να έχουν μονό βαθμό (η αρχική και η τελική κορυφή), ενώ όλες οι άλλες κορυφές πρέπει να έχουν άρτιο βαθμό.
Εφαρμόζοντας αυτή την παρατήρηση στο γράφημα του Κένιγκσμπεργκ:
Περιοχή A (αριστερή όχθη): 3 γέφυρες (μονός βαθμός)
Περιοχή B (δεξιά όχθη): 3 γέφυρες (μονός βαθμός)
Περιοχή C (πάνω νησί): 5 γέφυρες (μονός βαθμός)
Περιοχή D (κάτω νησί): 3 γέφυρες (μονός βαθμός)
Παρατηρούμε ότι όλες οι κορυφές έχουν μονό βαθμό! Σύμφωνα με την αρχή του Όιλερ, αυτό σημαίνει ότι δεν υπάρχει δυνατότητα να διασχίσει κανείς όλες τις γέφυρες ακριβώς μία φορά, είτε επιστρέφοντας στο σημείο εκκίνησης είτε όχι.
Ο Όιλερ απέδειξε ότι το παζλ ήταν άλυτο.
Η Κληρονομιά του Παζλ
Η σημασία της εργασίας του Όιλερ δεν ήταν απλώς η επίλυση ενός τοπικού παζλ. Ήταν η γέννηση της Θεωρίας Γράφων (Graph Theory). Αυτός ο κλάδος των μαθηματικών μελετά τα δίκτυα και τις σχέσεις μεταξύ αντικειμένων, ανεξάρτητα από τη φυσική τους φύση.
Σήμερα, η Θεωρία Γράφων έχει εφαρμογές σε αμέτρητα πεδία:
Πληροφορική: Σχεδιασμός δικτύων υπολογιστών, αλγόριθμοι αναζήτησης στο διαδίκτυο (π.χ., ο αλγόριθμος του Google PageRank).
Βιολογία: Ανάλυση γενετικών δικτύων, δομή πρωτεϊνών.
Κοινωνικές Επιστήμες: Μελέτη κοινωνικών δικτύων, διάδοση πληροφοριών.
Μεταφορές: Βελτιστοποίηση διαδρομών, σχεδιασμός συγκοινωνιών.
Χημεία: Αναπαράσταση μοριακών δομών.
Από ένα φαινομενικά απλό παζλ, ο Όιλερ μας έδειξε ότι με την κατάλληλη αφαίρεση και την εστίαση στις θεμελιώδεις δομές, μπορούμε να ξεκλειδώσουμε βαθύτερες μαθηματικές αρχές που έχουν εφαρμογές σε ολόκληρο τον κόσμο γύρω μας. Το παζλ των επτά γεφυρών του Κένιγκσμπεργκ είναι ένα λαμπρό παράδειγμα του πώς η περιέργεια και η συστηματική σκέψη μπορούν να οδηγήσουν σε πρωτοποριακές ανακαλύψεις.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου