7Euler

Königsberg

Recorridos eulerianos
Gregorio Hernández Peñalver
UPM
Teoría de Grafos
2

Euler 1736

3

Un recorrido euleriano en un grafo es un recorrido que contiene a
todas las aristas del grafoexactamente una vez.
Un grafo es euleriano si contiene un recorrido euleriano cerrado.
Teorema
Sea G un grafo conexo
G es euleriano ⇔ Todos los vértices de G tienen grado par.
Consecuencia
Un grafo conexoG tiene un recorrido euleriano no cerrado ⇔
G tiene, exactamente, dos vértices de grado impar.

4

Algoritmo de Fleury
Paso 1.- Se comienza en un vértice cualquiera v0 .
(O en un impar si hay dosvértices impares)
Paso 2.- Si se ha construido el camino v0 a1 v1 a2...vk-1 ak vk con
aristas distintas, se elige la arista siguiente ak+1 con las condiciones:
(1) ak+1 incidente con vk
(2) no ser puenteen el grafo G−{a1,a2,...,ak}
(salvo que no haya alternativa).
Paso 3.- Se sigue hasta que el camino contenga todas las aristas.
Complejidad
En cada paso se analiza si la arista elegida para avanzar esun puente.
Este análisis cuesta O(q). Como se recorren todas las aristas la
complejidad total es O(q2)

5

6

1

Algoritmo de Fleury

Justificación

Justificación

Algoritmo de Fleury

El algoritmoproduce un recorrido euleriano.
Inducción sobre q
El resultado es cierto si q=1.
Supongamos cierto para q − 1 aristas.
Caso 1) Todos los vértices de G son pares
Entonces G no puede tener puentes. (Siuna arista fuera puente,
al borrarla tendríamos grafos con sólo un vértice impar).
Así empezando en un vértice v y una primera arista uv, el grafo
G−{uv} tiene q − 1 aristas y dos vértices impares,luego por hipótesis
de inducción tenemos un recorrido euleriano en G −{uv} que con la
arista uv completa un recorrido euleriano cerrado en G.

Caso 2) Supongamos ahora que G tiene dos vértices imparesu, v.
Si d(u)=1 y x es el vértice adyacente, por inducción en G −{ux}
tenemos el recorrido euleriano de u hasta v.
Si d(u)>1, sea P un camino de u a v, y sea ux una arista incidente
con u que no...