4.4: Caminos y circuitos de Euler
- Page ID
- 115789
¡Investiga!
Un camino de Euler, en una gráfica o multígrafo, es un recorrido por el gráfico que usa cada borde exactamente una vez. Un circuito de Euler es un camino de Euler que comienza y se detiene en el mismo vértice. Nuestro objetivo es encontrar una manera rápida de verificar si una gráfica (o multígrafo) tiene una ruta o circuito de Euler.
- ¿Cuál de las siguientes gráficas tiene caminos de Euler? ¿Cuáles tienen circuitos de Euler?
- Enumere los grados de cada vértice de las gráficas anteriores. ¿Existe una conexión entre grados y la existencia de caminos y circuitos de Euler?
- ¿Es posible que una gráfica con un vértice de grado 1 tenga un circuito de Euler? Si es así, dibuja uno. Si no, explica por qué no. ¿Y un camino de Euler?
- Y si cada vértice de la gráfica tiene grado 2. ¿Hay un camino de Euler? ¿Un circuito de Euler? Dibuja algunas gráficas.
- A continuación se muestra parte de una gráfica. A pesar de que sólo se pueden ver algunos de los vértices, ¿se puede deducir si la gráfica tendrá una trayectoria o circuito de Euler?
Si empezamos en un vértice y trazamos a lo largo de los bordes para llegar a otros vértices, creamos un recorrido por la gráfica. Más precisamente, un paseo en una gráfica es una secuencia de vértices tal que cada vértice de la secuencia es adyacente a los vértices antes y después de él en la secuencia. Si la caminata recorre cada borde exactamente una vez, entonces la caminata se llama sendero de Euler (o caminata de Euler). Si, además, los vértices inicial y final son los mismos (por lo que trazas a lo largo de cada borde exactamente una vez y terminas donde empezaste), entonces la caminata se llama circuito de Euler (o recorrido de Euler). Por supuesto que si una gráfica no está conectada, no hay esperanza de encontrar tal camino o circuito. Para el resto de esta sección, supongamos que todas las gráficas discutidas están conectadas.
El problema de los puentes de Königsberg es realmente una cuestión sobre la existencia de caminos de Euler. Habrá una ruta que cruza cada puente exactamente una vez si y solo si la gráfica de abajo tiene un camino de Euler:
Esta gráfica es lo suficientemente pequeña como para que podamos verificar cada caminata posible que no reutilice bordes, y al hacerlo convencernos de que no hay camino de Euler (y mucho menos un circuito de Euler). En pequeñas gráficas que sí tienen un camino de Euler, no suele ser difícil encontrar uno. Nuestro objetivo es encontrar una manera rápida de comprobar si una gráfica tiene una trayectoria o circuito de Euler, aunque la gráfica sea bastante grande.
Una forma de garantizar que una gráfica no tenga un circuito de Euler es incluir un “pico”, un vértice de grado 1.
El vértice\(a\) tiene grado 1, y si intentas hacer un circuito de Euler, ves que te quedarás atascado en el vértice. Es un callejón sin salida. Es decir, a menos que empieces ahí. Pero entonces no hay manera de regresar, así que no hay esperanza de encontrar un circuito de Euler. Sin embargo, hay un camino de Euler. Comienza en el vértice\(a\text{,}\) y luego gira alrededor del triángulo. Terminarás en el vértice del grado 3.
Te encuentras con un problema similar cada vez que tienes un vértice de cualquier grado impar. Si comienzas en tal vértice, no podrás terminar ahí (después de atravesar cada borde exactamente una vez). Después de usar un borde para dejar el vértice inicial, te quedarás con un número par de bordes que emanan del vértice. La mitad de estos podrían usarse para regresar al vértice, la otra mitad para irse. Entonces regresas, luego te vas. Regresa, luego vete. La única forma de usar todos los bordes es usar el último dejando el vértice. Por otro lado, si tienes un vértice con grado impar en el que no comienzas un camino, entonces eventualmente te quedarás atascado en ese vértice. El camino utilizará pares de aristas incidentes al vértice para llegar y salir de nuevo. Eventualmente todos menos uno de estos bordes se agotarán, dejando solo un borde para llegar, y ninguno para volver a salir.
Lo que todo esto dice es que si una gráfica tiene una trayectoria de Euler y dos vértices con grado impar, entonces la trayectoria de Euler debe comenzar en uno de los vértices de grado impar y terminar en el otro. En tal situación, cada otro vértice debe tener un grado par ya que necesitamos un número igual de aristas para llegar a esos vértices como para dejarlos. ¿Cómo podríamos tener un circuito de Euler? La gráfica no podría tener ningún vértice de grado impar ya que un camino de Euler tendría que comenzar ahí o terminar ahí, pero no ambos. Así, para que una gráfica tenga un circuito de Euler, todos los vértices deben tener grado par.
Lo contrario también es cierto: si todos los vértices de una gráfica tienen grado par, entonces la gráfica tiene un circuito de Euler, y si hay exactamente dos vértices con grado impar, la gráfica tiene una trayectoria de Euler. Demostrar esto es un poco complicado, pero la idea básica es que nunca te quedarás atascado porque hay un borde “saliente” por cada borde “entrante” en cada vértice. Si intentas hacer un camino de Euler y pierdes algunos bordes, siempre podrás “empalmar” un circuito usando los bordes que antes te perdiste.
Rutas y Circuitos de Euler
- Una gráfica tiene un circuito de Euler si y sólo si el grado de cada vértice es par.
- Una gráfica tiene una trayectoria de Euler si y sólo si hay como máximo dos vértices con grado impar.
Dado que los puentes de Königsberg grafo tiene los cuatro vértices con grado impar, no hay trayectoria de Euler a través de la gráfica. Por lo tanto, no hay manera de que la gente del pueblo cruce cada puente exactamente una vez.
Caminos de Hamilton
Supongamos que quería recorrer Königsberg de tal manera donde visite cada masa terrestre (las dos islas y ambas orillas) exactamente una vez. Esto se puede hacer. En términos de teoría gráfica, nos preguntamos si hay un camino que visita cada vértice exactamente una vez. Tal camino se llama camino de Hamilton (o camino hamiltoniano). También podríamos considerar los ciclos Hamilton, que son caminos Hamliton que comienzan y se detienen en el mismo vértice.
Ejemplo\(\PageIndex{1}\)
Determine si las gráficas a continuación tienen un camino Hamilton.
- Solución
-
La gráfica de la izquierda tiene un camino Hamilton (muchos diferentes, en realidad), como se muestra aquí:
La gráfica de la derecha no tiene un camino Hamilton. Tendrías que visitar cada uno de los vértices “exteriores”, pero en cuanto visites uno, te quedas atascado. Tenga en cuenta que esta gráfica no tiene un camino de Euler, aunque hay gráficas con caminos de Euler pero no con caminos de Hamilton.
Parece que encontrar caminos Hamilton sería más fácil porque las gráficas suelen tener más aristas que vértices, por lo que hay menos requisitos por cumplir. No obstante, nadie sabe si esto es cierto. No se conoce una prueba simple para saber si una gráfica tiene un camino Hamilton. Para las gráficas pequeñas esto no es un problema, pero a medida que crece el tamaño de la gráfica, se vuelve cada vez más difícil verificar que haya un camino de Hamilton. De hecho, este es un ejemplo de una pregunta que hasta donde sabemos es demasiado difícil de resolver para las computadoras; es un ejemplo de un problema que es NP-completo.