Práctico 10 - Ejercicios 1 y 3.

Práctico 10 - Ejercicios 1 y 3.

de Marco Liguori Hernandez -
Número de respuestas: 4

Buenas,

Tengo un par de dudas respecto a estos dos ejercicios.

Ej1) Me quedó la duda leyendo libro, si para encontrar un corte mínimo es necesario previamente correr Ford-Fulkerson. Entiendo que si ya se corrió FF, se puede hacer BFS o DFS y encontrar todos los nodos alcanzables por el nodo fuente s en el grafo residual, pero en ese caso no estaría entendiendo el fín de encontrar el corte mínimo más que para dar una cota más ajustada que la de la suma de las capacidades saliendo de s = C. 

Dicho de otra manera, ¿que utilidad tendría encontrar un corte de capacidad mínima si ya conozco el valor del flujo máximo (encontrado por ejemplo por el algoritmo de FF)?.

En el caso del ejercicio 1, en la parte b, ¿cómo yo podría saber a priori que el flujo no es máximo en base al corte A={s} y B=V-A de capacidad 3. No me vería obligado a correr FF para realmente hallar ese flujo?.

Ej3) Para demostrar la corrección del algoritmo, ¿Es necesario probar que se cumplen las condiciones de capacidad y de conservación?. Lo que creo que habría que demostrar es que el algoritmo termina y que devuelve la respuesta correcta (true si hay una forma de realizar un traslado, false de lo contrario).

Luego, el tiempo de ejecución me quedó acotado por O(n^{2} x k) ya que el grafo modelado tiene n x k aristas y se ejecuta por a lo sumo por n iteraciones del While de Ford-Fulkerson, ya que el grafo tiene un nodo por cada paciente (esto sería el X del grafo bipartito), y cada arista de p_i a h_j tiene capacidad 1, al igual de las que van de s a cada  p_i. ¿Esta cota es correcta para el tiempo?.

Desde ya muchas gracias, 

Marco.

En respuesta a Marco Liguori Hernandez

Re: Práctico 10 - Ejercicios 1 y 3.

de Jonathan Murana -
Hola Marco, espero estés bien, te respondo entre líneas

Ej1) Me quedó la duda leyendo libro, si para encontrar un corte mínimo es necesario previamente correr Ford-Fulkerson.
Entiendo que si ya se corrió FF, se puede hacer BFS o DFS y encontrar todos los nodos alcanzables por el nodo fuente s en el grafo residual,
pero en ese caso no estaría entendiendo el fín de encontrar el corte mínimo más que para dar una cota más ajustada que la de la suma de las capacidades saliendo de s = C.
Dicho de otra manera, ¿que utilidad tendría encontrar un corte de capacidad mínima si ya conozco el valor del flujo máximo (encontrado por ejemplo por el algoritmo de FF)?.
En el caso del ejercicio 1, en la parte b, ¿cómo yo podría saber a priori que el flujo no es máximo en base al corte A={s} y B=V-A de capacidad 3.
No me vería obligado a correr FF para realmente hallar ese flujo?.

RESPUESTA:
Los razonamientos que planteas son correctos. El ejercicio está planteado de forma incremental para entender primero el concepto de valor de flujo, luego la relación entre corte de capacidad mínima y flujo máximo, y finalmente FF.
No se pide ningún algoritmo en particular para encontrar el corte de capacidad mínima en la parte b, dado el tamaño de la instancia se puede indicar uno y describir las otras posibilidades (de forma exhaustiva).

Ej3) Para demostrar la corrección del algoritmo, ¿Es necesario probar que se cumplen las condiciones de capacidad y de conservación?.
Lo que creo que habría que demostrar es que el algoritmo termina y que devuelve la respuesta correcta
(true si hay una forma de realizar un traslado, false de lo contrario).

RESPUESTA:
Sí, es necesario demostrar que tu reduccion es efectivamente una red de flujo. Si no se demuestra eso no podrías usar FF y estar seguro de llegar al óptimo, porque FF solo devuelve el óptimo en redes de flujo.
En la página 396 del libro hay un ejemplo guía de lo que se debe demostrar en estas reducciones.

Luego, el tiempo de ejecución me quedó acotado por O(n^{2} x k) ya que el grafo modelado tiene n x k aristas y
se ejecuta por a lo sumo por n iteraciones del While de Ford-Fulkerson, ya que el grafo tiene un nodo por cada paciente
(esto sería el X del grafo bipartito), y cada arista de p_i a h_j tiene capacidad 1, al igual de las que van de s a cada p_i.
¿Esta cota es correcta para el tiempo?.

RESPUESTA:
Está bien. La demostración debería ser más ordenada:
1) decir cuántas aristas tiene la red y por qué.
2) decir cual es la cota de flujo máximo y por qué.
3) usar KyT 7.5 (O de FF)


Saludos!
En respuesta a Jonathan Murana

Re: Práctico 10 - Ejercicios 1 y 3.

de Marco Liguori Hernandez -
Buenas Jonathan,

Con respecto al Ej 1: Entiendo lo que dices, básicamente hay que dar todos los cortes mínimos de la red de flujo. Lo que no me termina de quedar claro es: ¿esto se mira sobre el grafo residual o sobre el grafo original?.

Con respecto al Ej 3: En la página 396 (sería 7.11 Project Selection) no encontré algo relacionado directamente con lo que estabamos hablando (¿quizás te referías a la 396 del pdf?).
Más allá de eso, como me imagino que podría probar que el grafo es una red de flujo sería:
Un paciente p_i es asignado a un hospital h_j si existe un camino s- p_i - h_j - t en el grafo residual y a su vez, la arista h_j - t (que tiene capacidad n/k redondeado hacía arriba) no tiene un flujo igual a su capacidad. Por lo tanto, como las aristas s - p y p - h tienen capacidad 1, el flujo se conserva en cada uno de los nodos p (puesto que existe una sola arista entrante a cada p y pueden haber a lo sumo k aristas p - h pero una vez que pasó flujo por un p_i a un h_j, ya no existen caminos s-t que pasen por tal paciente).
Luego, se conserva el flujo en los nodos h pues el flujo que puede atravesar h depende de la capacidad de la arista h-t, por lo tanto, como a lo sumo pueden entrar n aristas y la capacidad de h-t es ceil(n/k) entonces a lo sumo pueden entrar ceil(n/k) unidades de flujo a h.

Con respecto al tiempo de ejecución: en el punto (2) ¿bastaría con ver que el flujo máximo es C = capacidad de las aristas salientes de s = n (una por cada paciente, cada una capacidad = 1) y por lo tanto el v(f) <= C o habría que usar otro/s argumentos?.

Muchas gracias,
Marco.
En respuesta a Marco Liguori Hernandez

Re: Práctico 10 - Ejercicios 1 y 3.

de Jonathan Murana -
Buenas! seguimos abajo

Con respecto al Ej 1: Entiendo lo que dices, básicamente hay que dar todos los cortes mínimos de la red de flujo.
Lo que no me termina de quedar claro es: ¿esto se mira sobre el grafo residual o sobre el grafo original?.

RESPUESTA:
Sobre el grafo original.

Con respecto al Ej 3: En la página 396 (sería 7.11 Project Selection) no encontré algo relacionado
directamente con lo que estabamos hablando (¿quizás te referías a la 396 del pdf?).
Más allá de eso, como me imagino que podría probar que el grafo es una red de flujo sería:
Un paciente p_i es asignado a un hospital h_j si existe un camino s- p_i - h_j - t en el grafo residual
y a su vez, la arista h_j - t (que tiene capacidad n/k redondeado hacía arriba) no tiene un flujo igual a su capacidad. Por lo tanto, como las aristas s - p y p - h tienen capacidad 1, el flujo se conserva en cada uno de los nodos p (puesto que existe una sola arista entrante a cada p y pueden haber a lo sumo k aristas p - h pero una vez que pasó flujo por un p_i a un h_j, ya no existen caminos s-t que pasen por tal paciente).
Luego, se conserva el flujo en los nodos h pues el flujo que puede atravesar h depende
de la capacidad de la arista h-t, por lo tanto, como a lo sumo pueden entrar n aristas
y la capacidad de h-t es ceil(n/k) entonces a lo sumo pueden entrar ceil(n/k) unidades de flujo a h.

RESPUESTA:
La página era 369 disculpas, es donde esta la proposición 7.37. Al comienzo de la página.
No seria el residual ahí, te planteo un poco la idea a continuación, un poco incompleta
En el directo, que es donde hay que mostrar que se modela una red de flujo,
tu hipótesis es que hay una solución al problema de matching válida, no podes mezclar.
(=>)
Si hay una forma válida de enviar pacientes a los hospitales, es decir que hay un matching válido entre pacientes y hospitales, entonces podemos enviar una unidad de flujo por cada camino s-p_i-h_j-t (pasando por cada arista del matching). Se cumple la conservación
si a cada nodo (distinto de s y t) llega el mismo flujo que sale:
A cada nodo paciente llega una unidad y sale una unidad (camino siguiendo s-p_i),
a cada nodo hospital llega una unidad por paciente asignado (caminos siguiendo los matching de s-p_i-h_j) y sale la suma por construcción de la red.
Se cumple la capacidad porque si el matching es válido,
ningún nodo hospital supera su capacidad de salida porque no recibe más de n/k unidades de flujo (por qué? y que pasa con las otras capacidades?).
Y por qué este flujo es máximo para la red para que FF lo encuentre?
(<=)
...


Con respecto al tiempo de ejecución: en el punto (2) ¿bastaría con ver que el flujo máximo
es C = capacidad de las aristas salientes de s = n (una por cada paciente, cada una capacidad = 1)
y por lo tanto el v(f) <= C o habría que usar otro/s argumentos?.

RESPUESTA:
Eso es suficiente

Muchas gracias,
Marco.