Recuento de policías ganador

El gráfico ganador del policía es un gráfico no dirigido en el que el perseguidor (el policía) puede ganar el juego de persecución y evasión en el que persigue al ladrón y los jugadores se turnan para moverse a lo largo de los bordes del gráfico o quedarse quietos hasta que el policía toma el vértice. donde está el ladrón [ 1] . Los gráficos policiales ganadores finitos también se denominan gráficos analizables o gráficos construidos , porque se pueden analizar eliminando un vértice dominado una y otra vez (un vértice cuyo vecindario cerrado es un subconjunto del vecindario de otro vértice) o construidos agregando repetidamente dicho vértice. Los gráficos de policías ganadores se pueden reconocer en tiempo polinomial mediante un algoritmo codicioso que genera un orden de clasificación. Esta clase incluye grafos cordales y grafos que contienen un vértice universal .

Definición

Persecución evasiva

Las gráficas ganadoras del policía (y la clase complementaria de gráficas, las gráficas ganadoras del ladrón) fueron introducidas por Nowakowski y Winkler [2] en el contexto del siguiente juego de persecución-evasión, que atribuyen a G. Gabor y A. Kiyo Dos jugadores, un policía y un ladrón, se ubican en diferentes vértices iniciales de un gráfico dado. Se turnan para jugar. Durante su turno, el jugador puede moverse a un vértice adyacente o permanecer en su lugar. El juego termina y el policía gana si el policía puede terminar su turno en el mismo vértice que el ladrón. El ladrón gana si puede esquivar al policía indefinidamente. Un gráfico de policía ganador es un gráfico con la propiedad de que no importa dónde comiencen el juego los dos jugadores, el policía siempre puede ganar [3] .

Desmontaje

Una vecindad cerrada N [ v ] de un vértice v de un grafo dado es el conjunto de vértices que consta del vértice v mismo y todos los demás vértices adyacentes a v . Se dice que un vértice v está dominado por otro vértice w si . Es decir, v y w son adyacentes, y cualquier vecino de v es vecino de w [4] . Nowakowski y Winkler [2] llaman a un vértice que está dominado por otro vértice un vértice irreducible [3] .

El orden de desensamblaje o el orden de eliminación de los vértices dominados de un grafo dado corresponde a un orden de vértices tal que si se eliminan los vértices uno por uno en ese orden, todos los vértices (excepto el último) son dominados. El gráfico se analiza si y solo si tiene un orden de análisis [3] [4] .

Propiedades de cierre

La familia de gráficos de policías ganadores se cierra bajo el fuerte producto de gráficos . El policía puede ganar en el producto estricto de las gráficas ganadoras del policía apostando en uno de los multiplicadores del producto y luego haciendo lo mismo en los otros multiplicadores, quedándose en el mismo vértice que el atracador en los multiplicadores ya ganados [3] . Por ejemplo, el gráfico de movimiento del rey , el producto fuerte de dos caminos , es el gráfico de un policía ganador [5] .

No es cierto que un subgrafo generado arbitrariamente de gráficos de policías ganadores sea ganador. Sin embargo, algunos subgrafos especiales generados siguen ganando. Nowakowski y Winkler [2] definen la contracción de un grafo G en uno de sus subgrafos H generados como un mapeo de vértices de G a vértices de H que mapea cada vértice de H en sí mismo, y mapea cada dos vértices adyacentes de G a cualquiera el mismo vértice o a un par de vértices adyacentes en H . Entonces, como dicen, la familia de gráficos de policías ganadores se cierra por contracción. Para ganar en H , se puede simular un juego en G. Si la estrategia ganadora en G para el policía es quedarse quieto o moverse a lo largo de un arco cuyos dos vértices corresponden al mismo vértice en H , el policía se queda quieto en H. En todos los demás casos, el policía se mueve a lo largo del borde en H , que es la imagen del borde ganador en G bajo contracción [3] .

Equivalencia de pagos de policías y analizabilidad

Cualquier gráfico analizado es ganador para el policía. La estrategia ganadora para el policía es encontrar un vértice dominado v y seguir (por inducción) la estrategia óptima en el gráfico formado por la eliminación de v , asumiendo que el ladrón está en un vértice que domina el vértice v . Esto da como resultado que el policía agarre al ladrón o que esté en una posición en la que el ladrón está en el vértice v y el policía en el vértice dominante, desde donde el policía puede ganar haciendo un movimiento adicional [3] . Esta estrategia se puede utilizar para demostrar por inducción que en un gráfico con n vértices se puede obligar a un policía a ganar en un máximo de n − 4 jugadas [6] [7] .

Por el contrario, cualquier gráfico de policía ganador tiene un vértice dominado. Si el ladrón juega de manera óptima con el objetivo de prolongar el juego y la última posición en el juego antes de que el policía atrape al ladrón en el nodo c y al ladrón en el nodo r , entonces c debe dominar r , de lo contrario, el ladrón podría extender el juego por al menos un movimiento. Una función que asigna r a c y deja el resto de los vértices en su lugar es una contracción, por lo que el gráfico formado al eliminar un vértice dominado aún debe ser ganador para el policía. Por inducción, obtenemos que cualquier gráfico policial ganador puede analizarse [3] . Los mismos argumentos muestran que en un grafo sin vértices dominados, el ladrón nunca pierde: siempre hay un movimiento a un vértice que no es adyacente al policía. En un gráfico arbitrario que no gana para el policía, el ladrón puede ganar eliminando todos los vértices dominados y jugando en el subgráfico restante, que no debe estar vacío, de lo contrario, el gráfico será analizable.

Algoritmos de reconocimiento y una familia de todas las órdenes de desmontaje

Si se domina un vértice en un gráfico de cop ganador, entonces (cuando se eliminan otros vértices dominados) permanece dominado hasta que se elimine, o permanece como el vértice final del orden de análisis. Por lo tanto, el conjunto de órdenes de análisis correctas tiene la estructura de un antimatroid , y el orden de análisis se puede encontrar mediante un algoritmo codicioso simple que elimina los vértices dominados paso a paso. El proceso tiene éxito si y solo si el gráfico gana para el policía, por lo que al proporcionar un algoritmo para encontrar el orden de análisis, este método proporciona un algoritmo para verificar si un gráfico dado gana para el policía.

Una forma de encontrar el siguiente vértice para eliminar es seguir los siguientes pasos:

En un grafo con n vértices, m aristas y degeneración d , este proceso se puede completar en O ( dm ) tiempo [8] .


Un algoritmo alternativo pero más complicado de Spinrad [9] utiliza un número, al que llama déficit , para cada par de vértices adyacentes ( x , y ) y este número contiene el número de vecinos de x que no son vecinos de y . El algoritmo crea y mantiene un conjunto deficitario (vecinos de x que no son vecinos de y ) solo cuando el déficit es pequeño. Para acelerar los cálculos, el algoritmo utiliza árboles de decisión que clasifican los vértices según su adyacencia a pequeños bloques con vértices. El algoritmo realiza los siguientes pasos:

El tiempo de ejecución de este procedimiento es [10] .

Familias de grafos relacionadas

Cualquier gráfico cordal finito es analizable, y cualquier orden de exclusión de gráfico cordal (orden de vértice en el que los vecinos finitos de cada vértice forman una camarilla ) es un orden de análisis válido. Sin embargo, hay infinitos grafos cordales que no son ganadores para el policía [11] .

Cualquier gráfico que tenga un vértice universal se analiza porque todos los demás vértices están dominados por el vértice universal y cualquier orden de vértice que coloque el vértice universal en último lugar es el orden de análisis correcto. Por el contrario, casi todos los gráficos analizados tienen un vértice universal en el sentido de que entre todos los gráficos analizados con n vértices, la proporción de gráficos con un vértice universal tiende a uno cuando n tiende a infinito [12] .

Los gráficos ganadores hereditarios del policía son gráficos en los que cada subgráfico isométrico gana para el policía. Esto no es cierto para todos los gráficos de policías ganadores. Por ejemplo, una rueda con cinco vértices es ganadora para el policía, pero contiene un cuadriciclo isométrico que no es ganador, por lo que el gráfico es ganador hereditariamente. Los gráficos de cop ganadores hereditarios son los mismos que los gráficos de puente, en los que cualquier ciclo de longitud cuatro o más tiene un camino de corte, un par de vértices que están más cerca en el gráfico que en el ciclo [13] . El gráfico ganador de un policía es hereditariamente ganador para un policía si y solo si no tiene ni un ciclo de 4 ni un ciclo de 5 como ciclo generado. Para un gráfico de policía hereditariamente ganador, la inversión de cualquier recorrido primero en anchura es un orden de clasificación adecuado, lo que implica que cualquier vértice puede elegirse como el último vértice del orden de clasificación [14] .

Se puede usar un juego similar con más policías para determinar el número de policías del gráfico, el menor número de policías necesarios para ganar el juego. Los gráficos de policías ganadores son exactamente los gráficos para los que el número de policías es igual a uno [15] .

Notas

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski y Winkler, 1983 , p. 235–239.
  4. ↑ 1 2 Chepoi, 1998 , pág. 414–436.
  5. ↑ Sobre el hecho de que un producto de camino estricto es un gráfico ganador, véase el artículo de Nowakowski y Winkler ( Nowakowski, Winkler 1983 ). Para el hecho de que la cuenta del rey es un producto estricto, ver Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , p. 5588–5595.
  7. ↑ Gavenciak, 2010 , pág. 1557-1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , pág. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , pág. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , pág. 27–41.
  12. ↑ Bonato, Kemkes, Pralat, 2012 , p. 1652-1657
  13. ↑ Anstee, Farber, 1988 , pág. 22–28.
  14. ↑ Chepoi, 1997 , pág. 97–100.
  15. ↑ Aigner, Fromme, 1984 , pág. 1–11.

Literatura

Enlaces