Αυτή είναι η κάτοψη του πύργου του διάσημου μαθηματικού Von Dumkopf .
Οι κύκλοι δείχνουν τα δωμάτια του πύργου που συνδέονται με διαδρόμους όπως φαίνεται στο σκίτσο. Βρείτε μια διαδρομή που να ξεκινάει από κάποιο δωμάτιο και αφού περάσει άπαξ από καθένα από όλα τα υπόλοιπα δωμάτια, να καταλήγει ξανά στο αρχικό δωμάτιο απ' όπου ξεκίνησε,ή αποδείξτε πως τέτοια διαδρομή δεν υπάρχει.
Yπόδειξη: Δεν υπάρχει τέτοια διαδρομή. Μια τέτοια διαδρομή,που ξεκινάει από κάποιον κόμβο ενός γραφήματος και περνάει μία φορά από όλους τους υπόλοιπους πριν κλείσει ο κύκλος, λέγεται Χαμιλτονιανή (Hamiltonian Circuit ή Cycle) . Yπάρχουν διάφοροι τρόπο, να αποδειχθεί πως ένας επίπεδος Γράφος δεν περιέχει κύκλωμα Χάμιλτον. Ένας συνηθισμένος και εύκολος είναι...
ΑπάντησηΔιαγραφήThink Grin!(berg)
Για να υπάρχει χαμιλτονιανός κύκλος (ΧΚ), θα πρέπει να ικανοποιείται το κριτήριο Grinberg:
ΑπάντησηΔιαγραφήΣ(ν-2)*(Π1ν-Π2ν)=0, από ν=3 έως Ν,
όπου Ν ο αριθμός κόμβων του γράφου, Π1ν το πλήθος των εσωτερικών τού ΧΚ πολυγώνων με ν πλευρές και Π2ν το πλήθος των αντίστοιχων εξωτερικών τού ΧΚ πολυγώνων με ν πλευρές.
Στον γράφο του σχήματος τα πολύγωνα που σχηματίζονται από τους κόμβους είναι 5-γωνα και 8-γωνα και ένα 9-γωνο, εξωτερικά του γράφου. Οι αριθμοί 5 και 8 είναι αμφότεροι 2mod3, αλλά ο 9 είναι 0mod3. Επομένως, το οποιοδήποτε άθροισμα Grinberg θα περιλαμβάνει τρείς όρους από τους οποίους οι δύο, που αντιστοιχούν στις τιμές ν=5 και ν=8, είναι 0mod3, αλλά ο τρίτος που αντιστοιχεί σε ν=9 είναι -7=2mod3. Επομένως, δεν είναι δυνατό να ικανοποιείται το κριτήριο Grinberg και ο γράφος δεν περιέχει ΧΚ.
Θανάση, πολύ σωστά!
ΑπάντησηΔιαγραφήΤο θ. του Γκρίνμπεργκ: http://en.wikipedia.org/wiki/Grinberg's_theorem
Πρόσθεσα στην ανάρτηση μια εικόνα που εξηγεί πώς λειτουργεί το Θεώρημα του Γκρίνμπεργκ. ∑(k - 2)(Fk - Gk) = 0 ,δηλαδή:
$(F3 - G3) + 2(F4 - G4) + 3(F5 - G5) + ... = 0$
Στην περίπτωση της εικόνας,έχουμε:
F4=1, F5=1, F6=1, G3=2, G5=1 και G6=1 (εξωτερικό κύκλωμα του γραφήματος) και πιστοποιούμε όντως πως ισχύει
1*(0-2)+2*(1-0)+3*(1-1)+4*(1-1)=0, άρα το γράφημα είναι χαμιλτονιανό.
Στο πρόβλημά μας ,όπως επεσήμανε ο Θανάσης, θα πρέπει να έχουμε για να είναι χαμιλτονιανός ο γράφος:
$3(F5 - G5) + 6(F8 - G8) + 7(F9 - G9) = 0$
Ξέρουμε τις τιμές F9=0 και G9=1 (ο 9άρης εξωτερικός κύκλος)
άρα 3(F5 - G5) + 6(F8 - G8) + (-1)*7=0
$3(F5 - G5) + 6(F8 - G8)=7$
Άρα ,ανεξαρτήτως τι ακριβώς είναι οι τιμές F5,G5,F8,G8, αρκεί πως είναι ακέραιοι, θα πρέπει να υπάρχει λύση στη σχέση που παίρνει την μορφή:
$3*k + 6*n=7$
Αυτή η σχέση όμως δεν έχει προφανώς λύση modulo 3 (το 7 δεν είναι πολλαπλάσιο του 3), άρα ο πύργος του Φον Ντούμκοπφ δεν είναι χαμιλτονιανός, άρα είναι αδύνατον να ξεκινήσει κανείς από κάποιο δωμάτιο και περνώντας μια φορά απο τα υπόλοιπα να επιστρέψει στην αφετηρία του.
Αν κάποιος -σε έναν γενικότερο προβληματισμό- έθετε το εύλογο ερώτημα "γιατί ο τύπος Grinberg ξεκινάει από κ>=3 ;" κι όχι από το 1, η απάντηση είναι πως σε έναν απλό γράφο (simple Graph) δεν έχει νόημα ως Χαμιλτονιανή διαδρομή το "πολύγωνο" πλευράς 1 (δηλαδή ο Βρόχος/loop ) ούτε οι 2 πλευρές (δηλαδή τα διπλά τόξα ,2 τόξα από τις δύο ίδιες κορυφές) αφού προφανώς αυτές οι περιπτώσεις αυτοακυρώνονται Χαμιλτονιανά, αφού απλώς επιστρέφουν ως διαδρομές σε μια κορυφή που έχουν ήδη επισκεφτεί.
ΑπάντησηΔιαγραφή