Hispanopedia Wiki
Articulo de referencia

Gráfico de victorias policiales

En teoría de grafos , un grafo cop-win 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 j...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

En teoría de grafos , un grafo cop-win 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 una arista de un grafo o quedarse donde están, hasta que el policía aterriza en el vértice del ladrón. [ 1 ] Los grafos cop-win finitos también se llaman grafos desmantelables o grafos constructibles , 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 cop-win se pueden reconocer en tiempo polinomial por un algoritmo voraz que construye un orden de desmantelamiento. Incluyen los grafos cordales y los grafos que contienen un vértice universal .

Definiciones

Persecución-evasión

Los grafos de victoria del policía se definen mediante un juego de persecución-evasión en el que dos jugadores, un policía y un ladrón, se sitúan en diferentes vértices iniciales de un grafo no dirigido dado . El policía elige primero un vértice inicial, y luego el ladrón elige otro. A continuación, juegan por turnos, comenzando de nuevo el policía. En cada turno, el jugador puede moverse a un vértice adyacente o permanecer en su posición. El juego termina, y el policía gana, si logra finalizar su turno en el mismo vértice que el ladrón. El ladrón gana evadiendo al policía indefinidamente. Un grafo de victoria del policía es un grafo con la propiedad de que, cuando los jugadores eligen posiciones iniciales y se mueven de esta manera, el policía siempre puede forzar la victoria. Si un grafo no dirigido no es un grafo de victoria del policía, se denomina grafo de victoria del ladrón. [ 2 ]

Desmantelamiento

En este grafo, el vértice v está dominado por el vértice w : la vecindad cerrada de v , N [ v ] (región sombreada interior) es un subconjunto de la vecindad cerrada de w , N [ w ] (región sombreada exterior).

El vecindario cerrado N [ v ] de un vértice v en un grafo dado es el conjunto de vértices que consta del propio vértice 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 vértice irreducible a un vértice que está dominado por otro vértice . [ 2 ]

Un orden de desmantelamiento o orden de eliminación por dominación de un grafo dado es un ordenamiento de los vértices tal que, si los vértices se eliminan uno a uno en este orden, cada vértice (excepto el último) está dominado en el momento de su eliminación. Un grafo es desmantelable si y solo si tiene un orden de desmantelamiento. [ 2 ] [ 3 ]

Equivalencia entre victoria policial y desmantelamiento

Todo grafo finito desmantelable es una victoria para el policía. Esto se puede demostrar por inducción matemática , tomando como caso base un grafo de un vértice (ganado trivialmente por el policía). 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 fingiendo que el ladrón está en el vértice que domina a v siempre que el ladrón esté realmente en v . Seguir esta estrategia resultará en una victoria real del juego, o en 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 necesita como máximo n movimientos para ganar, independientemente de la posición inicial. Eligiendo 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, todo grafo de victoria del policía tiene un vértice dominado. Pues, en un grafo sin vértices dominados, si el ladrón no ha perdido ya, 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 del policía, entonces eliminar v debe producir otro grafo de victoria del policía, pues de lo contrario el ladrón podría jugar dentro de ese subgrafo, fingiendo que el policía está en el vértice que domina a v cuando 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 del policía finito es desmantelable. [ 2 ] [ 9 ]

Propiedades de cierre

En un tablero de ajedrez, uno de los dos reyes, jugando como policía, puede vencer al otro rey, jugando como ladrón, por lo que el gráfico del rey es un gráfico de victoria del policía.

Se dice que una familia de objetos matemáticos es 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 cop-win es cerrada bajo productos fuertes de grafos . Cada vértice en el producto fuerte corresponde a un par de vértices en cada uno de los dos grafos factoriales. El policía puede ganar en un producto fuerte de dos grafos cop-win, primero, jugando para ganar en uno de estos dos grafos factoriales, llegando a un par cuyo primer componente es el mismo que el del ladrón. Luego, mientras permanece en pares cuyo primer componente es el mismo que el del ladrón, el policía puede jugar para 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 cop-win. En este grafo, los vértices corresponden a las casillas 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 una casilla 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 todo subgrafo inducido de un grafo cop-win sea cop-win. Sin embargo, ciertos subgrafos inducidos especiales sí conservan la propiedad cop-win. 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 o a un par de vértices adyacentes en H. Entonces, la familia de grafos cop-win es cerrada bajo la retracción. Esto se debe a que un policía puede ganar en H simulando un juego en G. Siempre que la estrategia ganadora en G requiera que el policía permanezca en su lugar o siga una arista cuyos extremos se asignan al mismo vértice de H , el policía permanece en H. Y en todos los demás casos, el policía sigue la arista en H que es la imagen, bajo la retracción, de una arista ganadora en G. [ 2 ]

Algoritmos de reconocimiento

Se conocen varias estrategias diferentes para comprobar si un grafo es de victoria para el policía y, en caso afirmativo, encontrar una secuencia de desmantelamiento que le permita ganar en el grafo. Estas incluyen algoritmos voraces y un algoritmo más complejo basado en el conteo de vecinos compartidos de los vértices.

Algoritmo voraz

Un algoritmo voraz simple que encuentra y elimina repetidamente cualquier vértice dominado puede determinar el orden de desmantelamiento . El proceso tiene éxito, al reducir el grafo a un solo vértice, si y solo si el grafo es de tipo "cop-win". Por lo tanto, además de proporcionar un algoritmo para encontrar órdenes de desmantelamiento, este método proporciona un algoritmo para comprobar si un grafo dado es de tipo "cop-win". Una forma en que este algoritmo encuentra los vértices dominados que elimina es realizando los siguientes pasos:

  • Encuentra todos los triángulos en el gráfico y cuenta la cantidad de triángulos en los que participa cada arista.
  • Encuentra repetidamente un vértice v que sea un extremo de una arista que participe en un número de triángulos igual al grado de v menos uno, elimina v y decrementa los triángulos por arista de cada arista restante que formó un triángulo con v .

En un grafo con n vértices, m aristas y degeneración d , este proceso puede llevarse a cabo en tiempo O ( dm ) . [ 12 ]

Contando vecinos

Un algoritmo alternativo y más complejo, propuesto por Spinrad (2004), consiste en mantener un número denominado déficit para cada par de vértices adyacentes ( x , y ) , que cuenta el número de vecinos de x que no son vecinos de y . Si este número se reduce a cero, tras la eliminación de otros vértices, entonces x está dominado por y y también puede eliminarse. Este algoritmo construye y mantiene el conjunto de déficit real (vecinos de x que no son vecinos de y ) únicamente para los pares ( x , y ) cuyo 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₂n vértices .  Si B es un conjunto de vértices que el algoritmo ha seleccionado como 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₂n bits  . Estos números permiten al algoritmo calcular, para cualesquiera dos vértices 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. Utilizando esta subrutina, el algoritmo realiza los siguientes pasos:

  • Crea bloques a partir de una partición arbitraria de los vértices y encuentra los números que representan los vecinos de cada vértice en cada bloque.
  • Utilice la subrutina de conteo de bloques para calcular el déficit para todos los pares de vértices adyacentes.
  • Repita los siguientes pasos hasta que se hayan eliminado todos los vértices:
    • Construye el conjunto de déficit para todos los pares adyacentes que tengan un déficit máximo de log n  y para los que aún no se haya construido dicho conjunto. El sistema inicial de bloques puede utilizarse para acelerar esta construcción.
    • Repita los siguientes pasos log n veces:
      • Encuentra un par ( x , y ) con un conjunto de déficit construido pero vacío. Si no existe tal par, el grafo no es de tipo cop-win; en ese caso, aborta el algoritmo.
      • Eliminar vértice x
      • Elimina x de todos los conjuntos de déficit construidos a los que pertenece.
    • Construye un bloque con el logaritmo de n vértices eliminados y números que representen las adyacencias de todos los demás vértices dentro de este bloque.
    • Utilice la subrutina de conteo de bloques, en este bloque en particular, para actualizar los déficits de todas las aristas.

Spinrad afirma que el tiempo total para este algoritmo es O ( n 3 /log n )  . [ 13 ]

En grafos infinitos

La computabilidad de problemas algorítmicos que involucran grafos de victoria policial también se ha estudiado para grafos infinitos . En el caso de grafos infinitos, es posible construir grafos computables infinitamente numerables , en los que un ladrón omnisciente siempre podría evadir a cualquier policía, pero para los que ningún algoritmo puede seguir esta estrategia. Estos grafos pueden incluso ser árboles infinitos, con un número finito de aristas por vértice. Según el lema de Kőnig , dicho árbol 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, cualquier algoritmo para elegir movimientos para el ladrón puede ser vencido por un policía que simplemente camina en el árbol por el camino único hacia el ladrón. Análogamente, es posible construir grafos computables infinitamente numerables de victoria policial, en los que un policía omnisciente tiene una estrategia ganadora que siempre termina en un número finito de movimientos, pero para los que ningún algoritmo puede seguir esta estrategia. En tales gráficos, cualquier algoritmo para elegir movimientos para el policía puede ser eludido indefinidamente por el ladrón. [ 14 ]

En este grafo, u es un vértice universal : es adyacente a todos los demás vértices.

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 ordenamiento de desmantelamiento válido. Sin embargo, existen grafos cordales infinitos, e incluso grafos cordales infinitos de diámetro dos, que no son cop-win. [ 15 ] [ 16 ] Para otros tipos de grafos, pueden existir grafos cop-win infinitos de ese tipo incluso cuando no hay grafos finitos; por ejemplo, esto es cierto para los grafos transitivos de vértices 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 ordenación de vértices que coloque al vértice universal al final es una ordenación válida para el desmantelamiento. 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 grafos de visibilidad de polígonos simples siempre favorecen al policía. Estos grafos se definen 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 salga del polígono. (En particular, los vértices adyacentes en el polígono también lo son en el grafo). Incluso cuando el policía y el ladrón pueden 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 del camino más corto hacia el ladrón. Este movimiento excluye una parte del polígono a la que el ladrón nunca podrá regresar. 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 vértices, por lo que es una estrategia ganadora válida para el grafo de visibilidad. [ 19 ]

El grafo de rueda de cinco vértices es de tipo "cop-win" pero no es hereditariamente "cop-win".

Los gráficos hereditariamente cop-win son los gráficos en los que cada subgrafo isométrico (un subgrafo)H⊆GRAMO{\displaystyle H\subseteg G}de tal manera que para cualesquiera dos vértices enH{\displaystyle H}la distancia entre ellos medida en GRAMO{\displaystyle G}es lo mismo que la distancia entre ellos medida enH{\displaystyle H}) es cop-win. Esto no es cierto para todos los grafos cop-win; por ejemplo, el grafo 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 rueda no es hereditariamente cop-win. Los grafos hereditariamente cop-win son los mismos que los grafos puenteados, 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 hereditariamente cop-win si y solo si no tiene ni el 4-ciclo ni el 5-ciclo como ciclos inducidos . Para un grafo hereditariamente cop-win, la inversión de cualquier recorrido en anchura es un orden de desmantelamiento válido, de lo cual se deduce que cualquier vértice puede ser elegido como el último vértice de un orden de desmantelamiento. [ 21 ]

Un juego similar con un mayor número de policías puede usarse para definir el número de policías de un grafo, el número mínimo de policías necesarios para ganar el juego. Los grafos de victoria de policías son exactamente los grafos con 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, usando el grafo dado como campo de juego. [ 23 ] El juego usado para definir el número de policías debe distinguirse de otro juego de policías y ladrones usado en una definición de ancho de árbol , que permite a los policías moverse a vértices arbitrarios en lugar de requerir que se desplacen a lo largo de las aristas del grafo. [ 24 ]

Historia

El juego con un solo policía, y los gráficos de victoria del policía 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ía definido a partir de él, fueron estudiados por primera vez por Aigner y Fromme (1984) . [ 22 ] [ 26 ]

Referencias

  1. ↑ Bonato, Anthony; Nowakowski, Richard J. (2011), El juego de policías y ladrones en grafos , Student Mathematical Library, vol.  61, Providence, RI: American Mathematical Society, doi : 10.1090/stml/061 , ISBN 978-0-8218-5347-4, MR 2830217 
  2. 1 2 3 4 5 6 7 8 9 Nowakowski, Richard; Winkler, Peter (1983), "Peligro de vértice a vértice en un grafo", Matemáticas Discretas , 43 ( 2–3 ): 235–239 , doi : 10.1016/0012-365X(83)90160-7 , MR 0685631 
  3. 1 2 Chepoi, Victor (1998), "Sobre ordenamientos que preservan la distancia y eliminan la dominación", SIAM Journal on Discrete Mathematics , 11 (3): 414– 436, doi : 10.1137/S0895480195291230 , MR 1628110 
  4. ↑ Bonato & Nowakowski (2011) , Teorema 2.3, página 32.
  5. ↑ Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J. (2009), "El tiempo de captura de un grafo", Matemáticas Discretas , 309 (18): 5588– 5595, doi : 10.1016/j.disc.2008.04.004 , MR 2567962 
  6. ↑ Gavenčiak, Tomáš (2010), "Gráficos de victoria de la policía con tiempo de captura máximo", Matemáticas Discretas , 310 ( 10–11 ): 1557–1563 , doi : 10.1016/j.disc.2010.01.015 , MR 2601265 
  7. ↑ Bonato y Nowakowski (2011) , pág. 36.
  8. ↑ Bonato & Nowakowski (2011) , Lema 2.1, página 31.
  9. ↑ Bonato & Nowakowski (2011) , Teorema 2.2, página 32.
  10. ↑ Bonato & Nowakowski (2011) , Teorema 2.8, página 43.
  11. ↑ Para el hecho de que un producto fuerte de caminos es cop-win, véase Nowakowski y Winkler (1983) . Para el hecho de que el grafo del rey es un producto fuerte de caminos, véase Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" , 2005 International Conference on Analysis of Algorithms , Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341 , MR 2193130 .  
  12. ↑ Lin, Min Chih; Soulignac, Francisco J.; Szwarcfiter, Jayme L. (2012), "Arboricidad, índice h y algoritmos dinámicos", Theoretical Computer Science , 426–427 : 75–90 , arXiv : 1005.2211 , doi : 10.1016/j.tcs.2011.12.006 , MR 2891574 , S2CID 15827218  
  13. 1 2 Spinrad, Jeremy P. (2004), "Reconocimiento de grafos cuasi-triangulados", Matemáticas Aplicadas Discretas , 138 ( 1– 2): 203– 213, doi : 10.1016/S0166-218X(03)00295-6 , MR 2057611 
  14. ↑ Stahl, Rachel D. (septiembre de 2021), "Computabilidad y el juego de policías y ladrones en grafos", Archive for Mathematical Logic , 61 ( 3–4 ): 373–397 , doi : 10.1007/s00153-021-00794-3 , S2CID 244214571 
  15. ↑ Hahn, Geňa; Laviolette, François; Sauer, Norbert; Woodrow, Robert E. (2002), "On cop-win graphs", Discrete Mathematics , 258 ( 1– 3): 27– 41, doi : 10.1016/S0012-365X(02)00260-1 , MR 2002070 
  16. ↑ Bonato y Nowakowski (2011) , Sección 7.4, Grafos cordales infinitos, págs. 178–182.
  17. ↑ Bonato y Nowakowski (2011) , Sección 7.5, Grafos cop-win transitivos de vértice, págs. 182–187.
  18. ↑ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), "Casi todos los grafos cop-win contienen un vértice universal", Matemáticas Discretas , 312 (10): 1652– 1657, doi : 10.1016/j.disc.2012.02.018 , MR 2901161 
  19. ↑ Lubiw, Anna ; Snoeyink, Jack; Vosoughpour, Hamideh (2017), "Visibility graphs, dismantlability, and the cops and robbers game", Computational Geometry , 66 : 14–27 , arXiv : 1601.01298 , doi : 10.1016/j.comgeo.2017.07.001 , MR 3693353 
  20. ↑ Anstee, RP; Farber, M. (1988), "Sobre grafos puenteados y grafos cop-win", Journal of Combinatorial Theory , Serie B, 44 (1): 22– 28, doi : 10.1016/0095-8956(88)90093-7 , MR 0923263 
  21. ↑ Chepoi, Victor (1997), "Los grafos puenteados son grafos cop-win: una prueba algorítmica", Journal of Combinatorial Theory , Serie B, 69 (1): 97–100 , doi : 10.1006/jctb.1996.1726 , MR 1426753 
  22. 1 2 Aigner, M.; Fromme, M. (1984), "Un juego de policías y ladrones", Matemáticas Aplicadas Discretas , 8 (1): 1– 11, doi : 10.1016/0166-218X(84)90073-8 , MR 0739593 
  23. ^ Bonato y Nowakowski (2011) , págs .
  24. ↑ Seymour, Paul D. ; Thomas, Robin (1993), "Búsqueda en grafos y un teorema min-max para el ancho de árbol", Journal of Combinatorial Theory, Serie B , 58 (1): 22– 33, doi : 10.1006/jctb.1993.1027
  25. ↑ Quilliot, Alain (1978), Jeux et pointes fixes sur les graphes [ Juegos y puntos fijos en gráficas ] , ciclo Thèse de 3ème (en francés), Universidad Pierre y Marie Curie , págs . , citado por Bonato y Nowakowski (2011)
  26. ^ Bonato y Nowakowski ( 2011) , pág.4. 
  • Grafos desmontables , Sistema de información sobre clases de grafos y sus inclusiones