Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. Un grafo se denomina grafo euleriano si un circuito euleriano.<\/p>\n
Propiedades de los grafo eulerianos:<\/p>\n
El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:<\/p>\n
\nDado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos v\u00e9rtices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los v\u00e9rtices tengan grado par, G tiene un ciclo euleriano.<\/p>\n<\/blockquote>\n
Un camino hamiltoniano es un camino de un grafo que visita todos los v\u00e9rtices del grafo una sola vez. Si adem\u00e1s el \u00faltimo v\u00e9rtice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.<\/p>\n
Ejempos de grafos Hamiltonianos:<\/p>\n
\n
- Todos los grafos ciclos son hamiltonianos.<\/li>\n
- Todos los s\u00f3lidos plat\u00f3nicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos<\/li>\n<\/ul>\n
Hay que tener en cuenta que cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se elimina cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo s\u00f3lo si los v\u00e9rtices de los extremos son adyacentes.<\/p>\n
Un resultado que puede ayudarnos a distinguirlos es el siguiente:<\/p>\n
\nUn grafo con n v\u00e9rtices (n > 3) es hamiltoniano si cada v\u00e9rtice tiene grado mayor o igual a n\/2.<\/p>\n<\/blockquote>\n
$\\quad$ <\/p>\n