Un recorrido euleriano utiliza cada arista exactamente una vez. La existencia de un camino o circuito de este tipo puede decidirse mediante conectividad y paridad de grados.
Los recorridos eulerianos surgieron del problema de los siete puentes de Königsberg: ¿es posible cruzar cada puente exactamente una vez?
El foco está en las aristas. Los vértices pueden visitarse repetidamente, porque una intersección puede ser necesaria para acceder a conexiones todavía no recorridas.
Un sendero euleriano recorre todas las aristas del grafo exactamente una vez. Puede comenzar y terminar en vértices distintos.
Una arista paralela cuenta como una conexión diferente y debe recorrerse por separado.
Un circuito euleriano es un sendero euleriano cerrado: comienza y termina en el mismo vértice.
Un grafo que contiene un circuito euleriano se denomina euleriano.
Cada vez que el recorrido entra a un vértice intermedio por una arista, debe salir por otra distinta. Las aristas incidentes se consumen en parejas.
En un circuito, incluso el vértice inicial necesita una arista de salida y otra de regreso; por ello todos los grados deben ser pares.
Un grafo no dirigido posee un circuito euleriano si y solo si todos los vértices de grado no nulo pertenecen a una misma componente conexa y todos tienen grado par.
Los vértices aislados no afectan el recorrido de las aristas.
Avanza para recorrer una arista por vez. El ejemplo contiene tres ciclos unidos en A; todas sus aristas se integran en un circuito único.
Aristas
Recorrido
Acción actual
Celeste indica las aristas ya utilizadas y verde la última arista recorrida.
Un grafo no dirigido conectado sobre sus aristas posee un sendero euleriano abierto si y solo si tiene exactamente dos vértices de grado impar.
Con más de dos vértices impares no existe un recorrido que utilice cada arista una sola vez.
| Vértices impares | Resultado | Inicio |
|---|---|---|
| 0 | Circuito euleriano | Cualquier vértice con aristas |
| 2 | Sendero euleriano abierto | Uno de los dos impares |
| Otro número | No existe | — |
Fleury elige en cada paso una arista que no sea puente del grafo restante, salvo que no exista alternativa.
Es intuitivo, pero detectar repetidamente puentes lo hace menos eficiente que Hierholzer.
Hierholzer comienza siguiendo aristas no utilizadas hasta cerrar un ciclo. Si quedan aristas, inicia otro ciclo desde un vértice del recorrido que todavía tenga conexiones y lo inserta en el anterior.
function hierholzer(adyacencia, inicio) {
const grafo = adyacencia.map(lista => [...lista]);
const pila = [inicio];
const circuito = [];
const usadas = new Set();
while (pila.length) {
const u = pila[pila.length - 1];
if (grafo[u].length) {
const { destino: v, id } = grafo[u].pop();
if (usadas.has(id)) continue;
usadas.add(id);
pila.push(v);
} else {
circuito.push(pila.pop());
}
}
return circuito.reverse();
}El identificador de arista es necesario para distinguir aristas paralelas y marcar una arista no dirigida desde cualquiera de sus extremos.
function agregarArista(grafo, u, v, id) {
grafo[u].push({ destino: v, id });
grafo[v].push({ destino: u, id });
}No basta con eliminar solo una aparición: una arista no dirigida figura en las listas de ambos extremos.
Con listas de adyacencia e identificadores de aristas, Hierholzer procesa cada arista una cantidad constante de veces.
Fleury puede llegar a O(E²) si cada decisión vuelve a comprobar puentes.
Un grafo dirigido posee circuito euleriano cuando sus vértices con aristas pertenecen a una región adecuadamente conectada y cada vértice tiene igual grado de entrada y salida.
Para un sendero abierto, el inicio tiene una salida adicional, el final una entrada adicional y los demás grados están equilibrados.
Los multigrafos encajan naturalmente en el problema. Cada arista paralela posee identidad propia. Un bucle aporta 2 al grado de su vértice en un grafo no dirigido y se recorre una vez.
Las implementaciones deben identificar aristas, no solo pares de vértices.
Solo los vértices con grado positivo deben pertenecer a la misma componente. Un vértice aislado no contiene aristas pendientes y puede ignorarse.
Dos componentes que contienen aristas hacen imposible un único recorrido, aunque todos sus grados sean pares.
Si el grafo no es euleriano pero necesitamos cubrir todas las aristas, el problema del cartero chino permite repetir algunas minimizando el costo adicional.
En grafos no dirigidos se emparejan los vértices de grado impar mediante caminos mínimos para convertir todos los grados en pares.
| Propiedad | Euleriano | Hamiltoniano |
|---|---|---|
| Elemento recorrido una vez | Aristas | Vértices |
| Puede repetir | Vértices | Aristas no seleccionadas son irrelevantes |
| Decisión | O(V + E) | NP-completa |
| Criterio principal | Grados y conectividad | Sin criterio completo simple |
Los grafos eulerianos muestran cómo una condición global puede decidirse mediante propiedades locales de grado más una comprobación de conectividad. Hierholzer convierte esa caracterización en un algoritmo lineal.
En el próximo tema estudiaremos isomorfismo de grafos: cómo reconocer cuándo dos representaciones describen exactamente la misma estructura.