Σε μία συστάδα νησιών υπάρχουν $19$ νησιά. Κάθε νησί έχει γέφυρες με διόδια για τουλάχιστον τρία άλλα νησιά.
Ένας οδηγός χρησιμοποίησε μια κακή εφαρμογή χαρτογράφησης και πήγε από μία διαδρομή, η οποία περιελάμβανε τη διέλευση $12$ γεφυρών.
Δείξτε ότι πρέπει να υπάρχει μια διαδρομή με λιγότερες γέφυρες.
Υπάρχουν νομίζω ασάφειες:
ΑπάντησηΔιαγραφή1.Καθένα από τα 19 νησιά συνδέεται με 3 τουλάχιστον άλλα νησιά με 3 γέφυρες αντίστοιχα;
2.Καθεμιά από τις 12 γέφυρες την πέρασε 1 ακριβώς φορά ή όχι απαραίτητα;
3. Ο οδηγός πέρασε και από τα 19 νησιά;
Υποθέτω ότι αρχικά ο οδηγός βρίσκεται σε οποιοδήποτε από τα 19 νησιά και έχει προορισμό οποιοδήποτε άλλο, οπότε πρέπει να δείξουμε ότι αυτό μπορεί να το καταφέρει με λιγότερες από 12 διελεύσεις γεφυρών.
ΑπάντησηΔιαγραφήΑν προσομοιώσουμε την κατάσταση με ένα επίπεδο (planar) γράφημα, αυτό θα έχει v=19 κορυφές (νησιά) και τουλάχιστον 3*19/2=28,5, δηλαδή τουλάχιστον e=29 ακμές (γέφυρες μεταξύ δύο νησιών). Από τη φόρμουλα Euler, v-e+f=2 (όπου f ο αριθμός εδρών, δηλαδή των κλειστών συνδέσεων τριών τουλάχιστον κορυφών μέσω ακμών), είναι f=e-v+2≥12. Προφανώς, η δυσμενέστερη περίπτωση ως προς το αποδεικτέο είναι η e=29=>f=12 και σε αυτές περιλαμβάνεται 1 εξωτερική έδρα, που περικλείει όλες τις κορυφές και όλες τις ακμές), αφού όσο περισσότερες συνδέσεις (ακμές/γέφυρες) έχει ένα νησί, τόσο περισσότερες επιλογές διαδρομών έχει ο οδηγός. Στην περίπτωσή μας, ο οδηγός ξεκίνησε από την κορυφή Α και κατέληξε στην κορυφή Ω, διερχόμενος από 12 γέφυρες/ακμές. Αλλά κάθε ακμή χωρίζει 2 έδρες, οπότε θα μπορούσε να καταφέρει το ίδιο το πολύ με 12/2=6 έως 12-1=11 διελεύσεις.