 |
| O Έρντος με το βιβλίο.... |
Είναι γνωστή η ιστορία για τον τρόπο που χαρακτήριζε ο Ούγγρος μαθηματικός Πωλ Έρντος τις κομψές μαθηματικές αποδείξεις.Έλεγε: Είναι μέσα από το βιβλίο, εννοώντας ότι ο Θεός έχει συγκεντρώσει σε ένα βιβλίο όλα τα μαθηματικά θεωρήματα το καθένα με την πλέον όμορφη απόδειξη του.Από καιρό σε καιρό...ξεχνάει το βιβλίο ανοιχτό και οι μαθηματικοί κρυφοκοιτάζουν....
Μια απόδειξη από το βιβλίο
Το θεώρημα φύλαξης του μουσείου (Αrt gallery problem) είναι ένα γνωστό πρόβλημα υπολογιστικής γεωμετρίας.Τέθηκε το 1973,από τον Αμερικανό μαθηματικό Victor Clee.Το απέδειξε το 1975,ο μαθηματικός Václav Chvátal.Περίπου πέντε χρόνια αργότερα ένας άλλος μαθηματικός, ο S.Fisk επανήλθε με μια κομψή απόδειξη.
Το πρόβλημα
Ας υποθέσουμε ότι σε ένα μουσείο έχουμε μια μεγάλη αίθουσα με εκθέματα και θέλουμε να προσλάβουμε ικανό αριθμό φυλάκων έτσι ώστε κάθε σημείο της αίθουσας να εποπτεύεται από κάποιο φύλακα.Οι φύλακες θα θεωρήσουμε ότι είναι στατικοί,δηλαδή δεν κινούνται και ενδεχομένως θα μπορούσαν να αντικατασταθούν από κάμερες.
Ας υποθέσουμε ότι σε ένα μουσείο έχουμε μια μεγάλη αίθουσα με εκθέματα και θέλουμε να προσλάβουμε ικανό αριθμό φυλάκων έτσι ώστε κάθε σημείο της αίθουσας να εποπτεύεται από κάποιο φύλακα.Οι φύλακες θα θεωρήσουμε ότι είναι στατικοί,δηλαδή δεν κινούνται και ενδεχομένως θα μπορούσαν να αντικατασταθούν από κάμερες.
Το ερώτημα: Ποιος είναι ο ελάχιστος αριθμός φυλάκων για να εποπτεύεται πλήρως η αίθουσα;
Η αίθουσα
του μουσείου έχει κάτοψη ένα απλό κλειστό πολύγωνο,με την λέξη απλό θεωρούμε ότι οι πλευρές του είναι ευθύγραμμα τμήματα που όμως δεν
τέμνονται μεταξύ τους. Επίσης,θεωρούμε ότι οι φύλακες θα τοποθετηθούν στις κορυφές του
πολυγώνου. Είναι προφανές ότι ο ελάχιστος αριθμός φυλάκων εξαρτάται από τον
αριθμό ν των κορυφών του πολυγώνου.
Αποδεικνύεται ότι, για την πλήρη φύλαξη και επόπτευση μιας απλής κλειστής πολυγωνικής αίθουσας με ν πλευρές (τοίχους)-ότι σχήμα και να έχει-απαιτούνται το πολύ [ν/3] φύλακες.
('Οπου [x] είναι το ακέραιο μέρος του αριθμού x ,δηλαδή ο μεγαλύτερος ακέραιος που δεν υπερβαίνει τον ίδιο τον αριθμό x)
Δηλαδή,στο παρακάτω σχήμα με 9 κορυφές,απαιτούνται το πολύ [9/3]=3 φύλακες.
Αποδεικνύεται ότι, για την πλήρη φύλαξη και επόπτευση μιας απλής κλειστής πολυγωνικής αίθουσας με ν πλευρές (τοίχους)-ότι σχήμα και να έχει-απαιτούνται το πολύ [ν/3] φύλακες.
('Οπου [x] είναι το ακέραιο μέρος του αριθμού x ,δηλαδή ο μεγαλύτερος ακέραιος που δεν υπερβαίνει τον ίδιο τον αριθμό x)
Δηλαδή,στο παρακάτω σχήμα με 9 κορυφές,απαιτούνται το πολύ [9/3]=3 φύλακες.
Πως αποδεικνύεται;
Ο φύλακας μπορεί να εποπτεύσει ένα
σημείο Α αν δεν παρεμβάλλεται τοίχος
ανάμεσα σε αυτόν και το Α.Σχηματικά αυτό μπορεί να αποδοθεί από το αν υπάρχει
ένα ευθύγραμμο τμήμα που θα ενώνει το φύλακα με το Α που θα βρίσκεται ολόκληρο
στο εσωτερικό του πολυγώνου,δηλαδή να μην παρεμβάλλεται πλευρά του πολυγώνου (τοίχος) ανάμεσα στο φύλακα και το Α.Εύκολα γίνεται αντιληπτό ότι,το πρόβλημα ανάγεται στο να μπορούμε να «τεμαχίσουμε» το πολύγωνο σε τομείς
οι οποίοι μπορούν να εποπτευτούν από
φύλακες τοποθετημένους σε κορυφές των τομέων.Μια τέτοια
διάταξη φυλάκων αποτελεί λύση του
προβλήματος.
Πως θα χωρίσουμε το πολύγωνο;
Μια μέθοδος για να το κάνουμε είναι
να το χωρίσουμε σε τρίγωνα.Φέρνουμε διαγώνιους έτσι ώστε να μην τέμνονται.Η διαδικασία ονομάζεται τριγωνοποιήση.Υπάρχουν πολλές τριγωνοποιησεις για το ίδιο σχήμα.
Δείτε το παρακάτω σχήμα.
Δείτε το παρακάτω σχήμα.
Προφανώς ένας
φύλακας που τοποθετείται σε μια κορυφή
ενός τριγώνου μπορεί να εποπτεύσει ολόκληρο το τρίγωνο.Το τρίγωνο είναι
κυρτό σχήμα δηλαδή κάθε ευθύγραμμο τμήμα που ενώνει δυο σημεία του βρίσκεται
εξολοκλήρου μέσα στο τρίγωνο.Άρα,μια πρώτη σκέψη είναι ότι οι θέσεις των φυλάκων θα είναι σίγουρα σε κορυφές τρίγωνων. Επίσης,παρατηρούμε ότι όταν δυο ή περισσότερα τρίγωνα έχουν κοινή κορυφή
ο φύλακας πρέπει να τοποθετηθεί σε αυτήν για να τα εποπτεύει όλα.Πως θα γίνει
η τοποθέτηση και πόσοι φύλακες θα απαιτηθούν;
Καταφεύγουμε στην θεωρία γράφων.Χρωματίζουμε τις κορυφές των τριγώνων με διαφορετικά χρώματα με τέτοιο τρόπο έτσι ώστε κάθε δυο γειτονικές κορυφές δεν έχουν το ίδιο χρώμα.Ποιος είναι ο ελάχιστος αριθμός διαφορετικών χρωμάτων που απαιτείται στο παραπάνω σχήμα και καλύπτει την παραπάνω προϋπόθεση;Απάντηση,μόνο 3.
Δείτε το σχήμα.Αν θεωρήσουμε τους φύλακες στις κορυφές με κόκκινο χρώμα τότε αυτοί εποπτευουν όλη την αίθουσα,συνεπώς οι κόκκινοι φύλακες αποτελούν μια λύση του προβλήματος.Λύσεις του προβλήματος αποτελούν και οι μπλε και οι πράσινοι φύλακες.
Επιλέγουμε το χρώμα με το λιγότερο πλήθος κορυφών(εδώ τυχαίνει είναι το ίδιο πλήθος για κάθε χρώμα).
Γενικά μετά τον χρωματισμό ενός ν-γωνου με τις παραπάνω προϋποθέσεις με τρία χρώματα το χρώμα που εμφανίζεται τις λιγότερες φορές βρίσκεται το πολύ σε [ν/3] κορυφές.
Καταφεύγουμε στην θεωρία γράφων.Χρωματίζουμε τις κορυφές των τριγώνων με διαφορετικά χρώματα με τέτοιο τρόπο έτσι ώστε κάθε δυο γειτονικές κορυφές δεν έχουν το ίδιο χρώμα.Ποιος είναι ο ελάχιστος αριθμός διαφορετικών χρωμάτων που απαιτείται στο παραπάνω σχήμα και καλύπτει την παραπάνω προϋπόθεση;Απάντηση,μόνο 3.
Δείτε το σχήμα.Αν θεωρήσουμε τους φύλακες στις κορυφές με κόκκινο χρώμα τότε αυτοί εποπτευουν όλη την αίθουσα,συνεπώς οι κόκκινοι φύλακες αποτελούν μια λύση του προβλήματος.Λύσεις του προβλήματος αποτελούν και οι μπλε και οι πράσινοι φύλακες.
Επιλέγουμε το χρώμα με το λιγότερο πλήθος κορυφών(εδώ τυχαίνει είναι το ίδιο πλήθος για κάθε χρώμα).
Γενικά μετά τον χρωματισμό ενός ν-γωνου με τις παραπάνω προϋποθέσεις με τρία χρώματα το χρώμα που εμφανίζεται τις λιγότερες φορές βρίσκεται το πολύ σε [ν/3] κορυφές.
Βρήκαμε λοιπον ότι χρειάζονται το πολύ 3 φύλακες για μια βέλτιστη τοποθέτηση (π.χ μπλε κορυφες) που φαίνεται στο παρακάτω σχήμα
Ο Πινγκ Πονγκ το εξηγεί συνοπτικά για ένα δεξαεξαγωνικο μουσείο...
1.How to Guard an Art Gallery And Other Discrete Mathematical Adventures, T. S. Michael The Johns Hopkins University Press
2.Proofs from the book ,M Aigner,M Ziegler
3.http://mathworld.wolfram.com/ArtGalleryTheorem.html
4.http://www-users.math.umn.edu/~reiner/Talks/ArtGallery.pdf
Ένα σχετικό βίντεο:
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου