Caminos y Ciclos Eulerianos y Hamiltonianos

Created in January 02, 2023 by Alan Yahir Juárez Rubio , last updated in June 04, 2024

2023   ·   grafo   grafo_no_dirigido   camino   ciclo   camino   euler   hamilton   ·   matematicas   matematicas-discretas   grafos

Camino Euleriano

Un camino euleriano es aquel camino o recorrido que puedes realizar sin repetir las aristas y pasando por todos las aristas.

Para saber si un camino es euleriano, se tiene que analizar los grados de cada uno de los nodos de dicho grafo.

Cómo saber si existe un camino euleriano

Para identificar si existe en un grafo existe un camino euleriano tenemos que:

  • Si un grafo tiene un solo un nodo con grado non, para hacer el camino euleriano tenemos que empezar y terminar en dicho nodo con grado impar.

  • Si tienes dos vértices con grado non, tienes que iniciar en uno de los dichos nodos y terminar en el otro para descubrir el camino euleriano.

Ciclo Euleriano

Un ciclo euleriano al igual que el camino euleriano busca recorrer todos los nodos sin repetir aristas, la diferencia es que el ciclo busca que el recorrido termine en el mismo punto de partida.

Para saber si existe un ciclo euleriano, tenemos que analizar los nodos de un grafo. Si dicho grafo no tiene nodos impares, entonces existe un ciclo euleriano.

Algoritmo de Fleury

El algoritmo de Fleury va a encontrar un ciclo euleriano. Los pasos del algoritmo de Fleury son:

  1. Verificar que el grado de todos los nodos es par. Si no lo son, no es un ciclo euleriano.
  2. Realizar un circuito cerrado, sin importar que no se encluyan todos los nodos.
  3. En cada nueva iteración realizar un nuevo camino cerrado visitando aristas que no han sido visitadas.
  4. Reemplazar cada nuevo circuito en el inicial hasta visitar todas las aristas.
Algoritmo de Fleury
Fig. 1: Algorimto de Fleury
CONSEJO

Un ciclo euleriano se ha hecho correctamente si el número de veces que el nodo aparece en el ciclo euleriano es la mitad del grado que tiene en el grafo.

Caminos Hamiltoniano

Un camino hamiltoniano es aquel en el que visitas a todas los vértices sin repetir aristas.

Para afirmar que hay un camino hamiltoniano se debe cumplir la condición donde la suma del grado de los dos grados más pequeños de los vertices es mayor o igual al número de vértices menos uno:

\[\text{Grado}\left(u\right)+\text{Grado}\left(v\right)\geq n-1\]

donde $n$ es el número de vértices del grafo.

NOTA

Si un grafo no cumple con esta condición, no significa que no sea hamiltoniano, sino que simplemente no se puede asegurar que sea un camino hamiltoniano

Ciclo Hamiltoniano

El ciclo hamiltoniano al igual que el camino hamiltoniano, busca visitar todos los nodos sin repetir aristas. Adicionalmente, el ciclo hamiltoniano busca finalizar en el punto de partida.

Grafos Hamiltoniano

Los grafos hamiltonianos son todos aquellos que no poseen un ciclo hamiltoniano.

Si en un grafo uno de los nodos tiene grado uno, entonces no existe camino hamiltoniano y, por ende, no es un grafo hamiltoniano.

Referencias



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • Introducción a los Comandos
  • Interfaces de Usuario en los Sistemas Operativos
  • Introducción a Linux
  • Introducción a los Sistemas Operativos
  • Vim CheatSet
  • Sistemas Numéricos