estalmat-andalucía actividades...
TRANSCRIPT
ESTALMAT-Andalucía Actividades 14/15 Sesión: 12 Fecha: 31/01/15 Título: GRAFOS (I) Primer Curso. _______________________________________________________________________________________
Alfonso Carriazo, Juan Núñez y Mª Trinidad Villar
ACTIVIDAD 1.- a) El “Problema de los Puentes de Königsberg”. Breve historia y resolución.
b) En la figura tenemos un mapa de la ciudad de Königsberg tal y como es hoy en día. ¿Cómo se resuelve ahora el “Problema de los puentes de Königsberg”?
ESTALMAT-Andalucía Actividades 14/15 Sesión: 12 Fecha: 31/01/15 Título: GRAFOS (I) Primer Curso. _______________________________________________________________________________________
Alfonso Carriazo, Juan Núñez y Mª Trinidad Villar
ACTIVIDAD 2.- Lema del Apretón de Manos Intenta dibujar un grafo con exactamente 3 vértices de grado impar. En la siguiente plantilla de 25 puntos tú eres el número …… Haremos una lista en la pizarra con las iniciales de los nombres y primeros apellidos de cada uno de tus compañeros. Traza una arista entre tu número y el de un compañero si coincide la inicial de vuestros nombres o bien la inicial de vuestros primeros apellidos.
En el grafo resultante el número de vértices con grado impar debe ser par (pudiendo ser cero). ¿Por qué crees que ocurre esto?
12
3
6
4
5
7
8
25
23
24
22
18
19
20
21
1213
15
16
17
9
1011
14
ESTALMAT-Andalucía Actividades 14/15 Sesión: 12 Fecha: 31/01/15 Título: GRAFOS (I) Primer Curso. _______________________________________________________________________________________
Alfonso Carriazo, Juan Núñez y Mª Trinidad Villar
ACTIVIDAD 3.-
En un futuro no muy lejano habrá viajes interplanetarios. Supón que en el sistema solar se establecieran las siguientes rutas y sólo éstas:
Tierra - Mercurio, Urano - Neptuno, Neptuno - Saturno, Marte - Urano, Saturno - Júpiter,
Plutón - Venus, Júpiter - Marte, Tierra - Plutón, Plutón - Mercurio, Mercurio - Venus.
¿Se podría realizar el viaje desde la Tierra hasta Marte? ¿Por qué?
ESTALMAT-Andalucía Actividades 14/15 Sesión: 12 Fecha: 31/01/15 Título: GRAFOS (I) Primer Curso. _______________________________________________________________________________________
Alfonso Carriazo, Juan Núñez y Mª Trinidad Villar
ACTIVIDAD 4.- a) En cierto pueblo hay tres vecinos que se llevan mal y no quieren que sus caminos se crucen cuando se dirigen directamente desde su casa hacia alguno de los siguientes establecimientos: la tienda de comestibles, la gasolinera y el centro de salud. ¿Cómo pueden hacerlo? b) Se quiere hacer una red de carreteras que conecte las siguientes ciudades: Cádiz, Córdoba, Huelva, Málaga y Sevilla. ¿Podría construirse dicha red de manera que no tuviera cruces y que cualquier par de ciudades estuviera conectado por una carretera directa?
c) Considera los siguientes grafos e intenta dibujarlos evitando el mayor número de cruces posibles. Para que te resulte más fácil, etiqueta previamente los vértices.
ESTALMAT-Andalucía Actividades 14/15 Sesión: 12 Fecha: 31/01/15 Título: GRAFOS (I) Primer Curso. _______________________________________________________________________________________
Alfonso Carriazo, Juan Núñez y Mª Trinidad Villar
ACTIVIDAD 5.- Trío de Palabras Tenemos las siguientes tarjetas para jugar con un contrincante.
Reglas del juego: Se colocan las tarjetas boca arriba y cada jugador, por turno, va eligiendo una tarjeta y colocándola junto
a él también boca arriba. Gana el primer jugador que consigue tres palabras que tengan la misma vocal. Si nadie lo consigue, la partida queda en tablas. ¿Cómo podríamos dibujar un grafo que nos ayudara a diseñar una estrategia ganadora?
¿Cómo sería el grafo si en las reglas del juego cambiáramos la condición de conseguir “tres palabras que tengan la misma vocal” por la de conseguir “tres palabras que tengan la misma consonante”? ¿Y si consideramos tríos de palabras con la misma letra?
FACULTAD DE
MATEMÁTICAS
A. Carriazo, L. M. Fernández, J. Núñez y M. T. Villar
EsTalMat 14-15
Los Puentes de Konigsberg
Sevilla, Enero 2015
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 las potencias 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
… 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 gran
número de combinaciones posibles… Por tanto, lo descarté y tratéde buscar otro que mostrase solamente si se puede descubrir un
camino 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
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 14-15