Königsberg Bridges Puzzle – Το Πρόβλημα που Γέννησε τη Θεωρία Γραφημάτων

🌉 Το πρόβλημα

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

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

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

🧩 Η λύση του Euler

Το 1736, ο Leonhard Euler απέδειξε ότι δεν υπάρχει τέτοια διαδρομή. Η απόδειξή του βασίστηκε σε μια απλή παρατήρηση:

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

Στο Königsberg, οι βαθμοί των κορυφών ήταν:

• Περιοχή A: 5 γέφυρες (περιττός)
• Περιοχή B: 3 γέφυρες (περιττός)
• Περιοχή C: 3 γέφυρες (περιττός)
• Περιοχή D: 3 γέφυρες (περιττός)

Όλες οι κορυφές έχουν περιττό βαθμό — άρα η διαδρομή είναι αδύνατη.

📐 Η γέννηση της θεωρίας γραφημάτων

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

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

Μια διαδρομή που διασχίζει κάθε ακμή ακριβώς μία φορά ονομάζεται πλέον διαδρομή Euler.

— Η ομάδα του eisatopon.gr

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →