Solución:
Un Camino de Euler es un camino que atraviesa cada borde exactamente una vez. Si termina en el vértice inicial, entonces es un Ciclo de Euler.
A Camino hamiltoniano es una ruta que atraviesa cada vértice exactamente una vez (NO cada borde). Si termina en el vértice inicial, entonces es un Ciclo hamiltoniano.
En un camino de Euler, puede pasar por un vértice más de una vez.
En un camino hamiltoniano es posible que no pase por todos los bordes.
Definiciones de la teoría de grafos
(En orden descendente de generalidad)
-
Andar: una secuencia de bordes donde el final de un borde marca el comienzo del siguiente borde
-
Sendero: un paseo que no repite ningún borde. Todos los senderos son paseos.
-
Sendero: un paseo en el que cada vértice se atraviesa como máximo una vez. (caminos utilizados para referirse a paseos abiertos, la definición ha cambiado ahora) La propiedad de atravesar vértices como máximo una vez significa que los bordes también se cruzan como máximo una vez, por lo tanto, todos los caminos son senderos.
Caminos hamiltonianos y senderos eulerianos
-
Camino hamiltoniano: visitas cada vértice del gráfico (exactamente una vez, porque es un camino)
-
Sendero euleriano: visitas cada borde en el gráfico exactamente una vez (debido a que es un sendero, los vértices pueden cruzarse más de una vez).
El camino euleriano debe visitar cada borde exactamente una vez, mientras que el camino hamiltoniano debe visitar cada vértice Exactamente una vez.