Caminos Eulerianos:
Un multígrafo conexo contiene un camino euleriano, si solo si tiene exactamente dos vértices de grado impar, como se muestra a continuación:
Ejemplo: b, a, g, c, f, e, d, c, b, g, f, d
En pocas palabras un camino de Euler es el que recorre todos los vértices pasando por todos los arcos (aristas) una sola vez.
Caminos Hamiltonianos:
Son los grafos donde se recorren las aristas sin repetir los vértices del grafo que se esta analizando.
En este ejemplo el camino seria:
c, d, e, b, a
Referencias:
trayectorias-y-circuitos-eulerianos-y-hamiltonianos.pdf (wordpress.com)
Arboleda M. O. (2008) Circuitos de Euler y Hamilton
No hay comentarios:
Publicar un comentario