6.3: Circuitos de Euler

Leonhard Euler discutió y utilizó por primera vez los caminos y circuitos de Euler en 1736. En lugar de encontrar un árbol de expansión mínimo que visite cada vértice de una gráfica, se puede usar una ruta o circuito de Euler para encontrar la manera de visitar cada borde de una gráfica una y solo una vez. Esto sería útil para verificar los parquímetros a lo largo de las calles de una ciudad, patrullar las calles de una ciudad o entregar correo.

Definición: Euler Path

Un camino que recorre cada borde de una gráfica conectada una y solo una vez y comienza y termina en diferentes vértices

Ejemplo\(\PageIndex{1}\): Euler Path

Figura\(\PageIndex{1}\): Ejemplo de ruta de Euler

Una ruta de Euler para la gráfica anterior es F, A, B, C, F, E, C, D, E como se muestra a continuación.

Figura\(\PageIndex{2}\): Sendero de Euler

Este camino de Euler recorre cada borde una vez y solo una vez y comienza y termina en diferentes vértices. Esta gráfica no puede tener un circuito de Euler ya que ningún camino de Euler puede comenzar y terminar en el mismo vértice sin cruzar al menos un borde más de una vez.

Definición: Circuito de Euler

Un camino de Euler que comienza y termina en el mismo vértice

Ejemplo\(\PageIndex{2}\): Euler Circuit

Figura\(\PageIndex{3}\): Ejemplo de circuito de Euler

Un circuito de Euler para la gráfica anterior es E, A, B, F, E, F, D, C, E como se muestra a continuación.

Figura\(\PageIndex{4}\): Circuito de Euler

Este camino de Euler recorre cada borde una vez y solo una vez y comienza y termina en el mismo vértice. Por lo tanto, también es un circuito de Euler.

Teorema de Euler\(\PageIndex{1}\): If a graph has any vertices of odd degree, then it cannot have an Euler circuit.

Si se conecta una gráfica y cada vértice tiene un grado par, entonces tiene al menos un circuito de Euler (generalmente más).

Teorema de Euler\(\PageIndex{2}\): If a graph has more than two vertices of odd degree, then it cannot have an Euler path.

Si una gráfica está conectada y tiene exactamente dos vértices de grado impar, entonces tiene al menos una ruta de Euler (generalmente más). Cualquier camino de este tipo debe comenzar en uno de los vértices de grado impar y terminar en el otro.

Teorema de Euler\(\PageIndex{3}\): The sum of the degrees of all the vertices of a graph equals twice the number of edges (and therefore must be an even number).

Por lo tanto, el número de vértices de grado impar debe ser par.

Encontrar circuitos de Euler

1. Asegúrese de que cada vértice de la red tenga grado par.
2. Comienza el circuito de Euler en cualquier vértice de la red.
3. Al elegir bordes, nunca use un edge que sea la única conexión a una parte de la red que aún no haya visitado.
4. Etiquete los bordes en el orden en que los recorra y continúe con esto hasta que haya viajado por cada borde exactamente una vez y termine en el vértice inicial.

Ejemplo\(\PageIndex{3}\): Finding an Euler Circuit

Figura\(\PageIndex{5}\): Gráfica para encontrar un circuito de Euler

La gráfica que se muestra arriba tiene un circuito de Euler ya que cada vértice en toda la gráfica es grado par. Así, comenzar en un vértice par, recorrer cada vértice una vez y sólo una vez, y terminar en el punto de partida. Un ejemplo de un circuito de Euler para esta gráfica es A, E, A, B, C, B, E, C, D, E, F, D, F, A. Este es un circuito que recorre cada borde una vez y sólo una vez y comienza y termina en el mismo lugar. Hay otros circuitos de Euler para esta gráfica. Este es sólo un ejemplo.

Figura\(\PageIndex{6}\): Circuito de Euler

El grado de cada vértice está etiquetado en rojo. El orden de los bordes del circuito se etiqueta en azul y la dirección del circuito se muestra con las flechas azules.