En teoría de grafos , una rama de las matemáticas, el número de policías o número de policías de un gráfico 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 gráfico.
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 permanecer sin ser atrapado. Así, los jugadores realizan las siguientes acciones, turnándose entre sí: [1]
El juego termina con una victoria para la policía 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 para que los policías puedan ganar el juego . [1]
En un árbol , el número de policía es uno. El policía puede comenzar 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.
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 forma, el ladrón puede evadir la captura para siempre. Sin embargo, si hay dos policías, uno puede permanecer 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 acabará perdiendo.
Todo gráfico cuya circunferencia sea mayor que cuatro tiene un número de policías al menos igual a su grado mínimo . [2] De ello se deduce que existen gráficos de un número de policías arbitrariamente alto.
¿ Cuál es el mayor número de policías posible de un gráfico de vértices?
Henri Meyniel (también conocido por los gráficos de Meyniel ) conjeturó en 1985 que todo gráfico de vértices conectados tiene un número de policía . Las gráficas de Levi (o gráficas 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]
Todos los gráficos tienen un número de policía sublineal. Una forma de demostrar esto es utilizar subgrafos que sean custodiados por un solo policía: el policía puede moverse para rastrear al ladrón de tal manera que, si el ladrón alguna vez entra en el subgrafo, el policía pueda capturarlo inmediatamente. Dos tipos de subgrafos que se pueden guardar son la vecindad cerrada de un solo vértice y el camino más corto entre dos vértices cualesquiera. El límite de Moore en el problema de grados de diámetro implica que al menos uno de estos dos tipos de conjuntos guardables tiene tamaño . Usar un policía para proteger este conjunto y recurrir dentro de los componentes conectados de los vértices restantes del gráfico muestra que el número de policías es como máximo . [3] [4]
Un límite superior más fuertemente sublineal en el número de policías,
es conocida. 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 suave de Meyniel , de que existe una constante para la cual el número de policía es siempre , es cierta. [3]
Calcular el número de policía de un gráfico determinado es EXPTIME-difícil , [5] y difícil para la complejidad parametrizada . [6]
Los gráficos de ganancia de policía son los gráficos con un número de policía igual a uno. [1]
Cada gráfico plano tiene un número de policías como máximo tres. [1] De manera más general, cada gráfico tiene un número de policías como máximo proporcional a su género . [7] Sin embargo, el límite inferior más conocido para el número de policías 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 del árbol de un gráfico también se puede obtener como resultado de un juego de persecución y 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 del árbol. Más específicamente, en gráficos de ancho de árbol , el número de policía es como máximo . [8]
