17237313 Grafos Eulerianos

Facultad de Ciencias y Tecnología
Departamento de Computación

Elementos Discretos

Teoría de Grafos:

Grafos Eulerianos

Teoría de Grafos
Unidad Académica Elementos Discretos

Problema de los Puentes de Königsberg:
Los Puentes de Königsberg:
Problema de
los Puentes de
Königsberg

Königsberg (populosa y rica ciudad de la Prusia Oriental), nombre
antiguo de la actual ciudad de Kaliningrado(Rusia).

La solución de
Euler
Definición de
Grafo
Euleriano
Teorema del
Circuito
Euleriano

El río Pregel atraviesa la ciudad y existen 2 islas en el medio del río,
conectadas entre sí y con las márgenes del río, a través de 7 puentes.

Demostración
del Teorema
Corolario del
Camino
Euleriano

Teoría de Grafos
Unidad Académica Elementos Discretos

Problema de los Puentes de Königsberg:
Los Puentes deKönigsberg:
Problema de
los Puentes de
Königsberg

Protagonistas de uno de los problemas de los matemáticos del siglo
XVIII.

La solución de
Euler
Definición de
Grafo
Euleriano
Teorema del
Circuito
Euleriano
Demostración
del Teorema
Corolario del
Camino
Euleriano

Problema:
¿Es posible partir de un punto de la ciudad y recorrer cada puente
una sola vez regresando al punto de partida.?
Teoría deGrafos
Unidad Académica Elementos Discretos

La solución de Euler:
Euler:
Problema de
los Puentes de
Königsberg
La solución de
Euler
Definición de
Grafo
Euleriano
Teorema del
Circuito
Euleriano
Demostración
del Teorema
Corolario del
Camino
Euleriano

En 1736, el matematico suizo Leonhard Euler
modelo el problema usando un grafo G = (V, A)
donde:
V = {las islas y las dos márgenes del río} y
A = {lospuentes}
margen 1
isla 1

1707 - 1783

G = (V, A)
isla 2

margen 2

Problema:
¿Existirá un circuito en el grafo G que recorra todos los arcos una
sola vez?

Respuesta:
Euler demostró que no existe dicho circuito.
Teoría de Grafos
Unidad Académica Elementos Discretos

La solución de Euler:
Euler:
Problema de
los Puentes de
Königsberg
La solución de
Euler
Definición de
Grafo
Euleriano

Para queexistiera el circuito buscado, todos los vértices de G debían
ser de grado par (en este caso todos son de grado impar).
3
G = (V, A)
3

5
3

Teorema del
Circuito
Euleriano
Demostración
del Teorema

Construcción de puentes:
Si se construyeran dos puentes el problema tendría solución
afirmativa.
4
G = (V, A)

Corolario del
Camino
Euleriano

6

4

4
Teoría de Grafos
Unidad Académica Elementos DiscretosDefinición de Grafo Euleriano:
Problema de
los Puentes de
Königsberg

Definiciones:
Camino euleriano:
Es un camino que recorre todos los arcos del grafo una sola vez.

Definición de
Grafo
Euleriano
Teorema del
Circuito
Euleriano
Demostración
del Teorema
Corolario del
Camino
Euleriano

Por lo tanto, es un camino simple que transita por todos los arcos del
grafo.

Circuito euleriano:
Es un caminoeuleriano, donde el vértice de partida coincide con el
vértice de llegada.
G = (V, A, ϕ)

Ejemplos:

La solución de
Euler

3

4

e2

e9 4
e1
e5

G1 = (V1, A1, ϕ)

2

2

e6
e10 4 e7
e8

4

e2

e4

e3

e11

4
3
C = (e2, e3, e4, e5, e6, e7, e8, e1, e9, e10, e11)
camino euleriano

e6

2 e7 e3

e1
e5
e8

e4
4
2
C = (e1, e2, e3, e4, e5, e6, e7, e8)
circuito euleriano
Teoría de Grafos
Unidad AcadémicaElementos Discretos

Definición de Grafo Euleriano:
Grafo Euleriano:

La solución de
Euler
Definición de
Grafo
Euleriano
Teorema del
Circuito
Euleriano

Un grafo es euleriano si contiene un camino o un circuito euleriano.

Por lo tanto

Problema de
los Puentes de
Königsberg

G1 = (V1, A1, ϕ)

G = (V, A, ϕ)

3

4

e2

e9 4
e1
e5

2

2

e6
e10 4 e7
e8

4

e2

e4

e3

2 e7 e3

e1
e5

e11

e8

e4
4
2
C= (e1, e2, e3, e4, e5, e6, e7, e8)
circuito euleriano

4
3
C = (e2, e3, e4, e5, e6, e7, e8, e1, e9, e10, e11)
camino euleriano

euleriano

e6

euleriano

3
G = (V, A)

Demostración
del Teorema
Corolario del
Camino
Euleriano

5

3

3
No se puede construir un
camino euleriano

no es euleriano
Teoría de Grafos
Unidad Académica Elementos Discretos

Teorema del Circuito Euleriano:
Teorema:
Problema...