De un solo trazo
Vértices impares
Aristas trazadas
Formas de trazarla

    • 0 vértices impares: un circuito, de cualquier vértice a sí mismo
    • 2 vértices impares: un camino de uno al otro
    • 4 o más: imposible de un solo trazo

    Método

    Más sobre caminos y circuitos eulerianos

    Buscador de caminos eulerianos

    ¿Se puede dibujar la casa de San Nicolás sin levantar el lápiz y sin repasar ninguna línea? Sí, pero solo empezando por una de las dos esquinas de abajo, y hay 44 formas desde cada una. La razón es el grado de un vértice, el número de líneas que se juntan en él: cada vez que el lápiz pasa por un vértice gasta dos de sus líneas. Leonhard Euler encontró esta regla en 1736 con los siete puentes de Königsberg. Traza tú mismo una figura, mira dónde te atascas y por qué, pide una pista o mira cómo la dibuja un algoritmo. Elige una figura y trázala: toca un vértice para empezar y luego las aristas o los vértices siguientes en orden, o arrastra de vértice en vértice. Cada arista solo se usa una vez. Atrás deshace un paso, Pista muestra la siguiente arista segura y Resolver ejecuta paso a paso el algoritmo de Fleury o el de Hierholzer. Los vértices impares están rellenos y la marca de cada vértice es su grado. En Dibujar, toca un espacio vacío para añadir un vértice y dos vértices para unirlos, otra vez para una segunda arista; arrastra un vértice para moverlo. Borrar elimina vértices y aristas. Cuando hay más de dos vértices impares, Añadir coloca las aristas que hacen trazable la figura.

    Cómo funciona

    1. Elige una figura, como los siete puentes de Königsberg, la casa de San Nicolás o una estrella, o dibuja la tuya en Dibujar, con tantas aristas como quieras entre dos vértices.
    2. Toca un vértice para empezar y luego las aristas o los vértices en orden, o arrastra de vértice en vértice. Si te atascas, la línea de estado dice por qué; Atrás deshace un paso y Pista muestra una arista segura.
    3. Lee la regla de los grados bajo la figura, añade a una figura imposible las aristas que propone o pulsa Resolver para ver cómo el algoritmo de Fleury o el de Hierholzer la dibuja paso a paso.

    Por qué deciden los vértices impares

    Un trazo que pasa por un vértice llega por una línea y sale por otra, así que gasta las líneas de ese vértice de dos en dos. Solo donde el trazo empieza o termina puede quedar una línea sin pareja. Por eso un vértice con un número impar de líneas tiene que ser el principio o el final. Sin vértices impares, el trazo termina donde empezó: un circuito euleriano. Con dos, va de uno al otro: un camino euleriano. Con cuatro o más hay demasiados extremos para un solo trazo, y k vértices impares necesitan k/2 trazos. Königsberg tenía cuatro zonas de tierra, con cinco, tres, tres y tres puentes: las cuatro impares, así que ningún paseo podía cruzar cada puente una vez. Un puente nuevo entre dos de ellas habría hecho posible el paseo.

    Los algoritmos de Fleury y de Hierholzer

    Saber que una figura se puede dibujar no es lo mismo que dibujarla: un trazo descuidado puede quedar aislado de las líneas que aún necesita. El algoritmo de Fleury, de 1883, lo evita con una regla: no cruces nunca un puente, es decir, una línea cuya eliminación partiría en dos las líneas restantes, salvo que no haya otra línea. El algoritmo de Hierholzer, de un artículo publicado en 1873, es más rápido: camina por donde quieras hasta atascarte, lo que solo puede ocurrir en el punto de partida, y luego, desde un vértice del recorrido que aún tenga líneas libres, recorre otro bucle cerrado e insértalo en el recorrido. Su tiempo crece en proporción al número de aristas, y así es como los ordenadores encuentran caminos eulerianos.

    Preguntas frecuentes

    ¿Qué diferencia hay entre un camino euleriano y un circuito euleriano?

    Los dos usan cada arista de un grafo exactamente una vez. Un circuito euleriano termina donde empezó; un camino euleriano termina en otro sitio. Un grafo conexo tiene un circuito cuando todos los vértices tienen grado par, y un camino cuando exactamente dos vértices tienen grado impar; el camino va entonces de uno al otro.

    ¿Por qué no se pueden cruzar una vez cada uno de los siete puentes de Königsberg?

    Dibuja cada zona de tierra como un vértice y cada puente como una arista. La isla de Kneiphof tenía cinco puentes y las otras tres zonas tres cada una, así que los cuatro vértices son impares. Un paseo solo puede empezar o terminar en un vértice impar, y cuatro son demasiados. Añadir un puente entre dos de ellos deja dos vértices impares, y el paseo pasa a ser posible.

    ¿De cuántas formas se puede dibujar la casa de San Nicolás?

    44 desde cada una de las dos esquinas de abajo, 88 en total, contando otro orden u otro sentido como otra forma. Desde cualquier otro vértice no se puede, porque las esquinas de abajo son las dos únicas con un número impar de líneas. La aplicación cuenta así las formas de las figuras pequeñas.

    ¿Qué es un puente en un grafo?

    Una arista cuya eliminación parte un grafo conexo en dos trozos. El algoritmo de Fleury nunca cruza un puente de las aristas restantes mientras tenga otra opción, porque dejaría atrás parte de la figura. En esta aplicación, a un trazo que se atasca tras cruzar un puente demasiado pronto se le dice qué paso fue.

    ¿Puede haber más de una arista entre dos vértices?

    Sí. Un grafo con aristas paralelas se llama multigrafo, y Königsberg lo necesita: dos puentes unían el Kneiphof con cada orilla. En Dibujar, toca de nuevo dos vértices para añadir otra arista entre ellos, hasta cuatro. La regla de los grados funciona igual, contando cada arista.

    ¿Listo para probarlo?

    Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

    Ir al editor