• About

ZOCO EL ANDALUS

~ No hay otra "alternativa"

ZOCO EL ANDALUS

Archivos de etiqueta: aristas

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

15 Miércoles Feb 2012

Posted by Directorio de Noticias in CIENCIA

≈ Deja un comentario

Etiquetas

algoritmo, aristas, cualquiera, dibujos, dos, dos veces, grafo, lineas, problemas, solo

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 aristasque 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 eulerianoEsto 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 eulerianoEs 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?

 

 Download as ePub

Artículos relacionados

  • Sigue el camino…módulo 7 (II)
  • La función Phi de Euler: otra genialidad del maestro
  • La fórmula de Euler: una maravilla matemática
  • Numeri idonei
  • Los números de Catalan

Autor: ^DiAmOnD^  |  Publicado el 13 de February de 2012 en

http://gaussianos.com/algoritmo-definitivo-para-resolver-los-problemas-sobre-dibujos-en-un-solo-trazo/
Categorías: Aprenda como, Topología

Anuncios
abril 2018
L M X J V S D
« Feb    
 1
2345678
9101112131415
16171819202122
23242526272829
30  

Entradas recientes

  • Algoritmo definitivo para resolver los problemas sobre dibujos en un solo trazo
  • Modificación de Ubuntu con gran cantidad de software instalado, configurado y listo para usarse
  • La nueva mentira global se hace tangible: WikiLeaks dice que “ya empezó” una invasión alienigena
  • Todas las medidas de #Rajoy #INVESTIDURA
  • NOTICIAS ALTERNATIVAS
  • BLOG RECOMENDADO lacrimaseca.wordpress.com
  • NOTICIAS DESTACADAS del 14 sep 2011

RSS AQUI hay TOMATE

  • De cómo Estados Unidos pospone su quiebra y aumenta la pobreza, imprimiendo billetes indiscriminadamente De OBLIGADA LECTURA
  • LOS VÍNCULOS ENTRE EL DIARIO PÚBLICO (MEDIAPRO) Y LA MONARQUÍA QATARÍ Y AL JAZEERA o ¿Por qué manipula Público la información sobre Libia y Siria?
  • Paul Krugman añora la economía de equivalencia ante la injusticia de la baja fiscalidad de los ricos
  • CINCO DE LOS ‘LOBBIES’ MÁS PODEROSOS Todos SIONISTAS
  • ¿Nueva guerra del Comando África de EE.UU.?
  • El fraude de la manipulación mediática de Occidente en la “revuelta árabe”: Siria
  • El mundo en guerra contra el trabajador #PRIMAVERAVALENCIANA PASALO RECOMENDADÍSIMO
  • #primaveravalenciana Brutalidad policial sin límites contra menores de edad, periodistas, profesores y viandantes en el centro de Valencia
  • El capitalismo global y el fascismo siglo 21
  • AIPAC El lobby judío que manda en EEUU y por ende en el mundo

RSS CIBERNOTICIAS EXPRESS

  • CIBERNOTICIAS ALTERNATIVAS
  • #ESPECIAL #19F – CLAMOR contra el DECRETAZO – ¡ NO a la REFORMA LABORAL!
  • #EstamosconGrecia VIDEOS, FOTOS, TUITS 2ª ACTUALIZACION #TODOSconGRECIA xq #GRECIAsomosTODOS
  • Esta reforma laboral no merece una huelga, merece un cierre patronal
  • REINO UNIDO SE PLANTEA USAR ARMAS QUÍMICAS, DISPARAR ARMAS Y USAR UN LASER CEGADOR CONTRA MANIFESTANTES
  • CIBERNOTICIAS ALTERNATIVAS del día
  • El Gobierno volverá a prestar dinero a la banca para apoyar nuevas fusiones de entidades a través del FROB
  • En EEUU los responsables de la crisis hipotecaria rendirán cuentas e indemnizará a los desahuciados
  • La derecha siempre enmierdando: A Chávez le queda menos de un año de vida
  • BOE 23 enero, Los politicos se autoregalan 20.7 MILLONES € PUBLICOS

Actualizaciones de Twitter

  • ¡ANONYMOUS TIMES está disponible! paper.li/ARMAKdeODELOT/… Gracias a @amuozp @ale1182 @mariandowney08 #informe #ciencia 1 hour ago
  • RT @JesusCintora: “El sueldo de los jóvenes ha caído un 11% en España desde el inicio de la crisis y la temporalidad ha crecido casi 10 pun… 4 hours ago
  • RT @Sanfermin00: 'Cuando te dicen que si no fuera por ti no comerían, se te cae el alma al suelo' publico.es/sociedad/casa-… vía @publico_es 4 hours ago
  • RT @PodemosAhora: Buenos días ¡'¡'¡'¡'¡' Barbarie capitalista: El número de ultramillonarios creció un 10% en 2017 y crecerá un 40% más h… 4 hours ago
  • RT @grancocolio: Bien claro lo dice aquí lo que es la libertad de expresión. El Gobierno lo penaliza, dice el Ministro Zoido que la pitada… 4 hours ago
  • RT @vmm7773: Ahora me entero que en francés "El partido del cambio sensato transversal CS" .... se traduce como ... "Le parti d'extrême-dro… 4 hours ago
  • RT @Tesa29053098: #FelizSábado Igual que a un deportista lo PILLAN DOPADO lo echan .El partido popular que han ido DOPADO a las eleccione… 4 hours ago
  • RT @Yo_Soy_Asin: MALDITOS COMUNISTAS PORTUGUESES Ahora va la UE y nos lo pone como ejemplo en gasto en I+D Que será lo siguiente, salir de… 4 hours ago
  • ¡El Diario de ARMAK de ODELOT está disponible! paper.li/ARMAKdeODELOT/… #mundo 5 hours ago
  • The latest #SPANISH REVOLUTION! paper.li/ARMAKdeODELOT/… Thanks to @ffchll @jotabelandria @jaka6763 #recomendaciones 6 hours ago
  • ¡DEMOCRACIA REAL YA está disponible! paper.li/ARMAKdeODELOT/… Gracias a @magdacamposgome @MJose23342951 @Morenaserena #sociedad 7 hours ago
  • ¡El ZOCO de ODELOT está disponible! paper.li/ARMAKdeODELOT/… Gracias a @FernandezPech @photour_toledo @QRooGrafico1 #cultura 7 hours ago
  • ¡El Diario de ARMAK de ODELOT está disponible! paper.li/ARMAKdeODELOT/… #noticias #mundo 9 hours ago
  • The latest #SPANISH REVOLUTION! paper.li/ARMAKdeODELOT/… Thanks to @Dennis08481468 @FERMINATX @Sylebram64 #salud #recomendaciones 10 hours ago
  • ¡DEMOCRACIA REAL YA está disponible! paper.li/ARMAKdeODELOT/… Gracias a @AnimoHermano @mreyespoblete @HobOnly #salud #sociedad 10 hours ago
Follow @ARMAKDEODELOT

Blog Stats

  • 4,889 hits
Anuncios

RSS INFORMACION ALTERNATIVA

  • Las 9 tácticas del manipulador de medios
  • Occidente no consigue aislar a Irán: 120 países se reúnen en Teherán
  • El 15M se manifestará contra Merkel el día de su visita a Madrid
  • Facebook, instrumento del imperialismo 2.0
  • El rescate de la banca habrá que devolverlo en 3 años y a un 3-4% de interés
  • ¿Cómo afectará el rescate a los ciudadanos?
  • Las previsiones de Krugman para España LLegó la hora de la verdad
  • #12M15M 10 personas se suicidan a diario en España por la crisis
  • EL #15M exige #Eleccionesgeneralesya x #FraudeElectoral #RajoyDimisión #12M15M
  • Desmontando la estafa de la crisis punto por punto ¿ Y... ahora qué?

Meta

  • Registrarse
  • Acceder
  • RSS de las entradas
  • RSS de los comentarios
  • WordPress.com

#15M #15m #marchabruselas #20n #democraciarealya #MARCHABRUSELAS #nolesvotes 14 sep 2011 21 JULIO 2011 afganistan agua alimentos ATENTADOS banco BENEFICIOS BIN LADEN Camps chófer coches colapso condonación COPYRIGHT corrupción crisis DESOBEDIENCIA CIVICA despacho deuda deuda española EEUU Ejército USA especulacion ESPIONAJE euro europa GENERACION NINI hambre II Encuentro Estatal de DRY IMPERIALISMO AMERICANO INMUNIDAD intervencion IRAK IRAN ISLANDIA ISP israel LACRIMASECA LIBIA lpentagono MANIPULACIÓN MATANZAS MEDIOS motor MOVILIZACIONES NORICIAS NORUEGA noticias nultinacionales PARO política portugal PP PRIVACIDAD privatizar redes sociales REVOLUCION SILENCIADA secretariA SIMBOLO INFINITO siria SOBREDOSIS SOLDADOS SUBE DESEMPLEO SUBEN BENEFICIOS tráfico de opio Valencia VIA LACTEA zona

Escribe tu dirección de correo electrónico para suscribirte a este blog, y recibir notificaciones de nuevos mensajes por correo.

Únete a 1 seguidor

Blog de WordPress.com.

Cancelar