Estoy pensando en la siguiente variante de la policía y ladrón problema, disculpas si este es bien conocido, y las referencias son bienvenidos.
La puesta en marcha.
Deje $G=(V,E)$ ser un simple finito de grafo no dirigido.
Un ladrón de la función en $G$ algunos $R:\mathbb Z_{\ge 0}\to V$ tal que $R(t)$ $R(t+1)$ son vértices adyacentes en $G$, en particular, $R(t)\neq R(t+1)$ todos los $t$ (no hay bucles en $G$, y el ladrón es siempre "en marcha").
Un policía de la estrategia en $G$ es cualquier función de $C:\mathbb Z_{\ge 0}\to V$, sin restricciones de ningún tipo.
Nos dicen que el cop de la estrategia de $C$ captura ladrón $R$ si existe alguna $t\in \mathbb Z_{\ge 0}$ tal que $C(t)=R(t)$. Denotar $T(C,R)$ a ser el más pequeño tal $t$ si existen, de lo contrario conjunto a $\infty$. Si $T(C,R) = \infty$, entonces se dice $R$ evita o se evade la captura por $C$.
Por último, decimos que la gráfica de $G$ tiene un seguro de captura de la estrategia, si existe un cop de la estrategia de $C$ tal que para todo ladrón función de $R$, $T(C,R)$ finito.
Ejemplos.
(1) Si $G$ es un camino en el gráfico, a continuación, $G$ tiene un seguro de captura de la estrategia.
(2) Si $G$ es una garra con tres ramas, cada rama con dos bordes, a continuación, $G$ tiene un seguro de captura de la estrategia.
Tanto de arriba puede ser analizado por mirar a la paridad de las posibles posiciones de partida de el ladrón, ya que estos son grafos bipartitos. De hecho,
(3) Si $G$ es una estrella como el gráfico de $n\ge 3$ ramas, y cada rama tener dos bordes, a continuación, $G$ tiene un seguro de captura de la estrategia. (Aquí se $G$ $2n+1$ vértices.)
Sketch. Indicar el punto de centro de la $G$$c$, y la rama de $i$ se compone de los vértices $a_i$ $b_i$ donde $a_i$ está conectado a $c$$b_i$. Si $n$ es impar, considere la posibilidad de la cop de la estrategia de $C$$a_1,c,a_1,c,a_2,c,\ldots,a_n,a_1,c,a_1,c,a_2,c,\ldots,a_n$. La primera mitad asegura ladrón es capturado si el ladrón se inicia en cualquier $a_i$ posición. Ahora si no hemos capturado al ladrón en la primera mitad, entonces el ladrón debe comenzó a $b_i$ posición, que después de la primera mitad que ahora desembarca en un $a_i$ posición, por lo que, volvemos a repetir la estrategia. Podemos adaptar de manera similar al $n$ es incluso.
Algunas de las preguntas.
(1) ¿Qué simple finito gráfica tiene un seguro de captura de la estrategia? [Se puede mostrar fácilmente que si $G$ tiene cualquier ciclo, a continuación, $G$ no tiene ningún tipo de seguro de captura de la estrategia. En efecto, si al contrario que la cop de la estrategia de $C$ es un seguro de captura de estrategia en $G$ con un ciclo, podemos usar $C$ a producir un ladrón función de $R$ que siempre evitar la captura, como cada vértice en el dicho de que el ciclo de grado $\ge 2$.] Por lo que deben ser los bosques.
(2) Considerar, a continuación, $G$ a ser conectado. A continuación, $G$ tiene un seguro de captura de la estrategia implica la $G$ es un árbol. Hacer todos los árboles tienen un seguro de captura de la estrategia? Yo no estoy tan seguro de que aquí, por una garra con tres ramas, pero cada rama con 3 o más aristas en ella, hay un seguro de captura de la estrategia?
(3) Si $G$ tiene un seguro de captura de la estrategia de $C$, entonces para todos ladrón función $R$, $T(C,R)$ es finito. Pero es $T(C,R)$ delimitado en todos los posibles $R$?
Soy consciente de la búsqueda de la evasión variante, donde tanto la policía y ladrón alternativo vez, tanto con información perfecta de donde uno al otro, ambos pueden omitir ir, y ambos deben mover a lo largo del borde. En tal caso, se analizan las posiciones de llamada esquinas (vértices $v$ cuyo cerrado vecindario $N[v]$ están cubiertos por un único vértice), y buscar en la eliminación/adición de estos rincones. Este podría ser adaptado aquí así?
