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.
Ford-Fulkerson, circulación con demandas: Explique la reducción del problema a uno de flujo máximo
Lo que vamos a hacer es crear una “super fuente” y un “super sumidero”. Los vamos a llamar S* y T*.
Entonces:
- Para cada vector con
dv > 0, creamos el ejee=(v,T*)con capacidadC(e) = dv. - Para cada vector con
dv < 0, creamos el ejee=(S*,v)con capacidadC(e) = -dv.
Básicamente, creamos una fuente y a cada vértice con demanda negativa (productor), lo enchufamos con esa fuente, y el valor del flujo del eje va a ser la misma demanda (positiva).
Lo mismo con el sumidero: creamos uno y a cada vértice con demanda positiva (consumidor) lo enchufamos a ese sumidero, y el valor del flujo del eje va a ser el mismo que el de la demanda.
Luego, resolvemos el flujo máximo.
Ford-Fulkerson: Explique la variante de circulación con demandas y límite inferior.
Se agrega una nueva condición: ciertos ejes tienen que tener un flujo mínimo.
Lo que se hace es reducir primero al problema de circulación con demandas y luego al problema de flujo máximo.
Vamos a crear un G* ficticio en donde forzamos que los ejes con límite tengan ese valor.
Cada eje entonces cambiará su capacidad en Ce-Le y cada vértice cambiará su demanda en dv-Lv, siendo:
Lv = Sumatoria (e in v) Le + Sumatoria (e out v) Le
donde Lv va a ser la sumatoria del límite inferior de todos los ejes que ingresan a ese nodo v, menos la sumatoria del límite inferior de todos los ejes que salen del nodo v.
Grafo Bipartito y Matching: Explique el problema
Dado un grafo G=(V,E) no dirigido, es bipartito si se puede dividir V=X+Y tal que cada eje de E sale de X y llega a Y.
Un matching M en G es el subconjunto de ejes tal que cada nodo aparece como mucho en un eje.
Queremos encontrar el set M del mayor tamaño posible.
Grafo Bipartito y Matching: Resolviendo con flujo máximo.
Podemos construir una red de flujo G' tal que las capacidades de cada eje es de 1, y agregamos un nodo s y otro nodo t, tratando de ir de los nodos de X a Y de la siguiente forma:
S -> X -> Y -> T
Si obtenemos el flujo máximo s-t, el valor del mismo es igual al tamaño del matching máximo.
Luego, podemos usar el flujo mismo para recuperar el matching: aquellos ejes que van de X a Y con un flujo en 1 (para utilizar una sola vez cada eje) forman pareja.
La suma del flujo de los ejes que salen de s indican la cantidad de parejas formadas: si hay k ejes, sabemos que tenemos k parejas formadas.
Diseño de Encuestas: Explique el problema
Sean:
- k productos que vende una empresa
- n clientes que realizaron compras a la empresa.
Se desea construir una encuesta de satisfacción personalizada.
Se tienen las siguientes restricciones:
- Cada cliente puede responder únicamente por producto que haya comprado.
- El cliente i puede responder consultas entre ci y ci' productos.
- El producto j debe tener entre pj y pj' respuestas de clientes.
Diseño de Encuestas: Explique el análisis del problema, ¿qué tipo de grafo podemos construir? ¿Con qué restricciones?
- Cada cliente compró un subconjunto de productos.
- Cada producto fue comprado por un subconjunto de cleintes.
Esto se puede modelizar como conjuntos disjuntos. Existe una relación entre un elemento i del conjunto “cliente” y j del conjunto producto si i compró a j.
Con esto podemos construir un grafo bipartito, usando los conjuntos y la relación entre ellos.
Para construir las encuestas, se deben cumplir con las restricciones:
- Para el cliente i, tenemos que elegir un subconjunto x de sus “relaciones” tal que Ci ≤ |x| ≤ Ci'.
- Para el producto j tenemos que elegir un subconjunto y de sus “relaciones” tal que Pj ≤ |y| ≤ Pj'
Diseño de Encuestas: Transformando el problema en uno de Flujo Máximo. ¿Cómo se interpretan los resultados?
- Cada cliente y producto es un nodo
- Cada relación cliente-producto define un eje de capacidad 1 entre el cliente y el producto.
- Agregamos un nodo ficticio
sy otro nodo ficticiot. - Por cada cliente
i, agregamos un ejes-icon capacidadCi'y límite inferiorCi. - Hacemos lo mismo para t: agregamos un eje de los productos a
t, con capacidadPi'y límite inferiorPi. - Agregamos un eje
t-scon capacidadsumatoria(Ci')y límite inferiorsumatoria(Ci).
Todos los nodos tendrán inicialmente demanda cero. Pero como tiene límites, van a eventualmente adaptar esa demanda.
Este problema se reduce a un problema de circulación con demanda. Al final:
- El flujo en eje s-t contiene la cantidad total de preguntas a realizar.
- El flujo de cada s-cicontiene cuántas preguntas debe contestar el cliente i.
- El flujo de cada pj-t contiene cuántas preguntas se realizan al producto j.
Aquellos ejes ci-pj con flujo 1 corresponden a preguntar al cliente i sobre el producto j.
Selección de Proyectos: Describir el problema
Tengo un conjunto de proyectos, donde para hacer unos, tengo que previamente hacer otros.
Cada proyecto i cuenta con un retorno económica de pi (número positivo o negativo) y puede tener un subconjunto de problemas que son prerequisitos para su ejecución.
Queremos seleccionar un subconjunto de proyectos que maximice la ganancia.
Selección de Proyectos: Explique qué es un grafo de precedencia.
Podemos representar las relaciones entre proyectos en un grafo G=(V,E), donde los ejes dirigidos representan las precedencias:
p1 -> p3 indica que el proyecto 1 debe realizarse antes que el proyecto 3.
Selección de Proyectos: Explique el concepto de Factibilidad de Proyectos
Un subconjunto de proyectos A de P es factible si los prerequisitos de cada proyecto en A también pertenecen a A.
Selección de Proyectos: Explique el concepto de Ganancia
Dado un subconjunto de proyectos factibles A, llamaremos Ganancia de A a la suma de los retornos de cada uno de los proyectos que lo compone.
Ganancia(A) = sumatoria(pi)
Para todos los proyectos con retorno positivo, llamaremos tope ganancia C a la suma de los retornos de esos proyectos:
C(A) = sumatoria(pi) ; si pi > 0
Selección de Proyectos: Construcción de Red de Flujos
- Agregamos un nodo
scomo fuente y otro nodotcomo sumidero. Vamos a tener un nodo por cada proyecto. - Por cada nodo
iconpi > 0, agregar un ejes-icon capacidadpi. - Por cada nodo
iconpi < 0, agregar un ejei-tcon capacidad-pi - Por cada relación
jque precede ai, agregar un ejei-jcon capacidadC+1(tope ganancia).
De esta forma, se “invierte” el gráfico. Aquellas tareas con ganancia positiva, van a priorizarse. Las relacinoes van a invertirse. La capacidad de esos ejes invertidos va a ser la capacidad máxima.
La capacidad de los nodos con ganancia negativa al nodo sumidero es el valor absoluto de la ganancia.
Selección de Proyectos: Explique el corte mínimo
Afirmamos que el corte mínimo s-t corresponde a la ganancia máxima obtenida. Siendo C(A',B') el corte mínimo, los proyectos en A' - {s} corresponden a los proyectos a ejecutar para maximizar la ganancia.
C(A',B') = C - Ganancia(A')
Resuelva: Ford Fulkerson
Eje Capacidad
S-A 5
S-C 20
A-B 5
A-D 10
B-T 5
C-B 5
C-F 8
D-C 2
D-E 10
F-G 9
G-T 8
E-T 10
Solución: 18
Resolver:
Demanda y Límite
Nodo Destino Capacidad Demanda(Nodo) Límite A F 10 -20 5 A B 10 -20 no tiene B C 30 0 no tiene F B 10 0 2 C - - 30 -
Solución: 20
Resolver: Grafo bipartito y Matching
Conjunto A: [a,b,c,d,e]
Conjunto B: [1,2,3,4,5]
Ejes: [(a,1), (a,2), (b,1), (c,2), (c,3), (d,3), (d,4), (d,5), e,5)]
Solución:
[(a,2), (b,1), (c,3), (d,4), (e,5)]
Resolver
Selección de Proyectos
p1-> p3
p1 -> p4
p2 -> p4
p2 -> p5
p5 -> p6
Ganancias:
(p1, p2, p3, p4, p5, p6) = (-3, -1, 5, 3, 1, -4)
Ganancia(A) = 4
Corte mínimo = Ganancia máx obtenida = 9 - 5 = 4
