6.4: Circuitos de Euler y el problema del cartero chino

Última actualización
Guardar como PDF

Page ID: 110620

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

En la primera sección, creamos una gráfica de los puentes Königsberg y preguntamos si era posible cruzar cada puente una vez. Debido a que Euler estudió por primera vez esta cuestión, este tipo de caminos llevan su nombre.

Sendero de Euler

Un camino de Euler es un camino que utiliza cada borde en una gráfica sin repeticiones. Al ser un camino, no tiene que volver al vértice inicial.

Ejemplo 5

En la gráfica que se muestra a continuación, hay varios caminos de Euler.

$gt20.svg$

Solución

Uno de esos caminos es CABDCB. El camino se muestra con flechas a la derecha, con el orden de aristas numeradas.

$gt21.svg$

Circuito de Euler

Un circuito de Euler es un circuito que utiliza cada borde en una gráfica sin repeticiones. Al ser un circuito, debe comenzar y terminar en el mismo vértice.

Ejemplo 6

La gráfica a continuación tiene varios circuitos posibles de Euler.

$gt22.svg$

Solución

Aquí hay una pareja, comenzando y terminando en el vértice A: ADEACEFCBA y AECABCFEDA. El segundo se muestra en flechas.

$gt23.svg$

Mira hacia atrás en el ejemplo usado para caminos de Euler — ¿esa gráfica tiene un circuito de Euler? Algunos intentos te dirán que no; esa gráfica no tiene un circuito de Euler. Cuando estábamos trabajando con los caminos más cortos, nos interesaba el camino óptimo. Con caminos y circuitos de Euler, nos interesa principalmente si existe una ruta o circuito de Euler.

¿Por qué nos importa si existe un circuito de Euler? Piense en nuestro inspector de césped de desarrollo habitacional desde el comienzo del capítulo. El inspector de césped está interesado en caminar lo menos posible. La situación ideal sería un circuito que cubra todas las calles sin repeticiones. ¡Eso es un circuito de Euler! Por suerte, Euler resolvió la cuestión de si existirá o no un camino o circuito de Euler.

Teoremas de Ruta y Circuito de Euler

Una gráfica contendrá una ruta de Euler si contiene como máximo dos vértices de grado impar.

Una gráfica contendrá un circuito de Euler si todos los vértices tienen grado par

Ejemplo 7

En la gráfica siguiente, los vértices A y C tienen grado 4, ya que hay 4 aristas que conducen a cada vértice. B es grado 2, D es grado 3 y E es grado 1. Esta gráfica contiene dos vértices con grado impar (D y E) y tres vértices con grado par (A, B y C), por lo que los teoremas de Euler nos dicen que esta gráfica tiene una trayectoria de Euler, pero no un circuito de Euler.

$gt24.svg$

Ejemplo 8

¿Hay un circuito de Euler en la gráfica de inspector de césped de desarrollo habitacional que creamos anteriormente en el capítulo? Todos los vértices resaltados tienen grado impar. Dado que hay más de dos vértices con grado impar, no hay caminos de Euler ni circuitos de Euler en esta gráfica. Desafortunadamente nuestro inspector de césped necesitará hacer algunos retrocesos.

$gt25.svg$ $gt26.svg$

Ejemplo 9

Cuando nieva en el mismo desarrollo habitacional, el quitanieves tiene que arar ambos lados de cada calle. Por simplicidad, asumiremos que el arado está fuera lo suficientemente temprano como para que pueda ignorar las leyes de tránsito y conducir por ambos lados de la calle en cualquier dirección. Esto se puede visualizar en la gráfica dibujando dos aristas para cada calle, representando los dos lados de la calle.

$gt27.svg$

Observe que cada vértice en esta gráfica tiene grado par, por lo que esta gráfica sí tiene un circuito de Euler.

Ahora sabemos cómo determinar si una gráfica tiene un circuito de Euler, pero si lo hace, ¿cómo encontramos uno? Si bien suele ser posible encontrar un circuito de Euler simplemente sacando el lápiz y tratando de encontrar uno, el método más formal es el algoritmo de Fleury.

Algoritmo de Fleury

Comience en cualquier vértice si encuentra un circuito de Euler. Si encuentra una ruta de Euler, comience en uno de los dos vértices con grado impar.
Elija cualquier borde que deje su vértice actual, siempre que al eliminar ese borde no se separe la gráfica en dos conjuntos de bordes desconectados.
Agrega ese borde a tu circuito y elimírelo de la gráfica.
Continúa hasta que termines.

Ejemplo 10

Encontremos un Circuito de Euler en esta gráfica usando el algoritmo de Fleury, comenzando en el vértice A.

Solución

Paso 1:

Gráfica Original. Elegir borde AD.

$gt28.svg$

Circuito hasta el momento: AD

Paso 2:

AD eliminado. D es actual. No se puede elegir DC ya que eso desconectaría el gráfico. Elegir DE

$gt29.svg$

Circuito hasta el momento: ADE

Paso 3:

E es actual. A partir de aquí, sólo hay una opción, por lo que se determina el resto del circuito.

$gt30.svg$

Circuito: ADEBDCA

Pruébalo ahora 3

¿La siguiente gráfica tiene un Circuito de Euler? Si es así, encuentra uno.

$gt31.svg$

Contestar: Sí, todos los vértices tienen grado par por lo que esta gráfica tiene un Circuito de Euler. Hay varias posibilidades. Uno es: ABEGFCDFEDBCA