El teorema de la galería de arte (teorema de Chvátal-Fisk)
El teorema de la galería de arte (Chvátal-Fisk) nos da la mejor cota superior (es decir, la mas pequeña) del número de cámaras que son suficientes para vigilar una galería de arte, e incluso en qué vértices colocarlas, pero no nos dice cuál es el número mínimo de cámaras que se necesitan para cada galería en concreto. Por ejemplo, en la galería poligonal que estamos utilizando en esta entrada del Cuaderno de Cultura Científica, y en la que hemos dejado cuatro cámaras (correspondientes a los vértices verdes) se podría suprimir incluso una de esas cámaras, y quedarnos solamente con tres. Se ha demostrado que el problema de calcular el número mínimo de cámaras para vigilar una galería de arte (lo suficientemente sofisticada) es un problema computacional de tipo NP fuerte, es decir, no existe un algoritmo eficiente que lo resuelva.
Vamos a hacer unos ejercicios para ver si hemos comprendido este teorema.