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:
- 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).
- 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:
- 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
:
- 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?
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: 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 ……
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… Lee más »
Betty Artesi, lo siento pero no hay algoritmos que nos ayuden a determinar si un grafo cualquiera es hamiltoniano.
[…] Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo gaussianos.com/algoritmo-definitivo-para-resolver-los-pro… por gabrielin hace nada […]
[…] "CRITEO-300×250", 300, 250); 1 meneos Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo gaussianos.com/algoritmo-definitivo-para-resolver-los-pro… por equisdx hace […]
Sí existen algoritmos para buscar ciclos hamiltonianos. Lo que pasa es que no son eficientes (es un problema NP-hard).
Habría que darle crédito a Carl Hierholzer por este algoritmo.
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!
[…] los comentarios 1 alma 20 Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo por Goefry en matemáticas hace nada […]
[…] Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo […]
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… Lee más »
Gracias Pepe, me gustaría conocer alguno que pruebe el tema de los hamiltonianos, aunque no sea eficiente.
Saludos
El algoritmo de Hierholzer está disponible como una de las funciones de análisis de Grafos, un software gratuito que podéis descargar desde:
http://arodrigu.webs.upv.es/grafos
Espero que os guste!
Alex
[…] partida. Es decir, lo que en teoría de grafos sería encontrar un circuito (o ciclo) euleriano. En este post dimos una caracterización de cuándo existe un circuito euleriano en un grafo no dirigido y […]
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… Lee más »
[…] fractal de la conjetura de Collatz, hablamos sobre integración por partes, os enseñé el algoritmo definitivo para dibujos en un solo trazo, vimos algunos resultados camino de la conjetura de Goldbach gracias a Rafael Tesoro, comenzamos […]
no sirvio