¿Cómo se coge a un gato en un árbol?

Question

Supongamos que tenemos un grafo conexo finito (no dirigido) $ G $ sin bucles (bordes propios). Hay un gato en uno de los vértices de este grafo, pero no sabemos cuál.

Jugamos a lo siguiente: en cada turno, podemos comprobar uno de los vértices para ver si el gato está allí o no. Si el gato está, ganamos. Si no está, el gato recibe un movimiento en el que puede desplazarse a cualquier vecino del vértice en el que se encuentra, y debe usar este movimiento. Esto es importante: el gato no puede sentarse en su posición actual, tiene que moverse de ella cuando llegue su turno. Entonces pasamos al siguiente turno en el que hacemos un movimiento y el gato hace un movimiento, luego al siguiente turno, etc. hasta que atrapemos al gato o fracasemos en el intento para siempre.

Para qué grafos finitos $ G $ ¿tenemos una estrategia que garantice la victoria?

Algunas observaciones preliminares: lo que estamos haciendo es definir un dirigido estructura de grafos en el conjunto de potencias $ \mathbb P(V) $ de los vértices $ V $ de $ G $ y preguntando si podemos llegar al conjunto vacío desde el conjunto $ V $ . Para grafos pequeños es posible buscar exhaustivamente en este grafo dirigido utilizando la búsqueda en profundidad primero y determinar si existe una solución o no.

Además, esta imagen también deja claro que $ G $ debe ser en realidad un árbol si tenemos una estrategia que garantice atrapar al gato. Esto se debe a que si hay un ciclo en $ G $ que inicialmente está incluido en un conjunto, entonces después de hacer nuestra observación podemos excluir como máximo un vértice de este ciclo, y como cada vértice del ciclo tiene al menos dos vecinos cuando el gato hace su movimiento seguirá siendo posible que esté en cualquier parte del ciclo.

He aquí algunos casos sencillos: siempre tenemos una estrategia ganadora para el gráficos de trayectorias $ P_n $ . Si los vértices son $ 1 $ a través de $ n $ entonces simplemente observamos $ 2, 3, \ldots, n-1, n-1, n-2, \ldots, 3, 2 $ en orden y tenemos garantizado atrapar al gato haga lo que haga. Si no ves cómo funciona esto, vale la pena trabajarlo explícitamente.

He aquí un árbol para el que no tenemos ninguna estrategia que gane siempre:

No tengo una prueba de este hecho; se verifica mediante la búsqueda en profundidad, como he mencionado antes (aunque una prueba para este caso concreto no debería ser difícil de encontrar). Sin embargo, algunos primos cercanos de este árbol tienen estrategias ganadoras, como ésta:

La solución óptima (en el sentido de minimizar el número de movimientos en el peor de los casos) para este gráfico requiere como máximo catorce movimientos para atrapar al gato. Puedes probar a ver si la encuentras.

Como ya he dicho, estoy interesado en cualquier resultado no trivial sobre árboles de este tipo, así que aunque no tengas una clasificación completa puedes publicar cualquier resultado parcial que seas capaz de demostrar.

Nota: Si alguien tiene confusiones sobre el problema, este cuaderno Colab contiene una implementación de un verificador para saber si existe o no una estrategia siempre ganadora para cualquier grafo dado.

Answer 1

El árbol mínimo (por número de nodos) en el que no se puede atrapar al gato es este grafo de 10 nodos:

o
 \
  o
   \
    o
     \
      o - o - o - o
     /
    o
   /
  o
 /
o

Llama a este árbol $Y$ . Afirmo que si $T$ es cualquier árbol que no contenga $Y$ entonces puedes atrapar al gato. He aquí un esbozo del argumento:

Si $T$ no contiene $Y$ entonces $T$ consiste en un camino largo (la "columna vertebral") con un cierto número de caminos de longitud como máximo 2 (las "patas") que salen de cada vértice interno (es decir, que no es un punto final) de la columna vertebral. Algunas de las patas de un vértice interno de la columna vertebral pueden compartir otro vértice interno de la pata común, como en la segunda imagen del post original (véase el vértice central de la columna vertebral).

Para atrapar al gato, comience por el primer vértice interno de la columna vertebral. En cada vértice interno $v$ , si hay alguna pata de longitud 2 saliendo de $v$ y, a continuación, para cada uno de esos tramos, pasar al vértice interno del tramo y volver inmediatamente a $v$ . (Los vértices internos de la pierna compartida sólo deben visitarse una vez.) A continuación, pasa al siguiente vértice de la columna vertebral. Repite esto hasta llegar al último vértice interno de la columna vertebral y maneja todos sus catetos de longitud 2. Para el último cateto del último vértice interno de la columna vertebral $v$ no es necesario volver a $v$ después de caminar sobre la pierna. En este punto, hemos recorrido todos los vértices que no son hojas al menos una vez, y el gato está restringido a una de las biparticiones del árbol. Ahora vuelve a recorrer los mismos vértices, pero en orden inverso (una vez más, después de recorrer el último tramo no es necesario volver atrás). Esto atrapará al gato.

Por ejemplo:

A------B-------C-------D--------E---------F
      / \                       |
     G   H                      I
    /     \                     |
   J       K                    L

La secuencia ganadora de aciertos descrita anteriormente es B, G, B, H, B, C, D, E, I (en este punto hemos recorrido todos los vértices no hoja, ahora hacemos la misma secuencia a la inversa, omitiendo la B final) I, E, D, C, B, H, B, G.