1
Introducción: 1
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
Könisberg (AT) (Río Pregel)
Problema: ¿Es posible, comenzando en cualquier punto de la ciudad de Konisberg, elegir un camino que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel?
Introducción: 2
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de GrafosProblema: ¿Es posible, comenzando en cualquier punto de la ciudad de Konisberg, elegir un camino que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel?
C
A
B
D
2
Introducción: 3
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de GrafosProblema: ¿Es posible, comenzando en cualquier punto de la ciudad de Konisberg, elegir un camino que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel?
C
A
B
D
vérticesaristas
Introducción: 4
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de GrafosProblema: ¿Es posible, comenzando en cualquier punto de la ciudad de Konisberg, elegir un camino que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel?
C
A
B
D
vérticesaristas
El primer grafo de la historia
3
Introducción: 5
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Leonhard Euler
Solutio problematis ad geometriam situspertinentis, Commentarii AcademiaeScientiarum Imperialis Petropolitanae 8 (1736), 128--140
Orígenes de la Teoría de Grafos
Introducción: 6
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
Redes eléctricas (Kirchhoff, 1847)
4
Introducción: 7
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
Metano (CH4) Etano (C2H6) Propano (C3H8) Butano (C4H10)
Química orgánica (hidrocarburos saturados)
Isómeros químicos (Cayley, 1874)
Isómeros del C4H10
Introducción: 8
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
Coloreado de mapas:
5
Introducción: 9
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
•En 1850 Francis Guthrie se interesa por el coloreado de mapas.
•El 23 de octubre de 1852, el matemático inglés Augustus de Morgan escribió a su colega Sir William R. Hamilton la siguiente carta:
“Un estudiante mío me ha pedido una respuesta sobre una cuestión de la cual yo desconocía y desconozco la solución. Él dice que cualquier mapa ha de poder colorearse con cuatro colores...’’
CONJETURA DE LOS 4 COLORESIntroducción: 10
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Orígenes de la Teoría de Grafos
6
Introducción: 11
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
•En 1878 Arthur Cayley presentó el problema a la London Mathematical Society.
•Alfred Kempe publica el primer artículo referente a la demostración de dicha conjetura.
CONJETURA DE LOS 4 COLORES
•En 1890 Heawood encontró un error (demuestra su validez para cinco colores).
•K. Appel y W. Haken, en 1976 demostraron con ayuda de tres ordenadores el Teorema de los Cuatro Colores.
Orígenes de la Teoría de Grafos
Introducción: 12
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 1: Se pretende realizar un calendario de exámenes de las asignaturas A, B, C, D, E y F. Debemos tener en cuenta que hay alumnos que se tienen que examinar de las asignaturas
A-B, A-D, A-F, B-F, C-E, D-E y E-F
¿Es posible en estas condiciones establecer un calendario de exámenes?
E
D
A
F
C
B
F4º
E3º
B y D2º
A y C1º
AsignaturasDía
7
Introducción: 13
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
A
F
E
D
C
B
C y F3º
B y D2º
A y E1º
AsignaturasDía
Problema 1: Se pretende realizar un calendario de exámenes de las asignaturas A, B, C, D, E y F. Debemos tener en cuenta que hay alumnos que se tienen que examinar de las asignaturas
A-B, A-D, A-F, B-F, C-E, D-E y E-F
¿Es posible en estas condiciones establecer un calendario de exámenes?
Introducción: 14
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón 1
0
2
3
4
5
7
6
8
8
Introducción: 15
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón 1
0
2
3
4
5
7
6
8
Parejas:
8 con 0
Introducción: 16
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón 1
2
3
4
5
7
6
Parejas:
8 con 0
7 con 1
9
Introducción: 17
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón
2
3
4
56
Parejas:
8 con 0
7 con 1
6 con 2
Introducción: 18
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón
3
4
5
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
10
Introducción: 19
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Ramón
4
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
4 es María
Introducción: 20
MA
TE
MÁ
TIC
A D
ISC
RE
TA
Pedro Reyes
Aplicaciones de la Teoría de Grafos
Problema 2: Ramón y María asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretón de manos y otros con un beso. Al acabar la fiesta, Ramón pregunta a los asistentes a cuánta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. ¿A cuantas personas ha dado la mano María?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramón, 0,1,2,3,4,5,6,7,8}
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
4 es María
Ramón 1
0
2
3
MARÍA5
7
6
8