Flujo con cotas inferiores

Tutorial

Hasta ahora, cada arista de nuestra red de flujo tenía una capacidad que sirve como cota superior del flujo que pasa por ella: $0 \le f(e) \le c(e)$. Ahora consideramos redes donde cada arista $e$ tiene además una cota inferior $\ell(e)$, de modo que cualquier flujo válido debe satisfacer

En otras palabras, ahora estamos obligados a empujar al menos $\ell(e)$ unidades de flujo por $e$. Esta única extensión es sorprendentemente potente: muchos problemas que no se parecen en nada a flujo (“cada tarea debe realizarse al menos $x$ veces”, “cada persona canta entre $a$ y $b$ canciones”) se reducen a ella.

Circulación factible

Empecemos por la versión más simple, en la que no hay fuente ni sumidero. Una circulación es una asignación de flujo a cada arista tal que

• cada arista respeta sus cotas: $\ell(e) \le f(e) \le c(e)$, y
• la conservación se cumple en todo vértice: el flujo que entra es igual al que sale.

La pregunta es si existe alguna circulación válida.

Primero ilustramos el grafo de flujo que podemos armar para resolver este problema y luego explicamos por qué funciona. Primero, creamos dos nodos nuevos $S$ y $T$ y conectamos $T \rightarrow S$ con capacidad $\infty$. Luego, aplicamos la siguiente transformación a cada arista $e = u \rightarrow v$:

• Conectamos $u \rightarrow T$ y $S \rightarrow v$ con capacidad $l(e)$.
• Reducimos la capacidad de $u \rightarrow v$ a $c(e) - l(e)$.

La idea es que, en esta red transformada, el flujo por $e$ se enruta primero por el ciclo azul ($u \rightarrow T \rightarrow S \rightarrow v$) hasta saturar las $l(e)$ unidades, y solo el exceso pasa por $e$ misma. Esto implica que todas las cotas inferiores se satisfacen si y solo si todas las aristas azules están saturadas. Para determinar si esto es posible, basta correr un flujo máximo de $S$ a $T$ y comprobar si el flujo resultante es exactamente $\sum l(e)$.

Para recuperar la circulación real, tomamos el flujo $g(e)$ hallado en la red auxiliar y le sumamos de nuevo la cota inferior: $f(e) = g(e) + \ell(e)$.

Flujo factible con fuente y sumidero

Ahora supongamos que sí tenemos una fuente $s$ y un sumidero $t$, y queremos cualquier flujo de $s$ a $t$ que respete las cotas inferiores. La restricción de conservación debe cumplirse en todos lados excepto $s$ y $t$.

Reducimos esto al caso de circulación con una arista extra: agregamos una arista de $t$ de vuelta a $s$ con cota inferior $0$ y capacidad $\infty$. Esta “arista de retorno” lleva el valor neto del flujo del sumidero a la fuente, de modo que la conservación también se cumple en $s$ y $t$, y toda la red se convierte en un problema de circulación. Aplicamos la construcción de arriba, y el valor del flujo de la red original es exactamente el flujo enviado por la arista $t \to s$.

Flujo máximo / mínimo con cotas inferiores

A menudo no queremos solo un flujo factible: queremos el flujo máximo (o mínimo) de $s$ a $t$ sujeto a las cotas inferiores. Se hace en dos fases:

1. Hallar un flujo factible usando la construcción de arriba. Si las aristas azules no se pueden saturar, no existe un flujo válido y nos detenemos.

2. Aumentar en la red residual. Quitamos los $S$ y $T$ auxiliares y la arista $t \to s$, y luego corremos un flujo máximo ordinario de $s$ a $t$ sobre el grafo residual que queda. Sumar estos caminos aumentantes al flujo factible lo mantiene factible (solo incrementamos flujo en aristas que tienen capacidad de sobra) a la vez que empujamos el valor $s \to t$ tan alto como sea posible.

   Para flujo mínimo, en cambio corremos un flujo máximo de $t$ a $s$ en el grafo residual y lo restamos: cancelamos tanto flujo circulante como sea posible manteniendo cada arista por encima de su cota inferior.

Problemas