Redes de flujo

[alvaro.martin]

Buenas tardes, tengo una consulta respecto al corte mínimo en las redes de flujo. Mi duda va por el lado de que cuando dieron el tema dijeron que una utilidad de las aristas sobre las que se corta, es que allí es donde (en el ejemplo de una tuberia) se debe invertir dinero para aumentar la capacidad, y que esto repercuta en el aumento de flujo. Suponiendo el ejemplo que dieron en su momento, que el flujo máximo era 3 pero era posible aumentarlo ya que las aristas de salida de la fuente tenían mas capacidad, para aprovechar al maximo esa capacidad ¿que debo hacer? Yo probe aumentando la capacidad en las aristas del corte mínimo de tal forma que la suma de ambas me de la capacidad de salida de la fuente, pero esto no me funcionó, ya que el flujo aumentaba pero no a tope. Luego se me ocurrió probar sumando pero manteniendo la proporción de las aristas de corte mínimo, es decir, si la capacidad de A->B era 1 y la capacidad de C->D era 2, el flujo maximo actual es 3 y quiero llevarlo a 9, aumentar a 3 y 6 respectivamente. Pero esto tampoco me funcionó. ¿Cual sería la forma correcta, si es que la hay? Gracias de antemano!!!

Saludos,

Alvaro

[Martín Buchwald]

Hola Álvaro, 

No hay una respuesta segura. Esta es sólo una aplicación en el sentido "por acá te conviene", pero puede ser que no sea suficiente para mejorar el flujo siquiera (pero ahí simplemente volvemos a aplicar el mismo criterio para encontrar las nuevas aristas de corte). Cómo llegar al tope, suena como un problema más complejo, y posiblemente combinatorio, así que ya se escapa un tanto. 

--
Cómo usar esta lista: https://tiny.cc/algo2-lista-doc
---
Has recibido este mensaje porque estás suscrito al grupo "fiuba-7541rw-alu" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a fiuba-7541rw-a...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fiuba-7541rw-alu/0b355eeb-c7d1-4ab4-b3b0-78fd36addf0dn%40googlegroups.com.