Art Gallery Problem

septiembre 14, 2007

a) Se tiene un grafo conexo con n vertices, hallar la menor cantidad de vertices (en funcion de n) que podemos escoger de forma que todo vertice del grafo sea vecino de uno de ellos (un vertice es vecino de si mismo).

b) Tenemos un museo que tiene forma de poligono y deseamos ubicar algunos guardias para vigilar las paredes. Cada guardia debe permanecer siempre en el mismo lugar pero puede darse vuelta. Si el museo tiene n paredes probar que \left\lfloor {n\over 3} \right\rfloor guardias alcanzan para vigilar todas las paredes.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: