Ciudad de Könisberg, Prusia, en XVIII:. ¿Sería posible dar un paseo pasando por cada uno de los...
-
Upload
goito-abascal -
Category
Documents
-
view
218 -
download
0
Transcript of Ciudad de Könisberg, Prusia, en XVIII:. ¿Sería posible dar un paseo pasando por cada uno de los...
![Page 1: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/1.jpg)
Ciudad de Könisberg, Prusia, en XVIII:
![Page 2: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/2.jpg)
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?
![Page 3: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/3.jpg)
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?
![Page 4: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/4.jpg)
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?
![Page 5: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/5.jpg)
Ciudad de Könisberg, Prusia, en XVIII:
¿ Sería posible armar un circuito que pase por todas las aristas una sola vez?
![Page 6: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/6.jpg)
Euler
La solución de Euler:
En 1736, el matematico suizo
Leonhard Euler dijo q NO
![Page 7: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/7.jpg)
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?
![Page 8: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/8.jpg)
Algunos ejemplos
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
![Page 9: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/9.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 10: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/10.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 11: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/11.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 12: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/12.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 13: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/13.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 14: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/14.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 15: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/15.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 16: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/16.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 17: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/17.jpg)
• ¿Es único? ¿Importa por dónde empezamos a armar el circuito?
cb
a d
cb
a d
Algunos ejemplos
![Page 18: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/18.jpg)
• ¿Si tenemos un circuito euleriano, qué podemos decir del grado de los vértices?
Algunos ejemplos
![Page 19: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/19.jpg)
• ¿Si tenemos un circuito euleriano, qué podemos decir del grado de los vértices?
V0 .….. V0 …… V0 ….. V0
Algunos ejemplos
![Page 20: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/20.jpg)
• ¿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?
Algunos ejemplos
![Page 21: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/21.jpg)
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
![Page 22: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/22.jpg)
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!
![Page 23: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/23.jpg)
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
![Page 24: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/24.jpg)
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
![Page 25: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/25.jpg)
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
![Page 26: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/26.jpg)
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
![Page 27: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/27.jpg)
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
![Page 28: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/28.jpg)
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
![Page 29: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/29.jpg)
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
C1 C1
Condición necesaria y suficiente
![Page 30: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/30.jpg)
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
G’C1
Condición necesaria y suficiente
![Page 31: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/31.jpg)
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
G’C1
Condición necesaria y suficiente
![Page 32: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/32.jpg)
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
G’
Condición necesaria y suficiente
![Page 33: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/33.jpg)
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
G’
Condición necesaria y suficiente
![Page 34: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/34.jpg)
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
G’
Condición necesaria y suficiente
![Page 35: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/35.jpg)
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
C2 C2
G’
Condición necesaria y suficiente
![Page 36: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/36.jpg)
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
G’
Condición necesaria y suficiente
![Page 37: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/37.jpg)
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
G’C1 U C2
Condición necesaria y suficiente
![Page 38: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/38.jpg)
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
G’
Condición necesaria y suficiente
![Page 39: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/39.jpg)
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
G’
Condición necesaria y suficiente
![Page 40: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/40.jpg)
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
G’
Condición necesaria y suficiente
![Page 41: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/41.jpg)
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
G’
Condición necesaria y suficiente
![Page 42: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/42.jpg)
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
G’
Condición necesaria y suficiente
![Page 43: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/43.jpg)
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
G’
Condición necesaria y suficiente
![Page 44: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/44.jpg)
Teorema (Euler 1736-Hierholzer1973): 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
G’
C
Condición necesaria y suficiente
![Page 45: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/45.jpg)
Algoritmo Hierholzer
1. G= (V,E) conexo, C=Ǿ, G=G’
2. C’ := armar un circuito SIMPLE en G’ a partir de v0
3. C= C U C’
4. G' := (V, E=E- aristas de C)
5. v0 := un vértice de C tal que d(v0) > 0 en G'
6. Mientras E no se vacío, volver a 2
7. Retornar C
C es un circuito euleriano entre las aristas que no están en G’
C
C’, ciclo simple en G’
![Page 46: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/46.jpg)
Recordar justificar los invariantesC := armar un circuito SIMPLE a partir de v0
¿Por qué siempre existe?
![Page 47: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/47.jpg)
Recordar justificar los invariantesC := 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
![Page 48: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/48.jpg)
Recordar justificar los invariantesC := 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?
![Page 49: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/49.jpg)
Recordar justificar los invariantesC := 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
![Page 50: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/50.jpg)
Recordar justificar los invariantesv0 := 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.
![Page 51: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/51.jpg)
Recordar justificar los invariantesv0 := 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?
![Page 52: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/52.jpg)
Teorema Un grafo (o multigrafo) conexo tiene un camino euleriano si y sólo si tiene exactamente dos nodos de grado impar.
Demo:
Corolarios…
![Page 53: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/53.jpg)
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…
![Page 54: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/54.jpg)
Teorema Un digrafo conexo es euleriano si y sólo si para todo vértice se verifica que din(v)= dout(v)
Demo:
Corolarios…
![Page 55: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/55.jpg)
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
Corolarios…
![Page 56: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/56.jpg)
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 !
![Page 57: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/57.jpg)
Problema del cartero chino (Guan, 1962)
Dado un grafo G con longitudes asignadas asus aristas, el problema consiste en encontrar un
circuito que pase por cada arista de G al menosuna vez de longitud mínima
Si G es euleriano, un circuito euleriano es LA solución del problema del cartero chino.
Como se resuelve?
![Page 58: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b42e1a28abb57c8fd591/html5/thumbnails/58.jpg)
Problema del cartero chino (Guan, 1962)
Dado un grafo G con longitudes asignadas asus aristas, el problema consiste en encontrar un
circuito que pase por cada arista de G al menosuna 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).