Número de policía

Número de policías necesarios para atrapar a un ladrón en un gráfico

En teoría de grafos , una rama de las matemáticas, el número de policías o copnumber de un grafo no dirigido es el número mínimo de policías que es suficiente para asegurar una victoria (es decir, la captura del ladrón) en un determinado juego de persecución-evasión en el grafo.

Normas

En este juego, un jugador controla la posición de un número determinado de policías y el otro jugador controla la posición de un ladrón. Los policías intentan atrapar al ladrón moviéndose a la misma posición, mientras que el ladrón intenta no ser atrapado. Por lo tanto, los jugadores realizan las siguientes acciones, turnándose entre sí: ^[1]

• En el primer turno del juego, el jugador que controla a los policías coloca a cada policía en un vértice del gráfico (lo que permite colocar más de un policía en el mismo vértice).
• A continuación, el jugador que controla al ladrón coloca al ladrón en un vértice del gráfico.
• En cada turno posterior, el jugador que controla a los policías elige un subconjunto (posiblemente vacío) de policías y mueve cada uno de estos policías a vértices adyacentes. Los policías restantes (si los hay) permanecen en su lugar.
• En el turno del ladrón, puede moverse a un vértice adyacente o quedarse donde está.

El juego termina con la victoria de los policías siempre que el ladrón ocupe el mismo vértice que un policía. Si esto nunca sucede, el ladrón gana.

El número de policías de un gráfico es el número mínimo tal que los policías pueden ganar el juego en . ^[1] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$

Ejemplo

En un árbol , el número de policía es uno. El policía puede empezar en cualquier lugar y, en cada paso, moverse hacia el único vecino que esté más cerca del ladrón. Cada uno de los pasos del policía reduce el tamaño del subárbol al que está confinado el ladrón, por lo que el juego finalmente termina.

Al acercarse gradualmente, dos policías pueden acabar atrapando a un ladrón en cualquier bicicleta (aquí, un campo de béisbol).

En un gráfico de ciclo de longitud superior a tres, el número de policías es dos. Si solo hay un policía, el ladrón puede moverse a una posición a dos pasos del policía y mantener siempre la misma distancia después de cada movimiento del ladrón. De esta manera, el ladrón puede evadir la captura para siempre. Sin embargo, si hay dos policías, uno puede quedarse en un vértice y hacer que el ladrón y el otro policía jueguen en el camino restante. Si el otro policía sigue la estrategia del árbol, el ladrón eventualmente perderá.

Resultados generales

Todo grafo cuyo perímetro sea mayor que cuatro tiene un número de cop al menos igual a su grado mínimo . ^[2] De ello se deduce que existen grafos con un número de cop arbitrariamente alto.

Problema sin resolver en matemáticas :

¿Cuál es el mayor número de cop posible de un gráfico de vértices? ${\displaystyle n}$

(más problemas sin resolver en matemáticas)

Henri Meyniel (también conocido por los grafos de Meyniel ) conjeturó en 1985 que todo grafo de vértice conexo tiene un número de cop . Los grafos de Levi (o grafos de incidencia) de planos proyectivos finitos tienen circunferencia seis y grado mínimo , por lo que, de ser cierto, este límite sería el mejor posible. ^[3] ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle \Omega ({\sqrt {n}})}$

Todos los grafos tienen un número de cop sublineal. Una forma de demostrarlo es usar subgrafos que sean vigilables por un solo cop: el cop puede moverse para seguir al ladrón de tal manera que, si el ladrón alguna vez se mueve dentro del subgrafo, el cop puede capturarlo inmediatamente. Dos tipos de subgrafos que son vigilables son el vecindario cerrado de un solo vértice y un camino más corto entre dos vértices cualesquiera. El límite de Moore en el problema del diámetro de grado implica que al menos uno de estos dos tipos de conjuntos vigilables tiene tamaño . El uso de un cop para proteger este conjunto y la recursión dentro de los componentes conectados de los vértices restantes del grafo muestra que el número de cop es como máximo . ^{[3] [4]} ${\displaystyle \Omega (\log n/\log \log n)}$ ${\displaystyle O(n\log \log n/\log n)}$

Un límite superior sublineal más fuertemente en el número de cop,

${\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}$

Se sabe que, sin embargo, los problemas de obtener un límite estricto y de probar o refutar la conjetura de Meyniel siguen sin resolverse. Incluso se desconoce si la conjetura blanda de Meyniel , de que existe una constante para la cual el número de cop es siempre , es verdadera. ^[3] ${\displaystyle c<1}$ ${\displaystyle O(n^{c})}$

Calcular el número de cop de un gráfico dado es EXPTIME-hard , ^[5] y difícil para la complejidad parametrizada . ^[6]

Clases especiales de gráficos

Los gráficos de victoria de los policías son los gráficos con un número de policías igual a uno. ^[1]

Todo grafo planar tiene un número de cop como máximo tres. ^[1] De manera más general, todo grafo tiene un número de cop como máximo proporcional a su género . ^[7] Sin embargo, el límite inferior más conocido para el número de cop en términos del género es aproximadamente la raíz cuadrada del género, que está lejos del límite superior cuando el género es grande. ^[2]

El ancho de árbol de un grafo también se puede obtener como resultado de un juego de persecución-evasión, pero en el que el ladrón puede moverse a lo largo de caminos de longitud arbitraria en lugar de un solo borde en cada turno. Esta libertad adicional significa que el número de policías es generalmente menor que el ancho de árbol. Más específicamente, en grafos de ancho de árbol , el número de policías es como máximo . ^[8] ${\displaystyle w}$ ${\displaystyle \lfloor w/2\rfloor +1}$

Referencias

1. Aigner, M. ; Fromme, M. (1984), "Un juego de policías y ladrones", Discrete Applied Mathematics , 8 (1): 1–11, doi : 10.1016/0166-218X(84)90073-8 , MR  0739593
2. Mohar, Bojan (2017), Notas sobre el juego de policías y ladrones en gráficos , arXiv : 1710.11281 , Bibcode :2017arXiv171011281M
3. Baird, William; Bonato, Anthony (2012), "La conjetura de Meyniel sobre el número de policías: una encuesta", Journal of Combinatorics , 3 (2): 225–238, arXiv : 1308.3385 , doi :10.4310/JOC.2012.v3.n2.a6, MR  2980752, S2CID  18942362
4. Frankl, Péter (1987), "Policías y ladrones en grafos con gran circunferencia y grafos de Cayley", Discrete Applied Mathematics , 17 (3): 301–305, doi :10.1016/0166-218X(87)90033-3, MR  0890640
5. Kinnersley, William B. (2015), "Cops and robbers es EXPTIME-completo", Journal of Combinatorial Theory , Serie B, 111 : 201–220, arXiv : 1309.5405 , doi : 10.1016/j.jctb.2014.11.002, MR  3315605, S2CID  15432889
6. Fomin, Fedor V .; Golovach, Petr A.; Kratochvíl, Jan (2008), "Sobre la manejabilidad del juego de policías y ladrones", Quinta Conferencia Internacional IFIP sobre Ciencias Informáticas Teóricas—TCS 2008 , IFIP Int. Fed. Inf. Process., vol. 273, Nueva York: Springer, págs. 171–185, doi : 10.1007/978-0-387-09680-3_12 , MR  2757374
7. Schroeder, Bernd SW (2001), "El número de cop de un gráfico está limitado por ", Perspectivas categóricas (Kent, OH, 1998) , Trends Math., Boston: Birkhäuser, págs. 243-263, MR  1827672 ${\displaystyle \lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3}$
8. Clarke, Nancy Elaine Blanche (2002), Policías y ladrones bajo control , tesis doctoral, Canadá: Dalhousie University, MR  2704200, ProQuest  305503876