Redes de Flujo: Ford Fulkerson, Grafo Bipartito y Matching, Diseño de Encuestas, Selección de Proyectos Flashcards
Explique cómo se pueden representar los problemas de Redes de Flujo
Los problemas de redes de flujo se pueden representar como grafos donde:
- Los ejes transportan algún tipo de flujo
- Los vértices actúan como conmutador de tráfico entre los diferentes ejes
¿Qué es la capacidad?
La capacidad es la cantidad máxima que un eje puede transportar.
¿Qué es la fuente?
La fuente es el vértice que genera tráfico saliente.
¿Qué es el sumidero?
El sumidero es el vértice que absorbe tráfico entrante.
¿Qué es el flujo?
El flujo es la cantidad transportada por un eje.
Explique la idea de un problema de Redes de Flujo. ¿A qué se le llama capacidad? ¿Qué tipos de nodos tiene el grafo resultante?
Dada una red de flujo, vamos a querer encontrar el flujo de máximo valor posible.
Sea G=(V,E) un grafo dirigido, para todo eje de E vamos a llamar Ce > 0 a su capacidad. Ce es un valor entero.
El grafo tiene un único vértice fuente s y un único vértice sumidero t. El resto son vértices internos.
¿Qué es el flujo s-t?
El flujo es una función f que mapea a cada eje e a un valor real no negativo.
Se debe satisfacer que:
- Para cada eje, el flujo es mayor o igual a cero, y menor o igual a la capacidad: 0 <= f(e) <= Ce.
- Para cada eje del grafo, excluyendo a s y t, la cantidad de flujo generada en la fuente es igual a la cantidad de flujo que sale por el sumidero (flujo, no capacidad).
¿Cómo se realiza el corte del grafo?
Corte del grafo: se dividen los nodos del grafo en dos sets: A y B. Se dice que s pertenece a A y t pertenece a B.
Ford Fulkerson: Defina “grafo residual”
Dada una red de flujo G y un flujo f en G, definimos el grafo residual Gf a:
- Los mismos vértices de G
- Ejes hacia adelante: para cada eje en el que
fe < Ce. Lo incluiremos con una capacidad residualCe-fe. - Ejes hacia atrás: para cada eje
e = (u,v)en el quefe > 0, incluimose'=(v,u)con capacidadfe.
Ford Fulkerson: Defina “cuello de botella”.
Sea P un camino simple s-t en Gf en donde P no visita más de una vez al mismo vértice.
Definimos cuello de botella a la capacidad residual mínima de cualquier eje de P con respecto al flujo f.
Ford Fulkerson: Defina “camino de aumento”.
Llamaremos a P como “camino de aumento”. Podemos incrementar el cuello de botella al flujo de P.
aumento(f,P): Sea b = cuelloDeBotella(P,f) Para cada eje e=(u,v) in P: Si e = (u,v) eje hacia adelante: f(e) += b en G Sino: e' = (v,u) f(e') -= b en G retornar f
Ford Fulkerson: Explique el pseudocódigo y la complejidad.
f(e) = 0 para todo eje e en G
Mientras haya un camino s-t en Gf:
Sea P un camino s-t simple en Gf
f' = aumento(f,P)
Actualizamos f para ser f'
Actualizamos Gf para ser Gf'
Retornar f
Complejidad temporal: O(|E| * F), siendo |E| la cantidad de aristas y F el flujo máximo (la suma de todas las capacidades que salen de la fuente).
Además: En F iteraciones como límite, terminará la ejecución.
Resolver:
Ford-Fulkerson
Nodo_i Nodo_f Capacity
S A 10
S C 10
A B 4
A C 2
A D 8
B T 10
C D 9
D B 6
D T 10
Flujo máximo: 19
Variante Ford Fulkerson: Explique la variante de circulación con demandas
La diferencia en este caso es que cada nodo puede ser productor o consumidor de flujo.
Un nodo que no es ni productor ni consumidor, se le llama conmutador.
Sea una red de flujo G=(V,E):
Cada vector v tiene una demanda dv entera
- Si
dv > 0, entoncesvdemandadvde flujo (es un sumidero). - Si
dv < 0, entoncesvproducedvde flujo (es una fuente). - Si
dv = 0, entoncesves un vertice interno.
El problema requiere determinar si existe una circulación que cumpla con las condiciones de demanda.
Ford-Fulkerson, circulación con demandas: Definir “condición de demanda”.
Se define una condición de demanda como: para cada vector v: f_in(v) - f_out(v) = dv.
