ΟΙ ΓΕΦΥΡΕΣ ΤΟΥ ΚΕΝΙΝΓΚΣΜΠΕΡΓΚ
Οι γέφυρες του Κένινγκσμπεργκ
Τα πέντε δωμάτια
Ο αστυνόμος (Ι)
Ο αστυνόμος (ΙΙ)
Μονοκονδυλιά (Ι)
Μονοκονδυλιά (ΙΙ)
1. Οι επτά γέφυρες του Κένινγκσμπεργκ
Το Κένινγκσμπεργκ ήταν μια γερμανική πόλη. Μετά τον Β΄ Παγκόσμιο Πόλεμο, ανήκει στη Ρωσία και ονομάζεται Καλίνινγκραντ. Μέσα από την πόλη περνάει ο ποταμός Πρεγκόλια και τη χωρίζει σε τέσσερις περιοχές, οι οποίες παλαιότερα συνδέονταν μεταξύ τους με επτά γέφυρες, όπως φαίνεται στο παρακάτω σχήμα. Οι κάτοικοι του Κένινγκσμπεργκ, στους οποίους άρεσαν οι περίπατοι, προσπαθούσαν να βρουν μια διαδρομή που να περνάει από κάθε γέφυρα μία μόνο φορά, χωρίς όμως αποτέλεσμα. Ο μεγάλος μαθηματικός Euler (Όιλερ) το 1735 εξέτασε το πρόβλημα και απέδειξε ότι δεν υπήρχε τέτοια διαδρομή. Η ανάλυση του προβλήματος από τον Euler έθεσε τα θεμέλια του κλάδου των μαθηματικών που ονομάζεται θεωρία γραφημάτων ή γράφων (graph theory).
Σε αυτό το πρόβλημα, δεν έχει καμία σημασία η έκταση των περιοχών της πόλης, ούτε το μήκος των γεφυρών, αλλά μόνο ποιες περιοχές της πόλης συνέδεε η κάθε γέφυρα. Έτσι, οι περιοχές της πόλης μπορούν να παρασταθούν με σημεία (κόμβους) και οι γέφυρες που συνέδεαν αυτές τις περιοχές μπορούν να παρασταθούν με γραμμές (ακμές), όπως φαίνεται στο παρακάτω γράφημα.
Το ερώτημα, λοιπόν, που πρέπει κανείς να απαντήσει είναι αν υπάρχει μια διαδρομή η οποία να περνάει από κάθε ακμή του γραφήματος μία μόνο φορά. Όπως θα δειχθεί στη συνέχεια, αυτό εξαρτάται από τον αριθμό των ακμών που συνδέουν κάθε κόμβο με τους υπόλοιπους. Ο αριθμός αυτός λέγεται βαθμός του κόμβου. Ο βαθμός των κόμβων Α, Γ και Δ είναι 3, ενώ του Β είναι 5.
Παρατηρήστε ότι κάθε φορά που περνάτε από έναν κόμβο χρησιμοποιείτε μια ακμή για να φτάσετε σε αυτόν και μια ακμή για να φύγετε από αυτόν. Άρα, αν πρέπει να χρησιμοποιήσετε κάθε ακμή μία μόνο φορά, οι κόμβοι από τους οποίους περνάτε πρέπει να έχουν άρτιο βαθμό. Αντίθετα, χρειάζεστε μια ακμή για να φύγετε από τον κόμβο που είναι η αρχή της διαδρομής ή για να φτάσετε στον κόμβο που είναι το τέλος της διαδρομής, εκτός από τα ζεύγη των ακμών που χρειάζεστε απλώς για να περάσετε από αυτούς τους κόμβους. Άρα, ο κόμβος που είναι η αρχή της διαδρομής και ο κόμβος που είναι το τέλος της πρέπει να έχουν περιττό βαθμό, εκτός και αν συμπίπτουν.
Συνεπώς, υπάρχει διαδρομή που περνάει από κάθε ακμή ενός γραφήματος μία μόνο φορά στις εξής δύο μόνο περιπτώσεις:
Α. Όλοι οι κόμβοι του γραφήματος έχουν βαθμό άρτιο. Σε αυτή την περίπτωση, η αρχή και το τέλος της διαδρομής είναι ο ίδιος κόμβος.
Β. Δύο κόμβοι του γραφήματος έχουν περιττό βαθμό και οι υπόλοιποι έχουν άρτιο βαθμό. Σε αυτή την περίπτωση, ο ένας κόμβος περιττού βαθμού είναι η αρχή της διαδρομής και ο άλλος είναι το τέλος της.
Όσον αφορά το πρόβλημα με τις γέφυρες του Κένινγκσμπεργκ, και οι τέσσερις κόμβοι του γραφήματος έχουν περιττό βαθμό, άρα δεν υπάρχει διαδρομή που να περνάει από κάθε ακμή του μία μόνο φορά. Επομένως, οι κάτοικοι του Κένινγκσμπεργκ, όσο και αν προσπαθούσαν, ποτέ δεν θα κατόρθωναν κατά τη διάρκεια ενός περιπάτου να περάσουν από κάθε γέφυρα μία μόνο φορά.
Έπειτα από όλα αυτά, δεν νομίζω ότι θα δυσκολευτείτε να απαντήσετε στο εξής ερώτημα: Υποθέστε ότι οι κάτοικοι του Κένινγκσμπεργκ συνέδεαν τις περιοχές Β και Δ με μία επιπλέον γέφυρα. Θα ήταν τότε δυνατόν, ξεκινώντας έναν περίπατο από κάποιο σημείο της πόλης τους, να περάσουν από κάθε γέφυρα μία μόνο φορά;
Σχεδιάστε το παρακάτω γράφημα, όπου οι περιοχές της πόλης παριστάνονται με κόμβους και οι γέφυρες με ακμές. Οι κόμβοι Α και Γ έχουν περιττό βαθμό και οι κόμβοι Β και Δ έχουν άρτιο βαθμό. Αφού υπάρχουν μόνο δύο κόμβοι περιττού βαθμού και οι άλλοι είναι άρτιου βαθμού, υπάρχει διαδρομή με άκρα τους κόμβους Α και Γ η οποία περνάει από κάθε ακμή του γραφήματος μία μόνο φορά.
Συνεπώς, αν μία επιπλέον γέφυρα συνέδεε την περιοχή Β με την περιοχή Δ, θα ήταν δυνατόν για τους κατοίκους του Κένινγκσμπεργκ, ξεκινώντας από την περιοχή Α ή Γ, να περάσουν από κάθε γέφυρα μία μόνο φορά και να καταλήξουν στην περιοχή Γ ή Α αντίστοιχα.
Μία από τις πολλές διαδρομές που θα μπορούσαν να ακολουθήσουν είναι η εξής:
Α → Β → Γ → Β → Α → Δ → Β → Δ → Γ
2. Τα πέντε δωμάτια
Στο παρακάτω σχέδιο, βλέπετε την κάτοψη ενός σπιτιού. Το σπίτι, όπως παρατηρείτε, έχει πέντε δωμάτια και αρκετές πόρτες με τις οποίες επικοινωνούν τα δωμάτια τόσο μεταξύ τους όσο και με τον εξωτερικό χώρο. Μπορείτε να σχεδιάσετε μια διαδρομή που να περνάει από κάθε πόρτα μία μόνο φορά;
Δεν υπάρχει καμία διαδρομή που να περνάει από κάθε πόρτα του σπιτιού μία μόνο φορά.
Παρατηρήστε ότι κάθε φορά που περνάτε από κάποιον από τους χώρους οι οποίοι δεν είναι η αρχή ή το τέλος της διαδρομής σας χρησιμοποιείτε μια πόρτα για να μπείτε σε αυτόν και μια πόρτα για να βγείτε από αυτόν. Άρα, αν πρέπει να περάσετε από κάθε πόρτα μία μόνο φορά, αυτοί οι χώροι πρέπει να έχουν άρτιο αριθμό πορτών. Αντίθετα, χρειάζεστε μια πόρτα για να βγείτε από τον χώρο που είναι η αρχή της διαδρομής σας ή για να μπείτε στον χώρο που είναι το τέλος της, εκτός από τα ζεύγη πορτών που χρειάζεστε απλώς για να περάσετε από αυτούς τους χώρους. Άρα, η αρχή και το τέλος της διαδρομής σας πρέπει να έχουν περιττό αριθμό πορτών, εκτός και αν πρόκειται για τον ίδιο χώρο. Αν, λοιπόν, υπήρχαν δύο χώροι με περιττό αριθμό πορτών, τότε ο ένας θα ήταν η αρχή και ο άλλος το τέλος της διαδρομής σας. Υπάρχουν, όμως, τέσσερις χώροι (τρία δωμάτια και ο εξωτερικός χώρος) με περιττό αριθμό πορτών. Επομένως, δεν υπάρχει διαδρομή που να περνάει από κάθε πόρτα μία μόνο φορά.
Επίσης, για να εξετάσατε αυτό το πρόβλημα, μπορείτε να κάνετε το παρακάτω γράφημα. Σε αυτό, οι χώροι παριστάνονται με κόμβους και οι πόρτες με ακμές. Οι κόμβοι 1 έως 5 παριστάνουν τα δωμάτια και ο κόμβος 6 τον εξωτερικό χώρο. Οι κόμβοι 3 και 5 είναι άρτιου βαθμού και οι κόμβοι 1, 2, 4 και 6 είναι περιττού βαθμού (δείτε τη σπαζοκεφαλιά «Οι γέφυρες του Κένιγκσμπεργκ»). Υπάρχουν τέσσερις κόμβοι περιττού βαθμού, επομένως δεν υπάρχει διαδρομή που να περνάει από κάθε ακμή μία μόνο φορά. Αυτό σημαίνει ότι δεν είναι δυνατόν να σχεδιάσετε μια διαδρομή που να περνάει από κάθε πόρτα του σπιτιού μία μόνο φορά.
3. Ο αστυνόμος (Ι)
Ένας αστυνόμος περνάει κάθε μέρα από όλους τους δρόμους γύρω από τα οικοδομικά τετράγωνα που φαίνονται στο σχήμα. Ξεκινάει πάντοτε από τη γωνία Α και καταλήγει στην ίδια γωνία, και κάθε φορά διαπιστώνει ότι πρέπει να περάσει από κάποιους δρόμους δύο φορές. Από ποιους δρόμους πρέπει να περνάει δύο φορές για να είναι η απόσταση που διανύει η μικρότερη δυνατή;
Στο παρακάτω γράφημα, οι κόμβοι παριστάνουν τις διασταυρώσεις των δρόμων και οι ακμές μεταξύ των κόμβων παριστάνουν τους δρόμους. Επειδή οκτώ κόμβοι είναι περιττού βαθμού, δεν υπάρχει διαδρομή που να περνάει από κάθε ακμή μία μόνο φορά (δείτε τη σπαζοκεφαλιά «Οι γέφυρες του Κένινγκσμπεργκ»). Για να υπάρξει μια τέτοια διαδρομή, η οποία επιπροσθέτως να ξεκινάει και να καταλήγει στον κόμβο Α, πρέπει όλοι οι κόμβοι να γίνουν άρτιου βαθμού. Ο απλούστερος τρόπος για να γίνει αυτό είναι να προστεθούν ακμές μεταξύ των κόμβων Β και Γ, Θ και Μ, Ξ και Ο, Ε και Ι. Δύο ακμές μεταξύ δύο κόμβων σημαίνει ότι ο αστυνόμος θα περνάει δύο φορές από τα αντίστοιχα τμήματα των δρόμων.
4. Ο αστυνόμος (ΙΙ)
Ένας αστυνόμος περνάει κάθε μέρα από όλους τους δρόμους γύρω από τα οικοδομικά τετράγωνα που φαίνονται στο σχήμα. Ξεκινάει πάντοτε από τη γωνία Α και καταλήγει στην γωνία Μ, και κάθε φορά διαπιστώνει ότι πρέπει να περάσει από κάποιους δρόμους δύο φορές. Από ποιους δρόμους πρέπει να περνάει δύο φορές για να είναι η απόσταση που διανύει η μικρότερη δυνατή;
Στο παρακάτω γράφημα, οι κόμβοι παριστάνουν τις διασταυρώσεις των δρόμων και οι ακμές μεταξύ των κόμβων παριστάνουν τους δρόμους. Για να υπάρχει μια διαδρομή η οποία να ξεκινάει από τον κόμβο Α, να περνάει από κάθε ακμή μία μόνο φορά και να καταλήγει στον κόμβο Μ, πρέπει οι κόμβοι Α και Μ να είναι περιττού βαθμού και όλοι οι άλλοι κόμβοι να είναι άρτιου βαθμού (δείτε τη σπαζοκεφαλιά «Οι γέφυρες του Κένινγκσμπεργκ»). Ο απλούστερος τρόπος για να γίνει αυτό είναι να προστεθούν ακμές μεταξύ των κόμβων Α και Ε, Β και Γ, Κ και Λ, Θ και Μ. Δύο ακμές μεταξύ δύο κόμβων σημαίνει ότι ο αστυνόμος θα περνάει δύο φορές από τα αντίστοιχα τμήματα των δρόμων.
5. Μονοκονδυλιά (Ι)
Μπορείτε να σχεδιάσετε το καθένα από τα παρακάτω σχήματα χωρίς να σηκώσετε το μολύβι σας από το χαρτί; Δεν επιτρέπεται να περάσετε με το μολύβι σας πάνω από τμήμα γραμμής που έχετε ήδη σχεδιάσει, επιτρέπεται όμως να περάσετε πάνω από ένα σημείο της.
Όλοι οι κόμβοι του πρώτου σχήματος είναι άρτιου βαθμού, επομένως είναι δυνατόν να σχεδιαστεί με μια μονοκονδυλιά από οποιονδήποτε κόμβο και αν ξεκινήσετε (δείτε τη σπαζοκεφαλιά «Οι επτά γέφυρες του Κένινγκσμπεργκ»). Η αρχή και το τέλος της μονοκονδυλιάς συμπίπτουν.
Δύο κόμβοι του δεύτερου σχήματος είναι περιττού βαθμού, επομένως πρέπει να ξεκινήσετε από τον έναν από αυτούς τους δύο κόμβους, για να είναι δυνατή η σχεδίαση του σχήματος με μια μονοκονδυλιά. Το τέλος της μονοκονδυλιάς είναι ο άλλος κόμβος περιττού βαθμού.
Μία λύση για την καθεμία περίπτωση φαίνεται στα παρακάτω σχήματα.
6. Μονοκονδυλιά (ΙΙ)
Ποια από τα τρία παρακάτω σχήματα μπορείτε να σχεδιάσετε χωρίς να σηκώσετε το μολύβι σας από το χαρτί; Δεν επιτρέπεται να περάσετε με το μολύβι σας πάνω από τμήμα γραμμής που έχετε ήδη σχεδιάσει, επιτρέπεται όμως να περάσετε πάνω από ένα σημείο της.
Στο πρώτο και στο δεύτερο σχήμα, δύο κόμβοι είναι περιττού βαθμού (δείτε τη σπαζοκεφαλιά «Οι επτά γέφυρες του Κένινγκσμπεργκ»). Άρα, πρέπει να ξεκινήσετε από τον έναν από αυτούς τους δύο κόμβους, για να είναι δυνατή η σχεδίαση αυτών των σχημάτων με μια μονοκονδυλιά. Το τέλος της μονοκονδυλιάς είναι ο άλλος κόμβος περιττού βαθμού. Μία λύση για το καθένα από αυτά τα δύο σχήματα φαίνεται παρακάτω.
Στο τρίτο σχήμα, υπάρχουν τέσσερις κόμβοι περιττού βαθμού: ο Α, ο Β, ο Γ και ο Δ. Άρα, δεν είναι δυνατόν να σχεδιαστεί αυτό το σχήμα με μια μονοκονδυλιά.
Last updated