Caminos de Euler y circuitos de Euler

Un camino de Euler

Recuerdo que me desafiaron a un juego mental en el que me dieron una imagen de un gráfico con puntos y líneas de conexión y me dijeron que buscara una manera de dibujar la misma figura sin levantar el lápiz y solo dibujar cada lado una vez. No se me permitió pasar por un lado que ya había dibujado. Poco sabía entonces que lo que estaba haciendo estaba realmente relacionado con el tema que estamos discutiendo en esta lección en video.

Lo que hice fue dibujar un camino de Euler , un camino en un gráfico donde cada lado se atraviesa exactamente una vez. Un gráfico con un camino de Euler en él se llama semi-euleriano . Disfruté mucho el desafío y pensé poco en las conexiones matemáticas que tenía. Déjame mostrarte el juego mental que me dieron.

Para dibujar esta forma sin levantar el lápiz y repasar cada línea exactamente una vez, tuve que comenzar en el punto 1, luego ir al punto 3, luego al 2, luego al 4 y luego al 3 nuevamente. ¿Ves cómo repasamos cada línea solo una vez? Esa es la característica definitoria de un gráfico de Euler. Además, tenga en cuenta que terminamos en un lugar diferente.

Otra característica de un gráfico semi-euleriano es que como máximo dos de los vértices serán de grado impar, lo que significa que tendrán un número impar de aristas que lo conectarán con otros vértices. Todos los demás vértices serán pares. En este gráfico, vemos que los vértices 1 y 3 son impares, mientras que 2 y 4 son pares.

Ejemplo 1

Veamos otro ejemplo. Esta vez, vea si puede resolverlo.

Nuevamente, lo que estamos tratando de hacer es encontrar un camino en el gráfico de modo que estemos cruzando cada borde exactamente una vez. Recuerda que un camino te lleva de un punto a otro. ¿Puedes encontrar uno en este gráfico?

Intenta comenzar en el punto 2. Ahora baja al punto 1. Luego al punto 4, vuelve al punto 2, al punto 3 y finalmente al punto 4. ¡Tenemos un camino de Euler! Hemos cruzado cada borde exactamente una vez. Entonces esto significa que este gráfico es semi-euleriano.

¿Hay otros caminos de Euler en este gráfico? Sí hay. También podemos anotar estos caminos de Euler simplemente escribiendo los nombres de los vértices que pasamos. Entonces, otro camino de Euler en este gráfico es 4, 3, 2, 4, 1, 2. Observe que con todos estos caminos, terminamos en un punto diferente de donde comenzamos. ¿Hay más formas de dibujar esta forma usando un camino de Euler? No les diré cuáles son, pero les diré que hay un total de 6 caminos de Euler en este gráfico. Lo que hace que cada camino sea diferente es el orden en que se dibujan los bordes.

Un circuito de Euler

Si terminamos en el mismo punto en el que comenzamos, entonces tenemos lo que se llama circuito de Euler , un circuito en un gráfico donde cada borde se atraviesa exactamente una vez y que comienza y termina en el mismo punto. Mire este gráfico y vea si puede dibujarlo sin levantar el lápiz, repasar cada borde solo una vez y comenzar y terminar en el mismo punto:

Al igual que con los caminos de Euler, podemos tener varios circuitos de Euler en un gráfico. Este es un ejemplo simple, y es posible que ya vea varias formas de dibujar esta forma usando un circuito de Euler. Debido a que esta gráfica tiene un circuito de Euler, la llamamos Euleriana . Un circuito de Euler que tiene esta gráfica es 2, 3, 4, 1, 2. Alternativamente, también puede dibujar esta forma siguiendo el circuito de Euler 1, 2, 3, 4, 1. Tenga en cuenta que nuestros puntos de inicio y final son los lo mismo en estos circuitos. Terminamos donde comenzamos.

Además, para un gráfico euleriano, todos los vértices son pares, lo que significa que todos los vértices tendrán un número par de aristas que lo conectarán con otros. Mire nuestro gráfico anterior y verá que todos nuestros vértices tienen un número par de aristas.

Ejemplo 2

Podemos tener circuitos de Euler simples y también podemos tener circuitos de Euler más complejos. Veamos uno. Vea si puede ver el circuito de Euler usted mismo esta vez.

Esta vez, los bordes están etiquetados en lugar de los vértices. ¿Puedes dibujar este usando un circuito de Euler? Siga los bordes en orden alfabético y verá un circuito de Euler. Esto significa que esta gráfica es euleriana. ¿Ves más circuitos de Euler en este gráfico? Veo al menos uno más.

Resumen de la lección

Repasemos lo que hemos aprendido. Una ruta de Euler es una ruta en un gráfico donde cada lado se recorre exactamente una vez. Un gráfico con un camino de Euler en él se llama semi-euleriano . A lo sumo, dos de estos vértices en un gráfico semi-euleriano serán impares. Todos los demás estarán parejos. Un circuito de Euler es un circuito en un gráfico donde cada borde se atraviesa exactamente una vez y comienza y termina en el mismo punto. Una gráfica con un circuito de Euler se llama Euleriana . Todos los vértices de un gráfico euleriano serán pares. Puede tener varias rutas de Euler en un gráfico. También puede tener varios circuitos de Euler en un gráfico. La diferencia entre cada ruta y circuito es el orden en el que se pasan los bordes.

Los resultados del aprendizaje

Después de esta lección, tendrá la capacidad de:

• Definir la ruta de Euler y el circuito de Euler
• Explica qué son las gráficas eulerianas y semi-eulerianas.

Rodrigo Ricardo Editor y fundador