Gráfico Cop-win
En teoría de grafos , un gráfico de cop-win es un gráfico 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 grafica o quédate quieto, hasta que el policía aterrice en el vértice del ladrón. [1] Las gráficas cop-win finitas también se denominan gráficas desmontables o gráficas construibles , porque pueden desmantelarse eliminando repetidamente un vértice dominado (una cuya vecindad cerrada es un subconjunto de la vecindad de otro vértice) o construirse agregando repetidamente dicho vértice. Los gráficos de cop-win se pueden reconocer entiempo polinomial por un algoritmo codicioso que construye un orden de desmantelamiento. Incluyen los gráficos cordales y los gráficos que contienen un vértice universal .
Los gráficos cop-win (y la clase complementaria de gráficos, los gráficos ladrón-ganador) se pueden definir mediante un juego de persecución-evasión en el que dos jugadores, un policía y un ladrón, se colocan en diferentes vértices iniciales de un gráfico dado, elegido primero por el policía y luego por el ladrón. Juegan por turnos; 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 el policía puede terminar un turno en el mismo vértice que el ladrón. El ladrón gana evadiendo indefinidamente al policía. Un gráfico cop-win es un gráfico con la propiedad de que, sin importar dónde empiecen los dos jugadores, el policía siempre puede forzar una victoria. [2]
La vecindad cerrada N [ v ] de un vértice v en un gráfico dado es el conjunto de vértices que consta de v en sí mismo 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 todos los demás vecinos de v también son vecinos de w . [3] Nowakowski y Winkler (1983)llamar 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 gráfico 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 gráfico es desmontable si y solo si tiene una orden de desmontaje. [2] [3]
Cada gráfico finito desmontable es cop-win. esto se puede demostrar por inducción matemática , con un gráfico de un vértice (ganado trivialmente por el policía) como caso base. Para una gráfica más grande, sea v cualquier vértice dominado. Según la hipótesis de inducción, el policía tiene una estrategia ganadora en la gráfica formada al eliminar v , y puede seguir la misma estrategia en la gráfica 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 resultará en una victoria real del juego, o en una posición en la que el ladrón está en v y el policía está en el vértice dominante, desde el cual el policía puede ganar en un movimiento más. [2][4] Un policía que sigue esta estrategia inductiva necesita como máximo n movimientos para ganar, independientemente de la posición inicial. Al elegir con cuidado la posición inicial del policía, se puede usar la misma idea para demostrar que, en una gráfica de n -vértices, el policía puede forzar una victoria en un máximo de n - 4 movimientos. [5] [6] [7]
| a | B | C | D | mi | F | gramo | h | ||
| 8 |    | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | B | C | D | mi | F | gramo | h | ||
