Construcción de Caminos de Euler

Teoría

Construir un camino (o circuito) de Euler consiste en encontrar un recorrido en una gráfica finita que pase por cada arista exactamente una vez. Aunque la existencia de tal camino la determinas simplemente por la paridad de los grados de los vértices (el Teorema de Euler), encontrar realmente la secuencia de vértices requiere enfoques algorítmicos específicos. Este problema es fundamental en combinatoria y teoría de gráficas, y sirve como base para problemas de inspección de rutas, ensamblaje de fragmentos de ADN y secuencias de de Bruijn.

Para esta construcción, puedes usar principalmente dos algoritmos: el Algoritmo de Fleury y el Algoritmo de Hierholzer. El Algoritmo de Fleury es un enfoque "voraz" (greedy) que construye el camino paso a paso evitando puentes (aristas cuya eliminación aumenta el número de componentes conexas) a menos que sea absolutamente necesario. Aunque es conceptualmente simple, es computacionalmente ineficiente para gráficas grandes. El Algoritmo de Hierholzer es más eficiente y te da una mejor idea de la estructura; descompone la gráfica en ciclos con aristas ajenas y los une.

Para las olimpiadas de matemáticas, entender estas construcciones te da intuición sobre las propiedades estructurales de las gráficas eulerianas. Específicamente, el enfoque de Hierholzer refuerza el concepto de que una gráfica conexa donde todos los grados son pares es, esencialmente, una unión de ciclos con aristas ajenas. Esta técnica de descomposición suele ser más útil en problemas de olimpiada que el propio resultado de encontrar el camino.

Fórmulas Clave

1. Criterios de Existencia (Prerrequisitos) Sea $G = (V, E)$ una gráfica conexa.

• $G$ tiene un Circuito de Euler si y solo si $\deg(v)$ es par para todo $v \in V$.
• $G$ tiene un Camino de Euler si y solo si exactamente cero o dos vértices tienen grados impares.

2. Algoritmo de Fleury Para construir un camino o circuito de Euler empezando en el vértice $u$:

1. Empieza en un vértice inicial válido $u$ (si hay 2 vértices impares, tienes que empezar en uno de ellos; si no, en cualquier vértice).
2. Desde el vértice actual $u$, elige una arista $(u, v)$ tal que:
   • $(u, v)$ no sea un puente en la gráfica restante actual, O
   • No haya otra arista disponible que no sea un puente.
3. Recorre $(u, v)$ y quítala de la gráfica. Pon a $v$ como el vértice actual.
4. Repite hasta que no queden aristas.

3. Algoritmo de Hierholzer (Descomposición en Ciclos) Para construir un circuito de Euler en una gráfica $G$ donde todos los vértices tienen grado par:

1. Elige cualquier vértice inicial $v$.
2. Sigue un rastro de aristas desde $v$ de forma arbitraria hasta regresar a $v$. Como cada vértice tiene grado par, es imposible que te quedes atrapado en cualquier vértice que no sea $v$. Esto forma un ciclo $C$.
3. Si $C$ contiene todas las aristas de $G$, detente.
4. De lo contrario, quita las aristas de $C$ de $G$. Identifica un vértice $w$ en $C$ que todavía tenga aristas incidentes en la gráfica restante.
5. Construye un nuevo ciclo $C'$ que empiece y termine en $w$ usando aristas no utilizadas.
6. Une $C'$ con $C$ (recorre $C$ hasta llegar a $w$, recorre todo $C'$, y luego continúa con el resto de $C$).
7. Repite hasta que uses todas las aristas.

4. Conversión de Camino a Circuito Si vas a construir un Camino de Euler entre los vértices de grado impar $u$ y $v$: $$ G' = G \cup {(u, v)} $$ Agrega una arista ficticia temporal $(u, v)$. Encuentra un Circuito de Euler en $G'$, y luego quita $(u, v)$ para romper el circuito y obtener el camino que buscas.

Demostración

Teorema: El Algoritmo de Hierholzer construye correctamente un Circuito de Euler para cualquier gráfica conexa $G=(V, E)$ donde cada vértice tiene un grado par.

Demostración: La demostración es por inducción sobre el número de aristas $|E|$.

Caso Base: Si $|E|=0$, el camino trivial que consiste en un solo vértice es un circuito de Euler. Si $|E| > 0$, como $G$ es conexa y cada vértice tiene grado par (y al menos un vértice tiene grado $\ge 2$), $G$ debe contener al menos un ciclo.

Paso Inductivo: Supón que para cualquier gráfica con menos de $k$ aristas que cumpla las condiciones eulerianas, el algoritmo construye un circuito válido. Sea $|E| = k$.

1. Encuentra el primer ciclo: Empieza en un vértice arbitrario $v_0$. Recorre una arista hacia $v_1$. Como $\deg(v_1)$ es par, si entras a $v_1$, debe haber una arista sin usar que salga de $v_1$. Continúa este recorrido. Como la gráfica es finita, eventualmente tienes que volver a visitar un vértice. Debido a que no puedes quedarte "atrapado" en ningún vértice que no sea el inicial (por los grados pares), eventualmente regresarás a $v_0$, formando un ciclo $C$.

2. Quita el ciclo: Considera la subgráfica $G' = (V, E \setminus E(C))$.

   • Al quitar las aristas del ciclo $C$, el grado de cada vértice en $C$ se reduce exactamente en 2.
   • Como todos los vértices en $G$ tenían grados pares, todos los vértices en $G'$ siguen teniendo grados pares.
   • Puede que $G'$ no sea conexa. Consiste en varias componentes conexas $K_1, K_2, \dots, K_m$ y posiblemente vértices aislados.

3. Aplica inducción: Cada componente $K_i$ tiene menos de $k$ aristas y cumple la condición de grado par. Por la hipótesis inductiva, cada componente $K_i$ tiene un circuito de Euler $T_i$.

4. Une los circuitos: Debido a que la gráfica original $G$ era conexa, cada componente $K_i$ que contenga al menos una arista debe compartir al menos un vértice con el ciclo $C$ (de lo contrario, $G$ habría sido disconexa). Sea $w_i$ un vértice común a $C$ y a la componente $K_i$. Puedes construir el circuito de Euler completo para $G$ de la siguiente manera:

   • Recorre $C$ empezando desde $v_0$.
   • Cuando encuentres un vértice $w_i$ que sea parte de una componente $K_i$, haz una pausa en tu recorrido de $C$, recorre todo el circuito $T_i$ empezando y terminando en $w_i$, y luego continúa recorriendo $C$.

   Como cada arista en $G$ pertenece a $C$ o a exactamente una componente $K_i$, y las recorres todas en una secuencia continua, el resultado es un Circuito de Euler.

$\square$