¿Cuánta memoria necesita una hormiga que recorre un grafo para decidir si el grafo es en realidad un árbol?

Question

Este es sólo un pequeño e interesante problema que se me ha ocurrido hoy y que no tengo ni idea de cómo resolverlo, así que por eso lo estoy publicando aquí.

---

Dejemos que $G$ sea un grafo finito, no dirigido y conectado. Damos a cada nodo un identificador único, digamos un número entero positivo. Se coloca una hormiga en un nodo aleatorio. La hormiga sólo puede "ver" el identificador del nodo en el que está y los identificadores de los vecinos del nodo en el que está. Ahora, cada segundo, la hormiga se desplaza a un vecino del nodo en el que se encuentra. El objetivo de la hormiga es detectar si $G$ es de hecho un árbol.

La cuestión es que la hormiga sólo tiene una cantidad finita de memoria (reescribible); sólo puede recordar una cierta cantidad de los nodos que ha visitado. Dejemos que $\alpha(G)$ es la cantidad mínima de memoria que necesita la hormiga para poder determinar con éxito si $G$ es de hecho un árbol.

Pregunta 1: ¿Cómo determinamos $\alpha(G)$ ?

Pregunta 2: Dado $n\in\mathbb{N}$ ¿podemos especificar todos los gráficos $G$ con $\alpha(G)=n$ ?

Pregunta extra: ¿Existe un algoritmo que la hormiga pueda utilizar siempre?

---

Lo que he encontrado hasta ahora:
Lo que he encontrado hasta ahora es que si $G$ es un ciclo, tenemos $\alpha(G)\le 3$ . Cuando la hormiga se pone en marcha, guarda en la memoria los identificadores del nodo en el que se encuentra y de sus dos vecinos. A continuación, se desplaza aleatoriamente a uno de sus vecinos. Después, simplemente sustituye el identificador del vecino que tiene en la memoria por el identificador del otro vecino y se desplaza al nodo con el identificador guardado. En cuanto todos los identificadores de los vecinos están en la memoria, la hormiga sabe que debe haber viajado en un ciclo y, por lo tanto $G$ no podía ser un árbol.

Además, si $G$ es un "ocho" (dos ciclos con algunos nodos comunes consecutivos), tenemos $\alpha(G)\le 4$ . Usamos el mismo algoritmo que con los ciclos, pero si llegamos a un punto en el que el nodo en el que está la hormiga tiene tres vecinos, dos de los cuales con su idenitfier no en la memoria, optamos por ignorar uno y seguir con nuestro algoritmo. Lo único que hacemos, es guardar el identificador de ese tercer vecino en memoria, la primera vez y la segunda (cuando toda la memoria está utilizada), no hacemos nada. Viajando a lo largo de uno de los ciclos, inevitablemente terminaremos junto a uno de estos nodos "permanentemente marcados" y por lo tanto, podremos decidir que no es un árbol.

Si $G$ es un gráfico completo con más de dos vértices, podemos tomar $\alpha(G)\le 2$ . Cuando la hormiga parte, pone en memoria el identificador del nodo en el que se encuentra y el identificador de uno de sus vecinos, tras lo cual se desplaza a uno de los vecinos cuyo identificador no está almacenado en memoria. Si ahora tiene dos vecinos con sus identificadores en memoria (los tiene), el grafo debe contener un triángulo y, por tanto, no puede ser un árbol.

Answer 1

Podemos comprobar que cualquier gráfico es un árbol con $n=4$ si a la hormiga se le permite un pequeño "truco": poder ordenar los identificadores de vértice (los que puede ver o recordar) por tamaño. Esto tiene sentido si los identificadores de vértice son enteros, no tanto si los vértices tienen colores únicos o algo así.

Si podemos hacer esto, entonces podemos hacer un recorrido por el gráfico $G$ utilizando la siguiente regla (llamada regla de la gira ): cada vez que se introduce un nodo $v$ del nodo $w$ el siguiente nodo al que vayas debería ser

• El vecino de $v$ que tiene la menor etiqueta mayor que $w$ o
• Cuando no existe tal vecino ( $w$ tenía la mayor etiqueta entre los vecinos de $v$ ) el vecino de $v$ que tiene la etiqueta más pequeña.

Sólo la aplicación de esta regla requiere una célula de memoria, utilizada para recordar la etiqueta de $w$ .

Si el gráfico $G$ es un árbol, acabamos recorriendo el perímetro de una incrustación plana de $G$ atravesando cada arista una vez en cada dirección. Si $G$ no es un árbol, podemos recorrer todas las aristas o sólo un subconjunto. Lo que distingue a los árboles de los no árboles es la siguiente caracterización:

$G$ es un árbol si y sólo si este recorrido tiene la siguiente propiedad (llamada propiedad de retroceso ): cada vez que dejamos un nodo $v$ para ir a $x$ la próxima vez que veamos $v$ es volviendo de $x$ .

(La propiedad de retroceso es forzada para cualquier recorrido de un árbol, porque no hay ciclos. Lo contrario es más difícil de ver, pero se puede demostrar por inducción en el tamaño de $G$ : esencialmente, un recorrido con la propiedad de retroceso sólo puede "dar la vuelta" en un vértice de grado $1$ y omitiendo este vértice se obtiene un recorrido con la propiedad de retroceso en un gráfico más pequeño).

Así que podemos comprobar si $G$ es un árbol comprobando la propiedad de retroceso para cada arista del recorrido. Más concretamente, utilizamos el siguiente algoritmo.

Células de memoria utilizadas:

• START el nodo en el que empezamos.
• SOURCE , TARGET : los dos puntos finales del borde del recorrido que estamos comprobando para ver si se satisface la propiedad de retroceso.
• LAST-VISITED : el vértice en el que estábamos en el paso anterior (necesario para aplicar la regla de recorrido).

Algoritmo:

1. Inicializar START . Establecer SOURCE a START , y establecer TARGET al vecino de START con la etiqueta más baja.
2. Comience el recorrido por ese vecino, actualizando LAST-VISITED a START como lo dejamos.
3. Siga la regla de la gira, actualizando LAST-VISITED apropiadamente (asumiré que lo hacemos sin mencionarlo a partir de ahora).
4. La próxima vez que lleguemos a SOURCE : si LAST-VISITED no es TARGET entonces no se cumple la propiedad de retroceso, por lo que $G$ no es un árbol.
5. De lo contrario, reiniciamos el recorrido desde el punto en el que íbamos de SOURCE a TARGET . Es decir, fijamos SOURCE al valor de TARGET y dar un paso hacia TARGET .
6. En el siguiente paso (que la hormiga puede identificar, si es muy olvidadiza, por la propiedad que SOURCE es igual a TARGET ) establecemos TARGET igual al siguiente destino a lo largo del recorrido, y volver al paso 3.
7. Cuando nos encontramos con SOURCE igual a START y el ajuste TARGET igual al vecino de START con la etiqueta más baja, sabemos que estamos comprobando esa arista por segunda vez, así que hemos comprobado todas las aristas y sabemos que $G$ es un árbol.

(En el transcurso de este algoritmo, SOURCE y TARGET de la hormiga, mientras que la hormiga recorre partes del recorrido varias veces).