Policías y ladrones sobre gráficas de fichas de árboles.

Ponente(s): Humberto Lozano Chávez, César Hernández Cruz

En este trabajo planteamos un modelo para estudiar el juego de policías y ladrones, a los cuales llamamos C y R. Si C tiene tantos policías como vértices tiene la gráfica G sobre la que se juega, entonces en esta instancia C tendría una estrategia ganadora. La pregunta natural que surge es determinar el mínimo número de policías tal que C tiene una estrategia ganadora; a este parámetro se le llama número policiaco. Se puede tomar una variante de este juego en la que el tablero corresponde a la gráfica de k fichas de una gráfica G. En este sentido, se puede determinar el número policiaco de las gráficas de fichas de una familia de gráficas sin necesidad de analizar la misma gráfica de fichas. Esto se logra a través de una modificación al juego sobre la gráfica G, donde cada policía y el ladrón conforman equipos de k fichas cada uno, de manera que el objetivo de C es que las k fichas de al menos un policía estén capturando las k fichas del ladrón, mientras que el objetivo de R es evitar que esto suceda. En esta plática veremos las estrategias desarrolladas para calcular el valor que toma el parámetro número policiaco para ciertas gráficas de fichas de familias de árboles, siendo esto último contenido original de mi tesis.