Policías y ladrones en gráficas de fichas

El juego de policías y ladrones es, valga redundancia, un juego de evasión-persecución en el que dos contrincantes, $C$ y $R$, alternan turnos para mover sobre los vértices de una gráfica a un grupo de policías, $c_1,\dots, c_k$, y a un ladrón $R$. El objetivo del jugador $C$ es que al menos uno de sus policías capture al ladrón, i.e., ocupe la misma posición del ladrón en un turno. Por otra parte, el objetivo de $R$ es evitar ser capturado por cualquier policía. Se dice que $C$ tiene una estrategia ganadora si puede capturar a $R$ sin importar los movimientos que este haga. En tanto, $R$ tiene una estrategia ganadora si puede evitar ser capturado por una cantidad indefinida de turnos.

Si $C$ tiene tantos policías como vértices tiene la gráfica $G$ sobre la que se juega, entonces $C$ tiene una estrategia ganadora. Surge pues el problema de determinar el mínimo número de policías tal que $C$ tiene una estrategia ganadora para ciertas familias de gráficas. A este parámetro se le llama número policiaco y está bien definido para cualquier gráfica.

Se puede considerar una variante equivalente al juego original sobre la gráfica de $k$ fichas de una gráfica $G$, cuyos vértices son las distintas configuraciones ($k$-conjuntos de vértices) de $G$ y dos configuraciones son adyacentes si y solo si la diferencia simétrica de ambas configuraciones es un conjunto de dos vértices adyacentes en $G$.

En este sentido, se puede determinar el número policiaco de las gráficas de fichas de $G$ solo analizando la estructura de $G$. En esta plática veremos las estrategias desarrolladas como demostración del valor que toma el parámetro número policiaco para ciertas gráficas de fichas de familias de árboles.