Evaluacion

Curso de doctorado “Problemas de optimizaci´n sobre grafos” o Departament de Matem`tica a

Los grafos como modelos matem´ticos: a ejemplos hist´ricos y aplicaciones actuales o

Los grafos como modelos matem´ticos: ejemplo hist´rico a o
El problema de los siete puentes de K¨nigsberg (Euler, 1736) o

Los grafos como modelos matem´ticos: a problema de optimizaci´n o
El problema del carterochino (Kwan Mei-Ko, 1960) Formulaci´n del problema: Un cartero debe repartir la correspondencia a cada o una de las manzanas de casas de su distrito siendo la oficina de correos su punto de partida y fin. Encontrar una ruta ´ptima (distancia total recorrida o m´ ınima).

Los grafos como modelos matem´ticos: ejemplo hist´rico a o
El juego del dodecaedro (Hamilton, 1857)

Los grafos comomodelos matem´ticos: a problema de optimizaci´n o
El problema del viajante de comercio Formulaci´n del problema: Un representante de una editorial, con sede en la o ciudad A, debe visitar una serie de clientes establecidos en distintas ciudades de manera que su itinerario tenga como principio y fin A. ¿Qu´ ruta deber´ e ıa seguir con el fin de minimizar costes? Modelizaci´n: Dado un grafo completo yponderado (grafo de distancias), o hallar un ciclo hamiltoniano de coste m´ ınimo (longitud total m´ ınima).

Los grafos como modelos matem´ticos: a ejemplos hist´ricos o

An´lisis de redes el´ctricas (Kirchhoff, 1847) a e

Enumeraci´n de is´meros qu´ o o ımicos (Cayley, 1857)
H H H

H

C

C

C

H

H

H

H

Los grafos como modelos matem´ticos: a problema de optimizaci´n oEl problema del conector m´ ınimo Formulaci´n del problema: Dado un conjunto de ciudades se desea construir o una red de carreteras, que conecte a todas entre s´ ¿Cu´l es la red de coste ı. a m´ ınimo? Modelizaci´n: Dado un grafo conexo y ponderado, hallar un ´rbol generador o a de peso m´ ınimo.

Los grafos como modelos matem´ticos: ejemplo hist´rico a o
El “problema matrimonial” (Hall 1935)Formulaci´n del problema: Tenemos un grupo de chicas y otro de chicos, o ambos con el mismo n´mero de individuos. Algunos de ellos ya se conocen u entre s´ ¿Cu´ndo pueden emparejarse los dos grupos de manera que la chica ı. a y el chico de cada pareja se conozcan previamente? Modelizaci´n: Dado un grafo bipartito, con igual n´mero de v´rtices en cada o u e parte, ¿qu´ condiciones deben cumplirsepara que exista un emparejamiento e perfecto?
d1 d2 d3 d4 h1 h2 h3 h4 √ √ √ √ √ √ √ √

Los grafos como modelos matem´ticos: a problema de optimizaci´n o
El problema del emparejamiento de peso m´ximo a Dado un grafo ponderado, hallar un emparejamiento de peso m´ximo. a

Los grafos como modelos matem´ticos: ejemplo hist´rico a o
El problema de los de cuatro colores (Appel y Haken 1976)Conjetura (Francis Guthrie, 1852): Todo mapa trazado sobre una hoja de papel puede colorearse usando solamente cuatro tintas de manera que “pa´ ıses” con “frontera com´n” tengan colores diferentes. u

Los grafos como modelos matem´ticos: a problema de optimizaci´n o
El problema de los ‘horarios’ Formulaci´n del problema: Confeccionar un calendario de ex´menes, que o a comprenda el m´ ınimo n´mero ded´ teniendo en cuenta que un estudiante u ıas, no puede realizar m´s de un examen en un mismo d´ a ıa. El problema de la asignaci´n de frecuencias en una red celular de o telefon´ m´vil ıa o Formulaci´n del problema: Asignar a cada celda un rango de frecuencias de o manera que celdas contiguas tengan rangos disjuntos (‘bien separados’). ¿Como debe hacerse dicha asignaci´n con el fin de minimizarel total de o frecuencias usadas. Modelizaci´n: Dado el grafo de incompatibilidades, hallar una v´rtice o e coloraci´n del mismo utilizando el menor n´mero de colores posible. o u

Los grafos como modelos matem´ticos: a problema de optimizaci´n o
El problema del camino m´ ınimo (Dijkstra, 1959) Formulaci´n del problema: Dada una red de transporte hallar la ruta ´ptima o o entre cada par de...