Policías y ladrones

Ponente(s): Sebastián Franco Martinez, Raúl González Pérez Sac-nicté Damayanti Salas Reyes Aarón Rodríguez González-Pacheco Dr. Miguel Tecpa Galván

Un juego de persecución y evasión en una gráfica G consiste en un juego bipersonal por turnos. Uno de los dos jugadores tiene a su disposición un conjunto de fichas posicionados en los vértices de G, los cuales representan policías, y el segundo jugador tiene una única ficha que representa un ladrón. El objetivo del juego es el mover a los policías y al ladrón a lo largo de la gráfica. El juego lo ganan los policías si es posible capturar al ladrón, y el ladrón tiene por objetivo el escapar de los policías. Debido a que el jugador que controla a los policías siempre tiene una estrategia ganadora si cuenta con suficientes fichas, se define el número de policía de G, denotado por p(G), como el mínimo número de policías que se requieren para que los policías tengan una estrategia ganadora bajo ciertas condiciones. En este trabajo se presentan algunas cotas para el número de policía en algunas operaciones de gráficas mediante la presentación de estrategias ganadoras para el jugador que tiene a su disposición las fichas de policía.