Το πρόβλημα των φυλάκων ενός Μουσείου

[Mihalis_Lambrou]

.
Με αφορμή την συζήτηση εδώ.

Το πρόβλημα των Mουσείων ζητά ποιος είναι ο μικρότερος αριθμός φυλάκων που πρέπει να τοποθετηθούν στο Mουσείο έτσι ώστε κάθε εσωτερικό του σημείο να είναι ορατό από τουλάχιστον έναν φύλακα.

Για παράδειγμα το Μουσείο στο αριστερά μέρος της παρακάτω εικόνας μπορεί να φυλαχθεί με δύο φύλακες (δίνω 2 διαφορετικές λύσεις). Η φύλαξη του με έναν φύλακα ή αδύνατη: Πράγματι (βλέπε το σχήμα δεξιά), για να φυλαχθεί το σημείο πρέπει να μπει ένας φύλακας στην κίτρινη περιοχή. Για να φυλαχθεί το σημείο πρέπει να μπει ένας φύλακας στην πράσινη περιοχή. Επειδή οι δύο αυτές περιοχές δεν έχουν κοινή τομή σημαίνει ότι δεν γίνεται να έχουμε φύλαξη του Μουσείου με λιγότερους από 2 φύλακες.
.

Μουσείο 1.png (7.05 KiB) Προβλήθηκε 311 φορές

.
Άσκηση 1. Βρείτε (με απόδειξη) τον μικρότερο αριθμό φυλάκων που απαιτούνται για την φύλαξη του καθενός από τα δύο παρακάτω Μουσεία.
.

Μουσείο 2.png (26.06 KiB) Προβλήθηκε 311 φορές

.
Άσκηση 2. Ομοίως για το παρακάτω Μουσείο.
.

Μουσείο 3.png (10.19 KiB) Προβλήθηκε 311 φορές

[αρψ2400]

Για τη δεύτερη Άσκηση: 3 φύλακες είναι αναγκαίοι αφού ένας πρέπει να τοποθετηθεί σε καθεμία από τις τρεις ξένες μεταξύ τους χρωματιστές περιοχές. (εικ1η) Είναι και αρκετοί όπως φαίνεται στην δεύτερη εικόνα αφού καλύπτουν όλο το κτίριο.