estalmat 13-14 los puentes de konigsbergthales.cica.es/~estalmat/act/sesiones/curso-13-14/... ·...
TRANSCRIPT
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
EsTalMat
13-14
Los Puentes de Konigsberg
Sevilla, Febrero 2014
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
El Problema de los Puentes de Königsberg
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Algo de Geografía
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Algo de Historia
LA CIUDAD DE KONIGSBERG
• Fue fundada en 1255 por los caballeros teutónicos.• Primeramente fue un Ducado y luego se convirtió
en Reino.
• Sufrió
la Guerra de los 7 años y las dos Guerras Mundiales.• Formó
parte de los Imperios Prusiano y Alemán
• En la Conferencia de Postdam, después de la Segunda Guerra Mundial, el territorio prusiano fue repartido entre laspotencias vencedoras. La parte Este correspondió
a URSS.
• Desde 1946 forma parte de la U.R.S.S., actual C.E.I.• Cambió
de nombre en 1947 por el actual de Kaliningrado.
• El río Pregel
se llama ahora río Pregolya.
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Königsberg
Castillo Río Pregel Catedral
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Kaliningrado
Ayuntamiento
Río Pregolya
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Ciudadanos Ilustres
Immanuel
Kant1724 -
1804
Gustav
R. Kirchhoff1824 -
1887
David Hilbert1862 -
1943
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
CONJETURA DE FERMAT
La ecuación
xn
+ yn
= zn
donde x, y, z son números naturales, no tiene solución entera para n > 2.
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
… pero en el siglo XVIII era así:
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
El Problema de los Puentes de Königsberg
“¿Es posible recorrer todas las zonas de la ciudad, atravesando todos los puentes una y sólo una vez cada uno
de ellos?”
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Leonhard Euler: 1707-1783
“… Se me ha informado que, mientras unos negaban la posibilidadde hacerlo y otros lo dudaban, nadie sostenía que fuese posible
realmente. El problema podría resolverse haciendocuidadosamente una tabla de todos los recorridos posibles
asegurándose así, por inspección, de cuál de todos ellos, si esque alguno hay, satisface lo requerido. Este método de solución,
sin embargo, es demasiado tedioso y difícil a causa del grannúmero de combinaciones posibles… Por tanto, lo descarté y traté
de buscar otro que mostrase solamente si se puede descubrir uncamino que satisfaga la condición prescrita.”
e 2 π
i
- 1 = 0
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
La solución de Euler: 1736
Para cruzar cada zona de la ciudad hay que
entrar por un puente y salir por otro distinto.
El número de aristas (líneas = puentes) que sale de cada vértice (punto = zona de la
ciudad) debe ser par
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
¿Cómo razonó
Euler?
Regiones Puentes que llegan Operaciones
A 5 3B 3 2C 3 2D 3 2
8 (= 7 + 1)
9 No hay soluciónB
A
C
D
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Recorrido euleriano
Un recorrido euleriano en un grafo es una elección sucesiva de sus aristas (camino en el grafo) de modo que:
1. Se usen todas las aristas.2. Ninguna arista se use más de una vez.3. Al elegir dos aristas consecutivamente, el vértice final de la primera
coincida con el vértice inicial de la segunda.4. El vértice inicial de la primera arista elegida coincide con el vértice
final de la última arista que se elija, (es decir, el recorrido es cerrado).
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
La solución de Euler
en lenguaje coloquial
Euler
afirmó
que para que exista un recorrido de este tipo, es decir, que pase por todos los puentes de la ciudad y además una sola vez por cada uno de ellos, tiene que ocurrir que a todos los vértices (puntos) del diagrama les llegue un número par de aristas (líneas).
En este caso, el camino existe y es
cerrado, es decir, se parte de un punto y se regresa al mismo punto.
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
La solución con el lenguaje matemático actual
Teorema.-
(Euler
(1736) -
Hierholzer
(1873)) La condición necesaria y suficiente para que un grafo admita un recorrido euleriano
es que
todos sus vértices sean de grado par.
Conclusión: La ruta de Königsberg es
imposible.
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Euler
aclara su solución (en lenguaje coloquial)
Euler
completó
su primer resultado indicando que para que exista un camino del tipo exigido, es decir, que recorra todas las zonas de la ciudad pasando por todos los puentes una y sólo una vez por cada uno de ellos es necesario que, o bien a todos los vértices les llegue un número par de líneas (en cuyo caso el camino sería cerrado) o bien sólo haya dos vértices a los que les llegue un número impar de líneas (el camino sería entonces abierto).
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Esta aclaración con el lenguaje matemático
actualCorolario: La C. N. y S. para que en un grafo exista un recorrido que pase por todas sus aristas una y sólo una vez es que el número de vértices de grado impar del grafo sea 0 (en cuyo caso el recorrido es cerrado) o 2 (en cuyo caso sería abierto).
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Un problema alternativo
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
¡Ahora sí
hay solución!
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
¿Y en Sevilla?
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
¿Y en Sevilla?
10717
Una ruta abierta es posible.
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Aplicación: Dibujar sin levantar el lápiz y sin pasar por una
misma línea dos veces
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Resumen: El trabajo del matemático
Problema de la vida real
ModelizaciónModelo Matemático
Solución del ModeloSolución del Problema real
Nueva teoría
adaptada al
modeloTraducción al
mundo real
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
Muchas gracias a todos
MUCHA SUERTE Y APROVECHAMIENTO EN
ESTALMAT 13-14