Modelos matemáticos de circuitos de Euler y caminos de Euler

Rutas y circuitos de Euler

En esta lección en video, veremos cómo las rutas y los circuitos de Euler se pueden usar para resolver problemas del mundo real. Verás cómo el cartero y el vendedor hacen uso de estos caminos y circuitos. También se le presentará un problema aparentemente complejo para ver si tal hazaña es posible. ¡Sigue mirando!

Primero, repasemos rápidamente lo que sabemos sobre las rutas y circuitos de Euler. Una ruta de Euler es una ruta en un gráfico donde cada borde se cruza exactamente una vez. Un camino de Euler puede tener cualquier punto de inicio con un punto final diferente. Un gráfico con una trayectoria de Euler puede tener cero o dos vértices impares. El resto debe ser parejo.

Un circuito de Euler es un circuito en un gráfico donde cada borde se cruza exactamente una vez. Los puntos de inicio y final son los mismos. Todos los vértices deben ser pares para que la gráfica tenga un circuito de Euler. Sigamos con los problemas ahora.

Entrega del correo

Nuestro primer problema tiene que ver con la entrega del correo. Imagínese a nuestro cartero con una pila de correo en la mano. Necesita entregar este correo a direcciones en cinco calles diferentes. Mira en el mapa y ve cómo las carreteras se conectan entre sí. Dibuja una versión simplificada del mapa. Marca cada intersección con un número. Como tiene coche, le gustaría terminar en el mismo punto donde empezó.

Para aprovechar al máximo su tiempo, debe recorrer cada camino una sola vez. ¿Puede hacerlo y, de ser así, cómo?

Mirando su gráfico, vemos que sí, es posible recorrer cada camino una sola vez. Puede estacionar su automóvil en la intersección uno, caminar hasta la intersección dos, luego tres, luego cuatro, luego cinco y luego regresar a la uno. Al hacer esto, habrá recorrido cada camino solo una vez. Desde que terminó donde comenzó, en realidad caminó por un circuito de Euler.

¿Hay otras formas en que podría haber hecho un circuito de Euler? Si. En realidad, hay diez circuitos de Euler diferentes que podría haber tomado. Pudo haber comenzado en el punto uno, ir al punto cinco, luego cuatro, tres, dos y luego volver al punto uno nuevamente. De hecho, puede comenzar en cualquiera de los puntos e ir en cualquier dirección. Tenemos cinco puntos y dos caminos por recorrer desde cada punto. Esto hace un total de diez posibles rutas que podría haber tomado; diez posibles circuitos de Euler.

El vendedor ambulante

Ahora, veamos el problema del viajante. El suyo es similar al del cartero. Dado que nuestro vendedor viaja, no le importa terminar en un punto diferente de donde comenzó. Pero al igual que el cartero, quiere aprovechar al máximo su tiempo y recorrer cada camino una sola vez. Este vendedor hizo lo que hizo el cartero y dibujó una versión simplificada de las carreteras que quiere recorrer.

También tiene cinco caminos para llegar. ¿Puede atravesar los cinco caminos solo una vez? Si, el puede. Si comienza en el punto tres, puede ir al punto dos, uno, cinco, cuatro y luego uno nuevamente. Habrá visitado las cinco carreteras solo una vez. Desde que terminó en un lugar diferente de donde comenzó, ha recorrido un camino de Euler. ¿Hay más caminos de Euler que nuestro vendedor podría haber tomado? Sí hay. ¿Puedes verlos?

Los siete puentes de Konigsberg

Este último ejemplo es complicado. En realidad, este fue un problema que se le planteó al matemático Leonhard Euler en el siglo XVIII. ¿Reconoces el nombre? Sí, este problema resuelto por el matemático Leonhard Euler es donde comenzó nuestro estudio de la teoría de grafos. Por lo tanto, tenemos el nombre de caminos de Euler y los circuitos de Euler llevan el nombre de este matemático. ¿Estás listo para este problema? Bueno. Aquí está.

Mapa de Konigsberg

Aquí tenemos un mapa de Konigsberg y sus siete puentes en el siglo XVIII. El problema que se le planteó a Euler fue el de poder visitar todos los puentes pero cruzar cada puente una sola vez. Sí, estamos buscando un camino de Euler o un circuito de Euler. ¿Cómo podemos solucionar este problema? Podemos comenzar haciendo un gráfico simplificado de nuestros puentes. Marcaremos cada área de tierra como un punto.

Tenemos cuatro áreas terrestres principales, por lo que terminamos con cuatro puntos. Hemos dibujado los puentes como líneas que conectan estos puntos. Ahora, la pregunta es ¿podemos pasar todas estas líneas una sola vez sin saltarnos? Bueno, analicemos nuestro gráfico por un minuto. Vemos que cada vértice de nuestra gráfica es realmente impar. El punto de la izquierda tiene cinco líneas que salen de él, mientras que el resto tiene tres. ¿Qué sabemos sobre los vértices de gráficos con trayectorias y circuitos de Euler en ellos? Recuerde que un gráfico con una trayectoria de Euler puede tener como máximo dos vértices impares, mientras que un gráfico con un circuito de Euler no debe tener ninguno. Dado que tenemos cuatro vértices impares en nuestro gráfico, esto significa que no hay solución a nuestro problema, ya que el número de vértices impares excede el permisible para cualquiera de los gráficos.

Resumen de la lección

Repasemos lo que hemos aprendido ahora. Una ruta de Euler es una ruta en un gráfico donde cada borde se cruza exactamente una vez. Un camino de Euler puede tener cualquier punto de inicio con un punto final diferente. Un gráfico con una trayectoria de Euler puede tener cero o dos vértices impares. El resto debe ser parejo.

Un circuito de Euler es un circuito en un gráfico donde cada borde se cruza exactamente una vez. Los puntos de inicio y final son los mismos. Todos los vértices deben ser pares para que la gráfica tenga un circuito de Euler.

Los carteros y vendedores utilizan los caminos y los circuitos de Euler en el mundo real cuando planean las mejores rutas a seguir. Puede haber varias rutas que pueden tomar dado un gráfico de las carreteras por las que deben pasar.

Los resultados del aprendizaje

Después de esta lección, debería poder:

• Describe la trayectoria de Euler y el circuito de Euler.
• Identifique el número requerido de vértices pares versus impares en cada
• Explicar los usos en el mundo real de las rutas y circuitos de Euler.

Rodrigo Ricardo Editor y fundador