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.
Propiedades de los grafo eulerianos:
- Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
- Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
- Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
- Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
- Un grafo no dirigido se dice que es susceptible de ser recorrido si es conexo y dos vértices en el grafo tienen grado impar.
El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:
Dado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, G tiene un ciclo euleriano.
Un camino hamiltoniano es un camino de un grafo que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.
Ejempos de grafos Hamiltonianos:
- Todos los grafos ciclos son hamiltonianos.
- Todos los sólidos platónicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos
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ólo si los vértices de los extremos son adyacentes.
Un resultado que puede ayudarnos a distinguirlos es el siguiente:
Un grafo con n vértices (n > 3) es hamiltoniano si cada vértice tiene grado mayor o igual a n/2.
$\quad$
| Ejercicio: Estudiar si el grafo representado por la matriz [0,1,0,1,0,0; 1,0,1,0,0,0; 0,1,0,1,1,1; 1,0,1,0,1,1;0,0,1,1,0,0; 0,0,1,1,0,0] tiene un camino o ciclo eureliano y/o hamiltoniano. |