tag:blogger.com,1999:blog-7136655045781905113.post6901993475633977638..comments2024-03-25T19:01:19.600+03:00Comments on Διασκεδαστικά Μαθηματικά : ΓραφογρίφοςΣωκράτης Δ. Ρωμανίδηςhttp://www.blogger.com/profile/05364191669604847034noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-7136655045781905113.post-65392849726285052952014-10-31T20:16:35.658+02:002014-10-31T20:16:35.658+02:00Αν κάποιος -σε έναν γενικότερο προβληματισμό- έθετ...Αν κάποιος -σε έναν γενικότερο προβληματισμό- έθετε το εύλογο ερώτημα "γιατί ο τύπος Grinberg ξεκινάει από κ>=3 ;" κι όχι από το 1, η απάντηση είναι πως σε έναν απλό γράφο (simple Graph) δεν έχει νόημα ως Χαμιλτονιανή διαδρομή το "πολύγωνο" πλευράς 1 (δηλαδή ο Βρόχος/loop ) ούτε οι 2 πλευρές (δηλαδή τα διπλά τόξα ,2 τόξα από τις δύο ίδιες κορυφές) αφού προφανώς αυτές οι περιπτώσεις αυτοακυρώνονται Χαμιλτονιανά, αφού απλώς επιστρέφουν ως διαδρομές σε μια κορυφή που έχουν ήδη επισκεφτεί.RIZOPOULOS GEORGIOShttps://www.blogger.com/profile/05401576457945165575noreply@blogger.comtag:blogger.com,1999:blog-7136655045781905113.post-85157718240821030802014-10-31T19:58:34.386+02:002014-10-31T19:58:34.386+02:00Θανάση, πολύ σωστά!
Το θ. του Γκρίνμπεργκ: http://...Θανάση, πολύ σωστά!<br />Το θ. του Γκρίνμπεργκ: http://en.wikipedia.org/wiki/Grinberg's_theorem<br />Πρόσθεσα στην ανάρτηση μια εικόνα που εξηγεί πώς λειτουργεί το Θεώρημα του Γκρίνμπεργκ. ∑(k - 2)(Fk - Gk) = 0 ,δηλαδή:<br />$(F3 - G3) + 2(F4 - G4) + 3(F5 - G5) + ... = 0$<br />Στην περίπτωση της εικόνας,έχουμε:<br /> F4=1, F5=1, F6=1, G3=2, G5=1 και G6=1 (εξωτερικό κύκλωμα του γραφήματος) και πιστοποιούμε όντως πως ισχύει<br />1*(0-2)+2*(1-0)+3*(1-1)+4*(1-1)=0, άρα το γράφημα είναι χαμιλτονιανό.<br />Στο πρόβλημά μας ,όπως επεσήμανε ο Θανάσης, θα πρέπει να έχουμε για να είναι χαμιλτονιανός ο γράφος:<br />$3(F5 - G5) + 6(F8 - G8) + 7(F9 - G9) = 0$ <br />Ξέρουμε τις τιμές F9=0 και G9=1 (ο 9άρης εξωτερικός κύκλος)<br />άρα 3(F5 - G5) + 6(F8 - G8) + (-1)*7=0<br />$3(F5 - G5) + 6(F8 - G8)=7$ <br />Άρα ,ανεξαρτήτως τι ακριβώς είναι οι τιμές F5,G5,F8,G8, αρκεί πως είναι ακέραιοι, θα πρέπει να υπάρχει λύση στη σχέση που παίρνει την μορφή:<br />$3*k + 6*n=7$<br />Αυτή η σχέση όμως δεν έχει προφανώς λύση modulo 3 (το 7 δεν είναι πολλαπλάσιο του 3), άρα ο πύργος του Φον Ντούμκοπφ δεν είναι χαμιλτονιανός, άρα είναι αδύνατον να ξεκινήσει κανείς από κάποιο δωμάτιο και περνώντας μια φορά απο τα υπόλοιπα να επιστρέψει στην αφετηρία του.<br /><br />RIZOPOULOS GEORGIOShttps://www.blogger.com/profile/05401576457945165575noreply@blogger.comtag:blogger.com,1999:blog-7136655045781905113.post-17938486452589308422014-10-31T17:15:10.322+02:002014-10-31T17:15:10.322+02:00Για να υπάρχει χαμιλτονιανός κύκλος (ΧΚ), θα πρέπε...Για να υπάρχει χαμιλτονιανός κύκλος (ΧΚ), θα πρέπει να ικανοποιείται το κριτήριο Grinberg: <br />Σ(ν-2)*(Π1ν-Π2ν)=0, από ν=3 έως Ν, <br />όπου Ν ο αριθμός κόμβων του γράφου, Π1ν το πλήθος των εσωτερικών τού ΧΚ πολυγώνων με ν πλευρές και Π2ν το πλήθος των αντίστοιχων εξωτερικών τού ΧΚ πολυγώνων με ν πλευρές.<br /><br />Στον γράφο του σχήματος τα πολύγωνα που σχηματίζονται από τους κόμβους είναι 5-γωνα και 8-γωνα και ένα 9-γωνο, εξωτερικά του γράφου. Οι αριθμοί 5 και 8 είναι αμφότεροι 2mod3, αλλά ο 9 είναι 0mod3. Επομένως, το οποιοδήποτε άθροισμα Grinberg θα περιλαμβάνει τρείς όρους από τους οποίους οι δύο, που αντιστοιχούν στις τιμές ν=5 και ν=8, είναι 0mod3, αλλά ο τρίτος που αντιστοιχεί σε ν=9 είναι -7=2mod3. Επομένως, δεν είναι δυνατό να ικανοποιείται το κριτήριο Grinberg και ο γράφος δεν περιέχει ΧΚ.<br />papadimhttps://www.blogger.com/profile/15678911054501824229noreply@blogger.comtag:blogger.com,1999:blog-7136655045781905113.post-9193211632994803582014-10-30T12:22:32.551+02:002014-10-30T12:22:32.551+02:00Yπόδειξη: Δεν υπάρχει τέτοια διαδρομή. Μια τέτοια ...Yπόδειξη: Δεν υπάρχει τέτοια διαδρομή. Μια τέτοια διαδρομή,που ξεκινάει από κάποιον κόμβο ενός γραφήματος και περνάει μία φορά από όλους τους υπόλοιπους πριν κλείσει ο κύκλος, λέγεται Χαμιλτονιανή (Hamiltonian Circuit ή Cycle) . Yπάρχουν διάφοροι τρόπο, να αποδειχθεί πως ένας επίπεδος Γράφος δεν περιέχει κύκλωμα Χάμιλτον. Ένας συνηθισμένος και εύκολος είναι...<br />Think Grin!(berg)RIZOPOULOS GEORGIOShttps://www.blogger.com/profile/05401576457945165575noreply@blogger.com