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.

(A la izquierda, imagen de los siete puentes de Königsberg. A la derecha, el grafo que representa dicha situación)

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 \Leftrightarrow 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 \Leftrightarrow 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 A, y comenzamos:

    1.- Elegimos un camino simple (que no repita ninguna arista) cerrado que comience y termine en A. 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 (A,B,E,A) y en este paso tomamos el camino (E,C,F,G,E), al insertarlo quedará

    (A,B,E,C,F,G,E,A)

    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 K_5):

    Partimos de un vértice, por ejemploA, y elegimos un camino simple cerrado que comience y acabe en él, por ejemplo (A,I,B,A). 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 (B,C,H,B) y lo insertamos en el anterior, quedando

    (A,I,B,C,H,B,A)

    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 (H,G,F,J,I,H) y lo insertamos en lo anterior, quedando

    (A,I,B,C,H,G,F,J,I,H,B,A)

    Eliminando aristas y vértices aislados queda

    Y ya es sencillo. Tomamos (G,C,D,G) y al insertar queda

    (A,I,B,C,H,G,C,D,G,F,J,I,H,B,A)

    Después, por ejemplo, (D,E,F,D), que al insertar nos da

    (A,I,B,C,H,G,C,D,E,F,D,G,F,J,I,H,B,A)

    Y, por último, (E,J,A,E), 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 A:

    (A,I,B,C,H,G,C,D,E,J,A,E,F,D,G,F,J,I,H,B,A)

  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 A y B. 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 a B (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, B 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 A y termina en el vértice B.

    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?

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. Buenísimo! Estudiaré la estrategia. Gracias!

    Vimos que para determinar si un ciclo es euleriano (que comience y termine en el mismo vértice) es necesario que tenga todos los vértices de grado par. Si comenzamos en un vértice y termina en otro (euleriano restringido) debe tener exactamente dos vértices de grado impar y los otros de grado par. Los ciclos son eulerianos si se los puede recorrer totalmente pasando sólo una vez por cada arista.

    Existen otros ciclos (hamiltonianos) que exigen recorrerlo totalmente pasando sólo una vez por cada vértice. Hay algún teorema que nos ayude a determinar si un ciclo es o no hamiltoniano?

    Betty Artesi

    Publica una respuesta
  2. Betty Artesi, lo siento pero no hay algoritmos que nos ayuden a determinar si un grafo cualquiera es hamiltoniano.

    Publica una respuesta
  3. Sí existen algoritmos para buscar ciclos hamiltonianos. Lo que pasa es que no son eficientes (es un problema NP-hard).

    Publica una respuesta
  4. Habría que darle crédito a Carl Hierholzer por este algoritmo.

    Publica una respuesta
  5. Es por cosas como estas,que Euler es mi matemático favorito (mas alla de la ignorancia matemática en la que pueda estar sumergido estudiando ingenieria y no matematicas o alguna carrera de ciencias exactas).

    Saludos de parte de un fiel seguidor de esta página!

    Publica una respuesta
  6. Una variante o generalización del problema de Ciclos de Euler es el problema DCC (doble cubrimiento por ciclo) en el que se pide demostrar que en un grafo dado existe un ciclo que pase exactamente dos veces (en el ciclo de Euler se pide exactamente uno).

    Para aquellos que prefieran la investigación original, de problemas no resueltos, a los pasatiempos (muy respetables por otra parte), vinculado a este problema DCC hay una importante conjetura de teoría de grafos, todavía abierta, que consiste en demostrar que todo grafo sin puentes (si tiene puentes es fácil demostrar que no tiene DCC) tiene un DCC (el problema se puede reducir a una clase más sencilla de grafos trivalentes llamados snarks que por cierto no son hamiltonianos: http://en.wikipedia.org/wiki/Snark_(graph_theory)).

    http://en.wikipedia.org/wiki/Cycle_double_cover

    Publica una respuesta
  7. Gracias Pepe, me gustaría conocer alguno que pruebe el tema de los hamiltonianos, aunque no sea eficiente.
    Saludos

    Publica una respuesta
  8. Amigos, me llamo Diego, y tengo una teoría matemática de la que se desprende un método o lagoritmo que entiende los caminos eulerianos y hamiltonianos como dos manifestaciones diferentes de una misma entidad, es decir, el mismo algoritmo es aplicable a la exigencia de pasar solo una vez por cada arista y a la de pasar por cada vértice. Sé que suena raro, y pondreis cara de excepticismo, pero puedo demostrarlo y someterlo al criterio de un experto en teoria de grafos para su revisión.
    Mi correo es: diegolopezosa@hotmail.es , si alguien está interesado podemos comunicarnosy ponerle al corriente. Un abrazo, Diego

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Seguro que en alguna ocasión te has topado con el problema del sobre o…
  2. Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo - [...] Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo gaussianos.com/algoritmo-definitivo-para-resolver-los-pro...  por gabrielin…
  3. Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo - [...] "CRITEO-300x250", 300, 250); 1 meneos Algoritmo definitivo para…
  4. Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo - [...] los comentarios 1 alma 20…
  5. Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo « ZOCO EL ANDALUS - [...] Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo [...]
  6. Nicolaas de Bruijn, del "BEST theorem" al confirmador de teorías matemáticas - Gaussianos | Gaussianos - [...] partida. Es decir, lo que en teoría de grafos sería encontrar un circuito (o ciclo) euleriano. En este post…
  7. Gaussianos cumple 6 años de vida - Gaussianos | Gaussianos - […] fractal de la conjetura de Collatz, hablamos sobre integración por partes, os enseñé el algoritmo definitivo para dibujos en…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *