Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo

Seguro que en alguna ocasión te has topado con el problema del sobre o alguno del estilo. Sí, un problema en el que aparece una figura con líneas que unen puntos y donde se te pide que partiendo de un punto recorras todas las líneas sin pasar más de una vez por ninguna de ellas, pudiendo acabar en cualquier otro punto. En este post te voy a contar cuándo se pueden resolver estos divertidos pasatiempos y cómo hacerlo en los casos en los que es posible.

Cuándo puede resolverse

En primer lugar es necesario comentar que este tipo de figuras son grafos, es decir, un conjuntos de puntos denominados vértices y un conjunto de líneas denominadas aristas que conectan, cada una de ellas, dos vértices. Por tanto el objetivo de estos juegos es partir de un vértice y recorrer todas las aristas del grafo exactamente una vez (es decir, sin repetir ninguna). Normalmente se termina en otro vértice.

Este problema se parece mucho al de los puentes de Königsberg: partir de una zona cualquiera de tierra (vértice) y recorrer todos los puentes (aristas) sin pasar dos veces por ninguno de ellos (sin repetir arista), llegando al mismo punto de partida.

Resolver nuestro problema consiste en encontrar un camino euleriano, que es un camino (secuencia de aristas) simple (ninguna se repite) que recorra todas las aristas del grafo. Resolver el problema de los puentes de Königsberg consiste en encontrar un ciclo euleriano, que es un camino euleriano que comienza y termina en el mismo vértice. En el post que enlacé anteriormente sobre los puentes de Königsberg aparecen los dos teoremas que nos dicen cuándo se pueden resolver cada uno de estos dos problemas. Vamos a recordarlo aquí.

Partimos de un grafo conexo (no está separado en varios trozos) y llamamos grado de un vértice al número de aristas a las que pertenece dicho vértice. Entonces:

1. Cuando debemos comenzar y terminar en el mismo vértice:
   

   Teorema: Un grafo conexo posee un ciclo euleriano todos sus vértices tienen grado par.

   Por tanto, en el caso de los puentes de Königsberg no se puede conseguir lo que queremos (ya que ninguno de sus vértices tiene grado par).

2. Cuando comenzamos en un vértice y terminamos en otro:
   

   Teorema: Un grafo conexo contiene un camino euleriano tiene exactamente dos vértice de grado impar.

   Por tanto en el caso de los puentes de Königsberg tampoco se podría conseguir esto, ese grafo tampoco contiene un camino euleriano.

¿Se podrá hacer algo con el sobre?

Si calculamos el grado de cada vértice obtenemos un vértice con grado 4 y cuatro vértices con grado 3. Por tanto este grafo no contiene ni un ciclo ni un camino euleriano.

¿Y con el sobre abierto?

Tenemos un vértice con grado 2, dos vértices con grado 3 y tres vértices con grado 4. Vamos, que hay exactamente dos vértices con grado impar. Por tanto no tenemos ciclo euleriano, pero sí tenemos camino euleriano.

Cómo resolverlo

Bien, ya sabemos cómo ver si un grafo posee o no un ciclo o un camino euleriano. La cuestión que nos debería venir a la cabeza ahora es cómo encontrar ese ciclo o ese camino euleriano en el caso de que se pueda. Lo primero que se nos podría ocurrir es hacerlo a ojo, y de hecho es lo que habitualmente hacemos. Para grafos con pocos vértices y pocas aristas la técnica ojímetro suele servir, pero cuando el grafo es muy complejo nuestro ojo se lía tanto que normalmente no nos permitirá resolver nuestro problema. Vamos a ver un algoritmo muy sencillo para llegar a la solución.

Vamos a distinguir los dos casos anteriores, aunque al final son básicamente iguales. Veámoslo:

1. Caso 1: El grafo posee un ciclo euleriano

   Esto significa que todos sus vértices tienen grado par. Tomamos un vértice cualquiera, digamos , y comenzamos:

   1.- Elegimos un camino simple (que no repita ninguna arista) cerrado que comience y termine en . Eliminamos del grafo inicial todas las aristas que contiene ese camino cerrado y los vértices que hayan quedado aislados (sin aristas), si es que ha quedado alguno.

   2.- Del grafo que nos queda elegimos otro camino simple cerrado que comience y termine en uno de los vértices que teníamos en el anterior y lo insertamos en él. Por ejemplo, si la secuencia de vértices del primero era y en este paso tomamos el camino , al insertarlo quedará

   

   Después borramos las aristas del camino que hemos insertado y también los vértices que hayan quedado aislados.

   3.- Repetimos el paso 2.- las veces que haga falta hasta que hayamos tachado todas las aristas y todos los vértices. El camino resultante es un ciclo euleriano.

   Veamos un ejemplo con el siguiente grafo (que corresponde a ):

   

   Partimos de un vértice, por ejemplo, y elegimos un camino simple cerrado que comience y acabe en él, por ejemplo . Eliminamos esas aristas y los vértices que queden aislados. Nos queda este grafo:

   

   Tomamos ahora otro camino simple cerrado que comience y termine en uno de los vértices que ya tenemos, por ejemplo y lo insertamos en el anterior, quedando

   

   Eliminamos las aristas que contiene el camino y los vértices aislados que queden. Llegamos a este grafo:

   

   Y continuamos de la misma forma. Por ejemplo, ahora elegimos y lo insertamos en lo anterior, quedando

   

   Eliminando aristas y vértices aislados queda

   

   Y ya es sencillo. Tomamos y al insertar queda

   

   Después, por ejemplo, , que al insertar nos da

   

   Y, por último, , que después de insertarlo nos da uno de los posibles recorridos que podemos hacer en el grafo inicial para pasar por todas las aristas exactamente una vez comenzando y terminando por el vértice :

   

2. Caso 2: El grafo no posee un ciclo euleriano, pero sí un camino euleriano

   Es decir, nuestro grafo tiene exactamente dos vértices de grado impar. Supongamos que estos vértices son y . Entonces el camino euleriano debe comenzar en uno de ellos y terminar en el otro después de pasar por todas las aristas.

   La forma de encontrar este camino euleriano es sencilla:

   1.- Trazamos una arista que una los dos vértices de grado impar, es decir, una arista que vaya de a (aunque ya hubiera una). Con esto conseguimos que todos los vértices de nuestro grafo tengan grado par, por lo que podemos encontrar un ciclo euleriano con el método anterior.

   2.- Comenzamos la búsqueda de ese ciclo euleriano tomando un camino cerrado que comience y termine en uno de los vértices de grado impar del primer grafo, por ejemplo. Después eliminamos aristas y vértices aislados.

   3.- Tomamos un camino cerrado que comience en un vértice que ya tengamos pero que no contenga a la arista que hemos añadido en el paso 1. Insertamos en lo que llevamos y eliminamos aristas y vértices aislados.

   4.- Continuamos de la misma forma sin tomar la arista añadida en el primer paso, que debe dejarse para el final.

   5.- Cuando lleguemos al último camino cerrado, lo tomamos para que la arista elegida sea la última del camino. Después insertamos y quitamos la arista que habíamos añadido. Lo que nos queda es un camino euleriano que parte del vértice y termina en el vértice .

   Si queréis practicar este método podéis hacerlo, por ejemplo, con este grafo

   

   donde todos los vértices tienen grado par excepto los dos de abajo, que tienen grado 5. Podéis intentarlo también a ojo, pero creo que coincidiremos en que no es demasiado recomendable.

Con estos métodos no habrá pasatiempo de este estilo que se os resista, aunque todo es susceptible de mejora. ¿Conocéis algún otro algoritmo para resolver este tipo de problemas?