Grafos

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 cartero chino (Kwan Mei-Ko, 1960)
Formulaci´n del problema: Un cartero debe repartirla 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 como modelos matem´ticos:
a
problema de optimizaci´n
o
El problema delviajante 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 y ponderado (grafo de distancias),
o
hallar un ciclohamiltoniano 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
o
El problema del conector m´
ınimoFormulaci´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 delproblema: 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 cumplirse para queexista 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 Haken1976)
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
acomprenda el m´
ınimo n´mero de d´ 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 hacersedicha asignaci´n con el fin de minimizar el 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...