Ciudad de Könisberg, Prusia, en XVIII:
Ciudad de Könisberg, Prusia, en XVIII:
¿Sería posible dar un paseo pasando por cada uno de los
siete puentes, sin repetir ninguno, comenzando y terminando
en el mismo lugar?
Ciudad de Könisberg, Prusia, en XVIII:
¿Sería posible dar un paseo pasando por cada uno de los
siete puentes, sin repetir ninguno, comenzando y terminando
en el mismo lugar?
Ciudad de Könisberg, Prusia, en XVIII:
(nombre antiguo de la actual ciudad de Kaliningrado, Rusia.)
¿Sería posible dar un paseo pasando por cada uno de los
siete puentes, sin repetir ninguno, comenzando y terminando
en el mismo lugar?
Ciudad de Könisberg, Prusia, en XVIII:
¿ Sería posible armar un circuito que pase por todas las
aristas una sola vez?
Euler
La solución de Euler:
En 1736, el matematico suizo
Leonhard Euler dijo q NO
Grafos eulerianos
• Un circuito C en un grafo G (o multigrafo) es un circuito
euleriano si C pasa por todos las aristas de G una única vez.
• Un grafo G se dice que es euleriano, cuando posee un
circuito euleriano
• Un camino euleriano es un camino que recorre todas las
artistas de G pasando una única vez por cada una
¿Cuando G es euleriano?
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el
circuito?
b
c
b
c
a
d
a
d
Algunos ejemplos
• ¿Si tenemos un circuito euleriano, qué podemos
decir del grado de los vértices?
Algunos ejemplos
• ¿Si tenemos un circuito euleriano, qué podemos
decir del grado de los vértices?
V0 .….. V0 …… V0 ….. V0
Algunos ejemplos
• ¿Si tenemos un circuito euleriano, qué podemos
decir del grado de los vértices?
• Todos los vértices
tienen grado par!
Condición necesaria
• ¿Es suficiente?
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Demo: (Ida).
Si es euleriano, entonces
todos sus vértices tienen
grado par.
ejercicio!
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Demo: (vuelta)
Si todos sus vértices
tienen grado par,
entonces es euleriano
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
C1
Construcción parcial del circuito
C1
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
C1
Construcción parcial del circuito
G’
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
C1
Construcción parcial del circuito
G’
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
C2
Construcción parcial del circuito
C2
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
C1 U C2
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736): Un grafo G (o multigrafo)
conexo es euleriano si y sólo si todos sus nodos
tienen grado par.
G’
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Condición necesaria y suficiente
Teorema (Euler 1736-Hierholzer1973): Un grafo G
(o multigrafo) conexo es euleriano si y sólo si
todos sus nodos tienen grado par.
G’
C
Construcción parcial del circuito
Grafo G’ con las condiciones del Teorema
Algoritmo Hierholzer
1.
2.
3.
4.
5.
6.
7.
G= (V,E) conexo, C=Ǿ, G=G’
C’ := armar un circuito SIMPLE en G’ a partir de v0
C= C U C’
G' := (V, E=E- aristas de C)
v0 := un vértice de C tal que d(v0) > 0 en G'
Mientras E no se vacío, volver a 2
Retornar C
C’, ciclo simple en G’
C
C es un circuito euleriano entre las aristas que no están en G’
Recordar justificar los invariantes
C := armar un circuito SIMPLE a partir de v0
¿Por qué siempre existe?
Recordar justificar los invariantes
C := armar un circuito SIMPLE a partir de v0
¿Por qué siempre existe?
Como los grados de los vértices son par y se le está sacando a cada
vértice una cantidad par de aristas incidentes (0 o 2) en cada iteración,
los grados continúan siendo par en cada C.C (invariante) y siempre que
puedo llegar al vértice, puedo salir
Recordar justificar los invariantes
C := armar un circuito SIMPLE a partir de v0
¿Por qué siempre existe?
Como los grados de los vértices son par y se le está sacando a cada
vértice una cantidad par de aristas incidentes (0 o 2) en cada iteración,
los grados continúan siendo par en cada C.C (invariante) y siempre que
puedo llegar al vértice, puedo salir
C= C U C’
¿Por qué C es un circuito que no repite
aristas, cómo lo recorro?
Recordar justificar los invariantes
C := armar un circuito SIMPLE a partir de v0
¿Por qué siempre existe?
Como los grados de los vértices son par y se le está sacando a cada
vértice una cantidad par de aristas incidentes (0 o 2) en cada iteración,
los grados continúan siendo par en cada C.C (invariante) y siempre que
puedo llegar al vértice, puedo salir
C= C U C’
¿Por qué C es un circuito que no repite
aristas, cómo lo recorro?
Como C y C’ tienen intersección en un vértice v0, empezamos en v0,
recorremos C, que no repite aristas (invariante) y luego recorremos
C’,que es un circuito simple con aristas de G’, es decir, aristas que no
están en C. Cuando termina, C es un circuito que no repite aristas y
contiene TODAS las aristas de G, ie. es euleriano
Recordar justificar los invariantes
v0 := un vértice de C tal que d(v0) > 0 en G'
¿Por qué siempre existe?
•
Si hay vértices de G que no están en C, entonces
hay un camino de ese vértice a C, porque G es
conexo
•
Si todos los vértices de G son alcanzados por C, y
G’ tiene aristas, tomamos un extremo de una
arista.
Nota: Esto se puede encuadrar en un esquema de
inducción en “m”, teniendo en cuenta estos
invariantes.
Recordar justificar los invariantes
v0 := un vértice de C tal que d(v0) > 0 en G'
¿Por qué siempre existe?
•
Si hay vértices de G que no están en C, entonces
hay un camino de ese vértice a C, porque G es
conexo
•
Si todos los vértices de G son alcanzados por C, y
G’ tiene aristas, tomamos un extremo de una
arista.
Cual es la complejidad de este algoritmo?
Corolarios…
Teorema Un grafo (o multigrafo) conexo tiene un
camino euleriano si y sólo si tiene exactamente
dos nodos de grado impar.
Demo:
Corolarios…
Teorema Un grafo (o multigrafo) conexo tiene un
camino euleriano si y sólo si tiene exactamente
dos nodos de grado impar.
Demo: Ejercicio
Hint: Considerar el caso en que esos dos vértices son
adyacentes y el caso en que no y aplicar el teorema
anterior a un multigrafo.
Corolarios…
Teorema Un digrafo conexo es euleriano si y sólo
si para todo vértice se verifica que din(v)= dout(v)
Demo:
Corolarios…
Teorema Un digrafo conexo es euleriano si y sólo
si para todo vértice se verifica que din(v)= dout(v)
Demo: Ejercicio
Hint: Seguir la demo del Teorema de Euler, teniendo en
cuenta la orientación de las aristas
Aplicaciones de circuitos o caminos eulerianos
• Buscar caminos que pasen por todas las calles
de una ciudad (asfaltar, recolectar basura,
cartero)
• Cada camino en una red de transportes;
• Famoso Problema del cartero chino !
Problema del cartero chino (Guan, 1962)
Dado un grafo G con longitudes asignadas a
sus aristas, el problema consiste en encontrar un
circuito que pase por cada arista de G al menos
una vez de longitud mínima
Si G es euleriano, un circuito euleriano es LA
solución del problema del cartero chino.
Como se resuelve?
Problema del cartero chino (Guan, 1962)
Dado un grafo G con longitudes asignadas a
sus aristas, el problema consiste en encontrar un
circuito que pase por cada arista de G al menos
una vez de longitud mínima
Si G es euleriano, un circuito euleriano es LA
solución del problema del cartero chino.
Como se resuelve?
Existen algoritmos polinomiales para el problema
del cartero chino cuando G es totalmente
orientado o no es orientado.
No se conocen algoritmos polinomiales si el grafo
es mixto (algunas aristas orientados y otros no).
Descargar

claseeuler