En teoría de grafos , un grafo de policía-ganador es un grafo no dirigido en el que el perseguidor (policía) siempre puede ganar un juego de persecución-evasión contra un ladrón, con los jugadores tomando turnos alternos en los que pueden elegir moverse a lo largo de un borde de un grafo o quedarse quietos, hasta que el policía aterrice en el vértice del ladrón. [1] Los grafos de policía-ganador finitos también se denominan grafos desmantelables o grafos construibles , porque se pueden desmantelar eliminando repetidamente un vértice dominado (uno cuyo vecindario cerrado es un subconjunto del vecindario de otro vértice) o construir agregando repetidamente dicho vértice. Los grafos de policía-ganador se pueden reconocer en tiempo polinomial mediante un algoritmo voraz que construye un orden de desmantelamiento. Incluyen los grafos cordales y los grafos que contienen un vértice universal .
Los grafos de policía-ganador pueden definirse como un juego de persecución-evasión en el que dos jugadores, un policía y un ladrón, se posicionan en diferentes vértices iniciales de un grafo no dirigido dado . El policía elige primero un vértice inicial y luego elige el ladrón. A continuación, juegan por turnos, nuevamente con el policía primero. En el turno de cada jugador, el jugador puede moverse a un vértice adyacente o quedarse quieto. El juego termina y el policía gana, si puede terminar un turno en el mismo vértice que el ladrón. El ladrón gana evadiendo indefinidamente al policía. Un grafo de policía-ganador es un grafo con la propiedad de que, cuando los jugadores eligen posiciones iniciales y luego se mueven de esta manera, el policía siempre puede forzar una victoria. Si un grafo no dirigido no es un grafo de policía-ganador, se llama grafo de ladrón-ganador. [2]
El entorno cerrado N [ v ] de un vértice v en un grafo dado es el conjunto de vértices que consiste en el propio v y todos los demás vértices adyacentes a v . Se dice que el vértice v está dominado por otro vértice w cuando N [ v ] ⊂ N [ w ] . Es decir, v y w son adyacentes, y cualquier otro vecino de v también es vecino de w . [3] Nowakowski y Winkler (1983) llaman a un vértice que está dominado por otro vértice un vértice irreducible . [2]
Un orden de desmantelamiento u orden de eliminación de dominación de un grafo dado es un orden de los vértices de manera que, si los vértices se eliminan uno por uno en este orden, cada vértice (excepto el último) está dominado en el momento en que se elimina. Un grafo es desmantelable si y solo si tiene un orden de desmantelamiento. [2] [3]
Todo grafo finito desmantelable es un grafo de policía-ganador. Esto se puede demostrar por inducción matemática , con un grafo de un vértice (trivialmente ganado por el policía) como caso base. Para un grafo más grande, sea v cualquier vértice dominado. Por la hipótesis de inducción, el policía tiene una estrategia ganadora en el grafo formado al eliminar v , y puede seguir la misma estrategia en el grafo original pretendiendo que el ladrón está en el vértice que domina v siempre que el ladrón esté realmente en v . Seguir esta estrategia dará como resultado una victoria real del juego, o una posición donde el ladrón está en v y el policía está en el vértice dominante, desde donde el policía puede ganar en un movimiento más. [2] [4] Un policía que sigue esta estrategia inductiva en un grafo con n vértices tarda como máximo n movimientos en ganar, independientemente de la posición inicial. Al elegir cuidadosamente la posición inicial del policía, se puede usar la misma idea para demostrar que, en un grafo de n vértices, el policía puede forzar una victoria en como máximo n − 4 movimientos. [5] [6] [7]
Por el contrario, cada grafo de victoria de policía tiene un vértice dominado. En un grafo sin vértices dominados, si el ladrón no ha perdido todavía, entonces hay un movimiento seguro a una posición no adyacente al policía, y el ladrón puede continuar el juego indefinidamente jugando uno de estos movimientos seguros en cada turno. [2] [8] Además, si v es un vértice dominado en un grafo de victoria de policía, entonces eliminar v debe producir otro grafo de victoria de policía, ya que de lo contrario el ladrón podría jugar dentro de ese subgrafo, pretendiendo que el policía está en el vértice que domina v siempre que el policía esté realmente en v , y nunca ser atrapado. Se sigue por inducción de estos dos principios que todo grafo de victoria de policía finito es desmantelable. [2] [9]
Se dice que una familia de objetos matemáticos está cerrada bajo un conjunto de operaciones si la combinación de miembros de la familia siempre produce otro miembro de esa familia. En ese sentido, la familia de grafos de policía-ganador está cerrada bajo productos fuertes de grafos . Cada vértice en el producto fuerte corresponde a un par de vértices en cada uno de dos grafos factoriales. El policía puede ganar en un producto fuerte de dos grafos de policía-ganador, primero, jugando a ganar en uno de estos dos grafos factoriales, alcanzando un par cuyo primer componente sea el mismo que el ladrón. Luego, mientras permanece en pares cuyo primer componente sea el mismo que el ladrón, el policía puede jugar a ganar en el segundo de los dos factores. [2] [10] Por ejemplo, el grafo del rey , un producto fuerte de dos grafos de caminos , es policía-ganador. En este grafo, los vértices corresponden a los cuadrados de un tablero de ajedrez, y tanto el policía como el ladrón se mueven como un rey en el juego de ajedrez , a un cuadrado que es adyacente horizontal, vertical o diagonalmente. La estrategia basada en el producto para el policía sería moverse primero a la misma fila que el ladrón, y luego moverse hacia la columna del ladrón mientras en cada paso permanece en la misma fila que el ladrón. [11]
No es cierto que cada subgrafo inducido de un grafo de cop-ganador sea cop-ganador. Sin embargo, ciertos subgrafos inducidos especiales sí siguen siendo cop-ganadores. Nowakowski y Winkler (1983) definen una retracción de un grafo G sobre uno de sus subgrafos inducidos H como una aplicación de los vértices de G a los vértices de H que asigna cada vértice de H a sí mismo, y que asigna cada par de vértices adyacentes de G al mismo vértice que cada uno de los otros o a un par de vértices adyacentes en H . Entonces la familia de grafos de cop-ganador está cerrada bajo retracción. Esto se debe a que un cop puede ganar en H simulando un juego en G . Siempre que la estrategia ganadora en G requiera que el cop se quede quieto, o que siga una arista cuyos puntos finales se asignan al mismo vértice de H , el cop se queda quieto en H . Y en todos los demás casos, el cop sigue la arista en H que es la imagen bajo la retracción de una arista ganadora en G . [2]
Se conocen varias estrategias diferentes para comprobar si un grafo es un grafo en el que el policía gana y, en caso afirmativo, encontrar una secuencia de desmantelamiento que permita que el policía gane en el grafo. Entre ellas se incluyen algoritmos voraces y un algoritmo más complicado basado en el recuento de vecinos compartidos de vértices.
Se puede encontrar un orden de desmantelamiento mediante un algoritmo voraz simple que encuentra y elimina repetidamente cualquier vértice dominado. El proceso tiene éxito, al reducir el grafo a un solo vértice, si y solo si el grafo es cop-win. Por lo tanto, además de proporcionar un algoritmo para encontrar órdenes de desmantelamiento, este método proporciona un algoritmo para probar si un grafo dado es cop-win. Una forma en que este algoritmo encuentra los vértices dominados que elimina es realizar los siguientes pasos:
En un gráfico con n vértices, m aristas y degeneración d , este proceso puede llevarse a cabo en el tiempo O ( dm ) . [12]
Un algoritmo alternativo y más complicado de Spinrad (2004) implica mantener un número llamado déficit para cada par adyacente de vértices ( x , y ) , que cuenta el número de vecinos de x que no son vecinos de y . Si este número se convierte en cero, después de que se hayan eliminado otros vértices, entonces x está dominado por y y también puede eliminarse. Construye y mantiene el conjunto de déficit real (vecinos de x que no son vecinos de y ) solo para pares ( x , y ) para los cuales el déficit es pequeño. [13]
Para acelerar sus cálculos, el algoritmo de Spinrad utiliza una subrutina para contar vecinos entre pequeños bloques de log 2 n vértices. Si B es un conjunto de vértices que el algoritmo ha seleccionado para ser un bloque, entonces para cualquier otro vértice, el conjunto de vecinos de ese vértice en B se puede representar como un número binario con log 2 n bits. Estos números permiten al algoritmo contar, para dos vértices cualesquiera x e y , cuánto contribuye B al déficit de x e y , en tiempo constante, mediante una combinación de operaciones bit a bit y búsquedas en tablas. Usando esta subrutina, el algoritmo realiza los siguientes pasos:
Spinrad indica el tiempo total para este algoritmo como O ( n 3 /log n ) . [13]
La computabilidad de problemas algorítmicos que involucran grafos de victoria de policía también se ha estudiado para grafos infinitos . En el caso de grafos infinitos, es posible construir grafos infinitos numerables computables , en los que un ladrón omnisciente siempre podría evadir a cualquier policía, pero para los cuales ningún algoritmo puede seguir esta estrategia. Estos grafos pueden incluso ser árboles infinitos, con un número finito de aristas por vértice. Por el lema de Kőnig , un árbol de este tipo debe tener un camino infinito, y un ladrón omnisciente puede ganar alejándose del policía por este camino, pero el camino no puede ser encontrado por un algoritmo. En cambio, cada algoritmo para elegir movimientos para el ladrón puede ser derrotado por un policía que simplemente camina en el árbol a lo largo del camino único hacia el ladrón. Análogamente, es posible construir grafos de victoria de policía infinitos numerables computables, en los que un policía omnisciente tiene una estrategia ganadora que siempre termina en un número finito de movimientos, pero para los cuales ningún algoritmo puede seguir esta estrategia. En tales gráficos, el ladrón puede evadir indefinidamente cualquier algoritmo para elegir movimientos del policía. [14]
Todo grafo cordal finito es un grafo desmantelable, y todo ordenamiento de eliminación de un grafo cordal (un ordenamiento de los vértices en el que los vecinos posteriores de cada vértice forman una camarilla ) es un orden de desmantelamiento válido. Sin embargo, existen infinitos grafos cordales, e incluso infinitos grafos cordales de diámetro dos, que no son cop-win. [15] [16] Para otros tipos de grafos, pueden existir infinitos grafos cop-win de ese tipo incluso cuando no hay ninguno finito; por ejemplo, esto es cierto para los grafos transitivos de vértice que no son grafos completos . [17]
Un vértice universal en un grafo es un vértice u que es adyacente a todos los demás vértices. Siempre que un grafo tiene un vértice universal , es desmantelable, porque todos los demás vértices están dominados por el vértice universal, y cualquier orden de vértices que coloque al vértice universal en último lugar es un orden de desmantelamiento válido. Por el contrario, casi todos los grafos desmantelables tienen un vértice universal, en el sentido de que, entre todos los grafos desmantelables de n vértices, la fracción de estos grafos que tienen un vértice universal tiende a uno en el límite cuando n tiende a infinito. [18]
Los gráficos de visibilidad de polígonos simples son siempre de tipo policía-ganador. Se trata de gráficos definidos a partir de los vértices de un polígono, con una arista siempre que dos vértices puedan conectarse mediante un segmento de línea que no pase por fuera del polígono. (En particular, los vértices que son adyacentes en el polígono también son adyacentes en el gráfico). Incluso cuando se permite al policía y al ladrón moverse en segmentos de línea recta dentro del polígono, en lugar de vértice a vértice, el policía puede ganar moviéndose siempre en el primer paso de un camino más corto hacia el ladrón. Tal movimiento corta parte del polígono a la que el ladrón nunca puede volver atrás para alcanzar. Cuando el policía comienza en un vértice y el ladrón está restringido a movimientos entre vértices, esta estrategia también limita al policía a los vértices, por lo que es una estrategia ganadora válida para el gráfico de visibilidad. [19]
Los grafos cop-win hereditarios son los grafos en los que cada subgrafo isométrico (un subgrafo tal que para cualesquiera dos vértices en la distancia entre ellos medida en es la misma que la distancia entre ellos medida en ) es cop-win. Esto no es cierto para todos los grafos cop-win; por ejemplo, el grafo de rueda de cinco vértices es cop-win pero contiene un 4-ciclo isométrico, que no es cop-win, por lo que este grafo de rueda no es cop-win hereditario. Los grafos cop-win hereditarios son los mismos que los grafos puente, grafos en los que cada ciclo de longitud cuatro o más tiene un atajo, un par de vértices más cercanos en el grafo que en el ciclo. [20] Un grafo cop-win es cop-win hereditario si y solo si no tiene ni el 4-ciclo ni el 5-ciclo como ciclos inducidos . En el caso de un gráfico de cop-win hereditario, la inversión de cualquier recorrido en amplitud es un orden de desmantelamiento válido, de lo que se deduce que cualquier vértice puede elegirse como el último vértice de un orden de desmantelamiento. [21]
Un juego similar con un mayor número de policías se puede utilizar para definir el número de policías de un gráfico, el menor número de policías necesarios para ganar el juego. Los gráficos de victoria de los policías son exactamente los gráficos de número de policías igual a uno. [22] Bonato y Nowakowski describen este juego intuitivamente como el número de fantasmas que se necesitarían para obligar a un jugador de Pac-Man a perder, utilizando el gráfico dado como campo de juego. [23] El juego utilizado para definir el número de policías debe distinguirse de un juego diferente de policías y ladrones utilizado en una definición de treewidth , que permite a los policías moverse a vértices arbitrarios en lugar de requerir que se desplacen a lo largo de los bordes del gráfico. [24]
El juego con un solo policía y los gráficos de victorias de policías definidos a partir de él fueron introducidos por Quilliot (1978). [25] [26] Otra referencia temprana es el trabajo de Nowakowski y Winkler (1983), quienes fueron introducidos al juego por G. Gabor. [2] [26] El juego con múltiples policías y el número de policías definido a partir de él fueron estudiados por primera vez por Aigner y Fromme (1984). [22] [26]
