4.3.6. Otros problemas con grafos.
Condiciones necesarias para que exista un circuito de Euler:
- El grafo debe ser conexo.
- Todos los nodos deben tener grado (número de aristas) par, ya que el camino entra y sale de los nodos.
Estas condiciones necesarias son también suficientes, si se cumplen entonces existe un circuito de Euler. ¿Cómo encontrarlo?
Algoritmo para encontrar un circuito de Euler en un grafo G, partiendo de un nodo v.
1. Buscar un ciclo en G empezando por v (por ejemplo con una búsqueda en profundidad). Puede que no todas las aristas hayan sido visitadas.
2. Si quedan aristas por visitar, seleccionar el primer nodo w del ciclo anterior que tenga una arista sin visitar. Buscar un ciclo partiendo de w que pase por aristas no visitadas.
3. Unir el ciclo del paso 1 con el obtenido en el paso 2. Repetir sucesivamente los pasos 2 y 3 hasta que no queden aristas por visitar.
Ejemplo. Paso 1. Ciclo: (1, 2, 5, 7, 6, 3, 1) Paso 2. Ciclo: (2, 3, 4, 2)
Paso 3. Ciclo: (1, 2, 3, 4, 2, 5, 7, 6, 3, 1) Paso 2. Ciclo: (4, 5, 6, 4)
Paso 3. Ciclo: (1, 2, 3, 4, 5, 6, 4, 2, 5, 7, 6, 3, 1) FIN