Juego de policías y ladrones en grafos
2018
Policias y ladrones es un juego que se juega sobre un grafo. En este juego los jugadores
se desplazan de vertice en vertice a traves de la aristas del grafo. El objetivo de los
policias es capturar al ladron, mientras que el ladron tiene que huir de los policias.
Este juego se introdujo durante los anos 80 y ha sido ampliamente estudiado desde
entonces. Una de las caracteristicas mas estudiadas de este juego es el "cop number", es
decir, el numero minimo de policias necesarios para capturar al ladron, ya que uno solo
no siempre puede capturar al ladron, y colocando uno en cada vertice seria muy
sencillo.
En los primeros capitulos de este documento se presenta un estudio de este juego, en el
que se mostraran tanto algunas cotas del "cop number" como algunas estrategias que
deben seguir los jugadores para ganar.---ABSTRACT---Cops and robbers is a game played on a graph. In this game players move from vertex
to vertex across the edges of the graph. The objective of the cops is to capture the
robber, while the robber try to avoid the cops.
This game was introduced during the 80s and has been widely studied since then. One
of the most studied features of this game is the "cop number", which is the minimum
number of cops needed to capture the robber, since only one cop can not capture the
robber, and placing one in each vertex would be very simple.
In the first chapters of this document, a study of this game is presented, in which some
bounds of the "cop number" are shown, as well as some strategies that the players must
follow to win.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI