Teoremas de Euler: circuito, trayectoria y suma de grados

Un gráfico

En esta lección en video, repasaremos tres de los teoremas de Euler relacionados con la teoría de grafos. ¿Por qué son estos importantes? Estos son importantes porque te ayudan a analizar gráficos como este:

¿Por qué son importantes estas gráficas? Si nuestro gráfico representa un vecindario donde los puntos son intersecciones y las líneas son las carreteras, entonces la teoría de gráficos puede ayudarnos a encontrar la mejor manera de desplazarnos por la ciudad. Por ejemplo, la teoría de grafos puede ayudar al cartero a entregar su correo para que no tenga que dar marcha atrás o pasar por el mismo camino dos veces. Los teoremas de Euler son útiles porque le dicen al cartero si es posible una ruta eficiente con solo mirar el gráfico. ¿Como funciona esto? Echemos un vistazo a los teoremas de Euler y veremos.

Teorema del circuito de Euler

El primer teorema que veremos se llama teorema del circuito de Euler . Este teorema establece lo siguiente: ‘Si todos los vértices de un gráfico son pares, entonces el gráfico tiene un circuito de Euler. De lo contrario, no tiene un circuito de Euler ”. ¿Qué significa esto para nuestro cartero? Recuerde que un circuito de Euler es una ruta en la que puede pasar por cada borde o línea en el gráfico exactamente una vez y terminar donde comenzó. Esto ayuda al cartero a determinar si hay una ruta que pueda tomar, donde termina donde comenzó y por donde pasa por cada camino solo una vez. Si tal ruta no existe en primer lugar, entonces no tiene sentido que él siquiera intente encontrar una. Nuestros vértices son de grado par si hay un número par de aristas que lo conectan con otros vértices.

Si todos los vértices tienen un grado par, la gráfica tiene un circuito de Euler

Mirando nuestro gráfico, vemos que todos nuestros vértices son de un grado par. El vértice inferior tiene un grado de 2. Todos los demás tienen un grado de 4. Esto significa que la gráfica tiene un circuito de Euler. Esto le dice al cartero que, sí, existe una ruta en la que no tiene que retroceder. Ahora puede ir descubriendo esa ruta.

Teorema de la trayectoria de Euler

Este siguiente teorema es muy similar. El teorema de la trayectoria de Euler establece lo siguiente: «Si una gráfica tiene exactamente dos vértices de grado impar, entonces tiene una trayectoria de Euler que comienza y termina en los vértices de grados impares. De lo contrario, no tiene un camino de Euler ‘. Recuerde que un camino de Euler es un camino en el que pasa por cada borde o línea en el gráfico exactamente una vez y termina en un lugar diferente al que comenzó. Un camino es muy similar a un circuito, con la única diferencia de que terminas en otro lugar en lugar de donde comenzaste. Un camino de Euler es bueno para un vendedor ambulante o para otra persona que no necesita terminar donde comenzó. Mirando nuestro gráfico, vemos que no tenemos vértices que sean impares. Esto nos dice que este gráfico no tiene una ruta de Euler.

Teorema de la suma de grados de Euler

El siguiente teorema es general y funciona para todos los gráficos. El teorema de la suma de grados de Euler nos dice que «la suma de los grados de los vértices en cualquier gráfico es igual al doble del número de aristas». Esto significa que si tenemos 3 aristas, obtendremos 6 después de sumar los grados de cada vértice. Miremos nuestro gráfico y veamos si este teorema es cierto. Esperamos que el número total de grados de nuestros vértices sume el doble del número de aristas en nuestro gráfico. Veamos cómo. Primero, contemos los bordes. Tenemos 11 aristas. Esto significa que deberíamos esperar que el número total de grados sume 22. Veamos si es así. El vértice inferior tiene un grado de 2. El resto tiene un grado de 4. Entonces, tenemos 2 + 4 + 4 + 4 + 4 + 4 = 22. Oye, mira eso; tenemos 22! ¡Como dice el teorema! Funciona. ¿Por qué es útil este teorema? Este teorema le permite saber si el gráfico que está viendo es legítimo o no.

Resumen de la lección

Repasemos lo que hemos aprendido. Aprendimos que el teorema del circuito de Euler establece esto: ‘Si los vértices de un gráfico son todos pares, entonces el gráfico tiene un circuito de Euler. De lo contrario, no tiene un circuito de Euler ‘. El teorema de la trayectoria de Euler establece lo siguiente: «Si una gráfica tiene exactamente dos vértices de grado impar, entonces tiene una trayectoria de Euler que comienza y termina en los vértices de grados impares. De lo contrario, no tiene un camino de Euler ‘. El teorema de la suma de grados de Euler nos dice que «la suma de los grados de los vértices en cualquier gráfico es igual al doble del número de aristas». Estos teoremas son útiles para analizar gráficos en teoría de grafos. Los teoremas del circuito y la trayectoria de Euler nos dicen si vale la pena buscar una ruta eficiente que nos lleve más allá de todas las aristas de un gráfico. Esto es útil para los carteros y otras personas que necesitan encontrar una ruta más eficiente.

Los resultados del aprendizaje

Una vez que haya terminado con esta lección, podrá:

• Enuncia tres de los teoremas de Euler
• Determinar si una gráfica tiene un circuito de Euler
• Definir el camino de Euler
• Recuerde por qué los teoremas de Euler podrían ser útiles en la vida real

Rodrigo Ricardo Editor y fundador