Caminos Eulerianos y Ciclos Eulerianos ¿QUÉ SON? 😀

Descubre QUE SON LOS CAMINOS EULERIANOS y CICLOS EULERIANOS con 2 ejemplos.

0:00 Intro
0:36 Ejemplo camino euleriano
3:06 Condición necesaria y suficiente para un camino euleriano
5:12 Ejemplo de ciclo euleriano
6:55 Condición necesaria y suficiente para un camino euleriano
8:02 Puentes de Konigsberg

Un camino euleriano es aquel camino donde se visitan todas las aristas de un grafo sin repetir ninguna. Aunque por esta definición se puede deducir que si se pueden repetir vértices en el camino.

Sabemos que un grafo admite un camino euleriano si y sólo si existen 2 y solo 2 vértices de grado impar.

Un ciclo euleriano a diferencia de un camino es aquel camino que empieza en el mismo vértice donde termina sin repetir ninguna arista.

Sabemos que un grafo admite un ciclo euleriano si y sólo si todos los vértices son de grado par.

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.

Por último doy una breve introducción sobre los puentes de Könisgsberg.