Caminos Hamiltonianos y Ciclos Hamiltonianos 😀

Descubre QUE SON los CAMINOS HAMILTONIANOS y CICLOS HAMILTONIANOS. Y las fórmulas que existen para saber si un camino o ciclo es hamiltoniano.

0:00 Que es un camino hamiltoniano
0:26 Ejemplo de camino hamiltoniano
1:20 Definición formal de camino hamiltoniano
1:40 Condición suficiente para saber si el grafo admite camino hamiltoniano
4:34 Ejemplo de ciclo hamiltoniano
5:26 Definición formal de ciclo hamiltoniano
6:22 Condición suficiente para saber si el grafo admite camino hamiltoniano

Un camino hamiltoniano es aquel que a diferencia del euleriano se visitan todos los vértices del grafo sin repetir ninguno.

Un ciclo hamiltoniano es aquel camino que empieza en el mismo vértice donde termina sin repetir ninguno en el camino.

Al contrario que con la teoría euleriana no existen condiciones necesarias y suficientes para saber si un grafo admite camino o ciclo hamiltoniano, pero sí existe el teorema de L. Redei que nos dice que si se cumple que para todo vértice u y v del grafo:

grado(u) + grado(v) mayor o igual a n-1

entonces si existe un camino hamiltoniano.

donde el grado son el número de aristas que tiene el vértice

y para el ciclo las condiciones son similares y si se cumplen para toda pareja de vértices u y v:

grado(u) + grado(v) mayor o igual a n

entonces si existe un ciclo hamiltoniano y podemos considerar que es un grafo hamiltoniano.