SLIDES - Tecnología Digital V Diseño de Algoritmos (7)

Vista previa del material en texto

GRAFOS: APLICACIONES, MODELOS Y PROPIEDADES
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Grafos pesados
Otro atributo importante a la hora de modelar es la posibilidad de asignar
pesos a las distintas componentes del grafo (vértices, arcos).
Sin embargo, los pesos no sólo se utilizan para visualizar información.
También sirven para modelar características importantes del problema que
involucren decisiones.
TD5: Diseño de Algoritmos - UTDT 2
Grafos pesados
Qué pueden representar los pesos en este grafo/digrafo?
Que características cumplen estos pesos?
TD5: Diseño de Algoritmos - UTDT 3
Grafos pesados
Definición
Dado un digrafo 𝐷 = (𝑁, 𝐴), con 𝑁 el conjunto de nodos y 𝐴 el conjunto de
arcos, podemos modelar el peso los ejes mediante una función 𝑤 : 𝐴→ ℝ
que asigna un valor 𝑤𝑖 𝑗 = 𝑤(𝑖 , 𝑗) para (𝑖 , 𝑗) ∈ 𝐴. En otras palabras, podemos
suponer que cada arco del digrafo tiene asociado un número que representa
su peso.
1
2
3
4
5
4
10
5 11
7
5
𝐷 = (𝑉, 𝐴) con
# 𝑉 = {1, 2, 3, 4, 5}, y
# 𝐴 = {(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 3)}
# 𝑤12 = 4, 𝑤13 = 10, 𝑤23 = 5,
𝑤45 = 11, 𝑤34 = 7, 𝑤43 = 5.
Preguntas
# Qué sucede con los pesos en grafos no dirigidos?
# Cómo podemos representar un (di)grafo con pesos?
TD5: Diseño de Algoritmos - UTDT 4
Grafos pesados: representación
Digrafo
1
2
3
4
5
4
10
5 11
7
5
Matriz de adyacencia
𝐴 =

0 4 10 0 0
0 0 5 0 0
0 0 0 7 0
0 0 5 0 11
0 0 0 0 0

Lista de vecinos
1 → {{2 → 4}, {3 → 10}}
2 → {{3 → 5}}
3 → {{4 → 7}}
4 → {{3 → 5}, {5 → 11}}
5 → {}
Pregunta
# Y si un arco / arista tiene más de un atributo?
# Formas de representarlo?
TD5: Diseño de Algoritmos - UTDT 5
Tipos especiales de grafos (1/5)
Definición
Un grafo se dice completo si todos los vértices son adyacentes entre sí.
Dado 𝑛 ∈ ℕ, 𝐾𝑛 es el grafo completo de 𝑛 vértices.
1
2
(a) 𝐾2
1
23
(b) 𝐾3
1
2
3
4
(c) 𝐾4
1
2
34
5
(d) 𝐾5
Preguntas
# Cuántas aristas tiene un grafo completo de 𝑛 vértices?
# Cuántos arcos tiene un digrafo completo de 𝑛 vértices?
TD5: Diseño de Algoritmos - UTDT 6
Tipos especiales de grafos (2/5)
Definición
Dado un grafo 𝐺 = (𝑉, 𝐸), el grafo complemento de 𝐺, que notamos como
�̄� = (𝑉, 𝑋), tiene el mismo conjunto de vértices que 𝐺 y un par de vértices
son adyacentes en �̄� sí y solo sí no son adyacentes en 𝐺. Formalmente,
𝑖 𝑗 ∈ 𝐸 sí y solo sí 𝑖 𝑗 ∉ 𝑋.
1
2
3
4
5
(a) 𝐺 = (𝑉, 𝐸)
1
2
3
4
5
(b) �̄� = (𝑉, 𝑋)
Pregunta
Si 𝐺 tiene 𝑛 vértices y 𝑚 aristas, cuántas aristas tiene �̄�?
TD5: Diseño de Algoritmos - UTDT 7
Tipos especiales de grafos (3/5)
Definición
Un grafo 𝐺 = (𝑉, 𝑋) se dice bipartito si existe una partición 𝑉1 , 𝑉2 del
conjunto de vértices 𝑉 , es decir,
1. 𝑉 = 𝑉1 ∪𝑉2,
2. 𝑉1 ∩𝑉2 = ∅,
3. 𝑉1 ≠ ∅,
4. 𝑉2 ≠ ∅
tal que todas las aristas de 𝐺 tienen un extremo en 𝑉1 y otro en 𝑉2.
1
2
3
4
5
(a) 𝐺 = (𝑉, 𝑋)
1
2
3
4
5
(b) 𝐾2,3
TD5: Diseño de Algoritmos - UTDT 8
Tipos especiales de grafos (3/5)
Definición
Un grafo bipartito 𝐺 = (𝑉, 𝑋) con partición 𝑉1 , 𝑉2 es bipartito completo si
todo vértice en 𝑉1 es adyacente a todo vértice en 𝑉2. Si 𝑛 = 𝑛1 + 𝑛2, con
|𝑉1 | = 𝑛1 y |𝑉2 | = 𝑛2, se denomina con 𝐾𝑛1 ,𝑛2 al grafo bipartito completo.
Teorema
Un grafo es bipartito si y sólo si no tiene circuitos simples de longitud impar.
Preguntas
# Cuántas aristas tiene un grafo bipartito completo?
# Qué aplicación de las que vimos hasta ahora nos permite modelar un
grafo bipartito (eventualmente, completo)?
TD5: Diseño de Algoritmos - UTDT 9
Motivación: Customer Service vs. Customer Experience
En la práctica
En un determinado instante, un conjunto de
usuarios que contactan a soporte al cliente
tienen que ser atendidos por representantes
con diferentes habilidades, experiencia, etc.
Definimos:
# 𝑉1 = {1, . . . , 𝑛1} el conjunto de clientes,
# 𝑉2 = {𝑛1 + 1, . . . , 𝑛1 + 𝑛2} el conjunto de representantes,
# 𝐺 = (𝑉 = 𝑉1 ∪𝑉2 , 𝐸, 𝑤) el grafo bipartito completo 𝐾𝑛1 ,𝑛2 ,
# 𝑤𝑖 𝑗 el beneficio esperado de asignar el representante 𝑗 al cliente 𝑖, 𝑖 𝑗 ∈ 𝐸.
TD5: Diseño de Algoritmos - UTDT 10
Tipos especiales de grafos (4/5)
Definición
Dos grafos 𝐺 = (𝑉, 𝑋) y 𝐺′ = (𝑉′, 𝑋′) se dicen
isomorfos si existe una función biyectiva
𝑓 : 𝑉 → 𝑉′ tal que para todo 𝑣, 𝑤 ∈ 𝑉
(𝑣, 𝑤) ∈ 𝑋 ⇐⇒ ( 𝑓 (𝑣), 𝑓 (𝑤)) ∈ 𝑋′.
1
2
3
4
5
(a) 𝐺 = (𝑉, 𝐸)
3
1
4
5
2
(b) 𝐺′ = (𝑉′ , 𝑋′)
5 4
3
2
1
(c) 𝐺′′ = (𝑉′′ , 𝐸′′)
Intuitivamente
Dos grafos son isomorfos si son esencialmente el mismo grafo salvo un
renombre de los vértices.
TD5: Diseño de Algoritmos - UTDT 11
Tipos especiales de grafos (4/5)
Proposición
Si dos grafos son isomorfos, entonces
# tienen el mismo número de vértices,
# tienen el mismo número de aristas,
# para todo 𝑘, 0 ≤ 𝑘 ≤ 𝑛 − 1, tienen el mismo número de vértices de grado
𝑘,
# tienen el mismo número de componentes conexas,
# para todo 𝑘, 1 ≤ 𝑘 ≤ 𝑛 − 1, tienen el mismo número de caminos simples
de longitud 𝑘.
Preguntas
# Es cierta la recíproca de esta propiedad?
# Hay condiciones necesarias y suficientes fácilmente verificables para ver
si dos grafos son isomorfos?
TD5: Diseño de Algoritmos - UTDT 12
Tipos especiales de grafos (5/5)
Problema
Cursos a dictar y
superposiciones entre cursos.
Cual es el mínimo número
de aulas que necesitamos
para dictar todos los cursos?
Definición
Dado un conjunto de 𝐼 = {𝐼1 , 𝐼2 , . . . , 𝐼𝑘} de intervalos, con 𝐼𝑖 = [𝑠𝑖 , 𝑒𝑖],
𝑠𝑖 ≤ 𝑒𝑖 ∈ ℝ, 𝐺 = (𝑉, 𝐸) es el grafo de intervalos de 𝐼 si:
# 𝐺 tiene un vértice por cada intervalo, i.e. 𝑉 = {1, . . . , 𝑘}; y
# 𝐺 tiene una arista 𝑖 𝑗 ∈ 𝐸 si los intervalos se intersecan, es decir, 𝐼𝑖 ∩ 𝐼𝑗 ≠ ∅.
TD5: Diseño de Algoritmos - UTDT 13
Aplicaciones y modelos
Definición
Dado un grafo 𝐺 = (𝑉, 𝐸), 𝑓 : 𝑉 −→ ℕ es un coloreo de vertices válido
para 𝐺 si 𝑓 (𝑖) ≠ 𝑓 (𝑗) para todo 𝑖 𝑗 ∈ 𝐸.
Intuitivamente, buscamos pintar los vértices (número = color) con colores de
forma tal que vértices adyacentes tengan colores distintos.
1
2
3
4
5
Preguntas
# Es válido el coloreo?
# En caso que lo sea, es mínimo?
# Podemos proveer una cota
superior para el número mínimo
de colores?
# Podemos proveer una cota
inferior para el número mínimo
de colores?
TD5: Diseño de Algoritmos - UTDT 14
Aplicaciones y modelos
Red de telefonía celular
Pregunta: Cuál es el mínimo
número de frecuencias para cubrir
el área sin interferencias?
# Modelamos el problema con
el grafo de interferencias
𝐺 = (𝑉, 𝐸).
# Buscamos un coloreo válido
para 𝐺 con el mínimo número
de colores.
Asignación de aulas
Pregunta: Cuál es el mínimo
número de aulas que necesitamos
para dictar todos los cursos?
# Modelamos el problema con
el grafo de intervalos
𝐺 = (𝑉, 𝐸).
# Buscamos un coloreo válido
para 𝐺 con el mínimo número
de colores.
TD5: Diseño de Algoritmos - UTDT 15
Aplicaciones y modelos
Planificación logística 1.0
Tenemos:
# un conjunto de negocios que realizan ventas diarias en una plataforma;
# un conjunto de puntos de consolidación, donde los vendedores llevan
sus productos para ingresarlos en la red logística;
# una estimación de la distancia a recorrer por cada negocio para entregar
sus productos en un determinado punto de consolidación.
Buscamos asignar cada negocio a exactamente un punto de consolidación
de forma tal que la distancia total recorrida sea mínima.
𝐺 = (𝑉1 ∪𝑉2 , 𝐸) bipartito completo pesado:
# 𝑉1 = conjunto de negocios;
# 𝑉2 = puntos de consolidación;
# 𝑖 𝑗 ∈ 𝐸, 𝑖 ∈ 𝑉1, 𝑗 ∈ 𝑉2;
# 𝑤𝑖 𝑗 = distancia recorrida por 𝑖 hasta 𝑗, 𝑖 𝑗 ∈ 𝐸.
TD5: Diseño de Algoritmos - UTDT 16
Aplicaciones y modelos
Planificación logística 2.0
Al problema anterior le agregamos:
# cada negocio 𝑖 ∈ 𝑉1 tiene un número 𝑑𝑖 de paquetes a entregar;
# cada punto de consolidación 𝑗 ∈ 𝑉2 tiene una capacidad máxima 𝑐 𝑗
(medida en paquetes) que puede recibir;
Buscamos asignar cada negocioa exactamente un punto de consolidación
de forma tal que la distancia total recorrida sea mínima sin exceder la
capacidad.
𝐺 = (𝑉1 ∪𝑉2 , 𝐸) bipartito completo pesado:
# 𝑉1 = conjunto de negocios;
# 𝑉2 = puntos de consolidación;
# 𝑖 𝑗 ∈ 𝐸, 𝑖 ∈ 𝑉1, 𝑗 ∈ 𝑉2;
# 𝑑𝑖 𝑗 = distancia recorrida por 𝑖 hasta 𝑗, 𝑖 𝑗 ∈ 𝐸;
# 𝑐𝑖 = demanda de 𝑖 ∈ 𝑉1;
# 𝑑𝑗 = capacidad de 𝑗 ∈ 𝑉2.
TD5: Diseño de Algoritmos - UTDT 17
Aplicaciones y modelos
En los ejemplos anteriores: ¿qué representa una solución?
TD5: Diseño de Algoritmos - UTDT 18