orígenes de la teoría de grafos - ma1.eii.us.esma1.eii.us.es/material/md_ii_introduccion.pdf ·...
Post on 09-Feb-2018
224 Views
Preview:
TRANSCRIPT
-
Introduccin: 1
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
Knisberg (AT) (Ro 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 ro Pregel?
-
Introduccin: 2
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora 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 ro Pregel?
C
A
B
D
-
Introduccin: 3
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora 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 ro Pregel?
C
A
B
D
vrtices
aristas
-
Introduccin: 4
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora 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 ro Pregel?
C
A
B
D
vrtices
aristas
El primer grafo de la historia
-
Introduccin: 5
MATEMTICA DISCRETA
Pedro Reyes
Leonhard Euler
Solutio problematis ad geometriam situspertinentis, Commentarii AcademiaeScientiarum Imperialis Petropolitanae 8 (1736), 128--140
Orgenes de la Teora de Grafos
-
Introduccin: 6
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
Redes elctricas (Kirchhoff, 1847)
-
Introduccin: 7
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
Metano (CH4) Etano (C2H6) Propano (C3H8) Butano (C4H10)
Qumica orgnica (hidrocarburos saturados)
Ismeros qumicos (Cayley, 1874)
Ismeros del C4H10
-
Introduccin: 8
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
Coloreado de mapas:
-
Introduccin: 9
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
En 1850 Francis Guthrie se interesa por el coloreado de mapas.
El 23 de octubre de 1852, el matemtico ingls
Augustus de Morgan escribi a su colega Sir William R. Hamilton la siguiente carta:
Un estudiante mo me ha pedido una respuesta sobre una cuestin de la cual yo desconoca y desconozco la solucin. l dice que cualquier mapa ha de poder colorearse con cuatro colores...
CONJETURA DE LOS 4 COLORES
-
Introduccin: 10
MATEMTICA DISCRETA
Pedro Reyes
Orgenes de la Teora de Grafos
-
Introduccin: 11
MATEMTICA DISCRETA
Pedro Reyes
En 1878 Arthur Cayley present el problema a la London Mathematical Society.
Alfred Kempe publica el primer artculo referente a la demostracin 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.
Orgenes de la Teora de Grafos
-
Introduccin: 12
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 1: Se pretende realizar un calendario de exmenes 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 exmenes?
E
D
A
F
C
B
F4
E3
B y D2
A y C1
AsignaturasDa
-
Introduccin: 13
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
A
F
E
D
C
B
C y F3
B y D2
A y E1
AsignaturasDa
Problema 1: Se pretende realizar un calendario de exmenes 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 exmenes?
-
Introduccin: 14
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn 1
0
2
3
4
5
7
6
8
-
Introduccin: 15
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn 1
0
2
3
4
5
7
6
8
Parejas:
8 con 0
-
Introduccin: 16
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn 1
2
3
4
5
7
6
Parejas:
8 con 0
7 con 1
-
Introduccin: 17
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn
2
3
4
5
6
Parejas:
8 con 0
7 con 1
6 con 2
-
Introduccin: 18
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn
3
4
5
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
-
Introduccin: 19
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Ramn
4
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
4 es Mara
-
Introduccin: 20
MATEMTICA DISCRETA
Pedro Reyes
Aplicaciones de la Teora de Grafos
Problema 2: Ramn y Mara asisten a una fiesta junto con otros cuatro matrimonios. Al encontrarse algunos se saludan con un apretn de manos y otros con un beso. Al acabar la fiesta, Ramn pregunta a los asistentes a cunta gente ha dado la mano al saludar y recibe nueve respuestas diferentes. A cuantas personas ha dado la mano Mara?
Respuestas: 0,1,2,3,4,5,6,7,8
Asistentes: {Ramn, 0,1,2,3,4,5,6,7,8}
Parejas:
8 con 0
7 con 1
6 con 2
5 con 3
4 es Mara
Ramn 1
0
2
3
MARA5
7
6
8
top related