Flujos con demandas

En una red de flujo normal el flujo de una arista solo está limitado por la capacidad $c(e)$ por arriba y por 0 por abajo. En este artículo discutiremos redes de flujo en las que además exigimos que el flujo de cada arista tenga una cierta cantidad, es decir, acotamos el flujo por abajo con una función de demanda (demand) $d(e)$:

$$d(e) \le f(e) \le c(e)$$

Así, a continuación cada arista tiene un valor de flujo mínimo, que tenemos que pasar a lo largo de la arista.

Esta es una generalización del problema de flujo normal, ya que poner $d(e) = 0$ para todas las aristas $e$ da una red de flujo normal. Nótese que en la red de flujo normal es extremadamente trivial encontrar un flujo válido: poner $f(e) = 0$ ya es uno válido. Sin embargo, si el flujo de cada arista tiene que satisfacer una demanda, de pronto encontrar un flujo válido ya es bastante complicado.

Consideraremos dos problemas:

1. encontrar un flujo arbitrario que satisfaga todas las restricciones
2. encontrar un flujo mínimo que satisfaga todas las restricciones

Encontrar un flujo arbitrario

Hacemos los siguientes cambios en la red. Agregamos una fuente nueva $s’$ y un sumidero nuevo $t’$, una arista nueva de la fuente $s’$ a cada otro vértice, una arista nueva de cada vértice al sumidero $t’$, y una arista de $t$ a $s$. Además definimos la función de capacidad nueva $c’$ como:

• $c’((s’, v)) = \sum_{u \in V} d((u, v))$ para cada arista $(s’, v)$.
• $c’((v, t’)) = \sum_{w \in V} d((v, w))$ para cada arista $(v, t’)$.
• $c’((u, v)) = c((u, v)) - d((u, v))$ para cada arista $(u, v)$ en la red vieja.
• $c’((t, s)) = \infty$

Si la red nueva tiene un flujo saturante (un flujo donde cada arista saliente de $s’$ está completamente llena, lo cual es equivalente a que cada arista entrante a $t’$ esté completamente llena), entonces la red con demandas tiene un flujo válido, y el flujo real se puede reconstruir fácilmente a partir de la red nueva. En caso contrario no existe un flujo que satisfaga todas las condiciones. Como un flujo saturante tiene que ser un flujo máximo, se puede encontrar con cualquier algoritmo de flujo máximo, como el algoritmo de Edmonds-Karp o el algoritmo Push-relabel.

La corrección de estas transformaciones es más difícil de entender. Podemos pensarlo de la siguiente forma: Cada arista $e = (u, v)$ con $d(e) > 0$ se reemplaza originalmente por dos aristas: una con la capacidad $d(i)$, y la otra con $c(i) - d(i)$. Queremos encontrar un flujo que sature la primera arista (es decir, el flujo a lo largo de esta arista debe ser igual a su capacidad). La segunda arista es menos importante: el flujo a lo largo de ella puede ser cualquier cosa, asumiendo que no exceda su capacidad. Consideremos cada arista que tiene que saturarse, y realizamos la siguiente operación: dibujamos la arista de la fuente nueva $s’$ a su extremo $v$, dibujamos la arista de su inicio $u$ al sumidero nuevo $t’$, quitamos la arista misma, y del sumidero viejo $t$ a la fuente vieja $s$ dibujamos una arista de capacidad infinita. Con estas acciones simulamos el hecho de que esta arista está saturada: de $v$ saldrá adicionalmente un flujo $d(e)$ (lo simulamos con una fuente nueva que alimenta la cantidad correcta de flujo a $v$), y $u$ también empujará $d(e)$ de flujo adicional (pero en lugar de a lo largo de la arista vieja, este flujo irá directamente al sumidero nuevo $t’$). Un flujo con el valor $d(e)$, que originalmente fluía a lo largo del camino $s - \dots - u - v - \dots t$ ahora puede tomar el camino nuevo $s’ - v - \dots - t - s - \dots - u - t’$. Lo único que se simplificó en la definición de la red nueva es que si el procedimiento creó múltiples aristas entre el mismo par de vértices, entonces se combinan en una sola arista con la capacidad sumada.

Flujo mínimo

Nótese que a lo largo de la arista $(t, s)$ (del sumidero viejo a la fuente vieja) con la capacidad $\infty$ fluye todo el flujo de la red vieja correspondiente. Es decir, la capacidad de esta arista afecta el valor del flujo de la red vieja. Al dar a esta arista una capacidad suficientemente grande (es decir, $\infty$), el flujo de la red vieja no está limitado. Al limitar esta arista con capacidades más pequeñas, el valor del flujo disminuirá. Sin embargo, si limitamos esta arista con un valor demasiado pequeño, entonces la red no tendrá una solución saturada, p. ej. la solución correspondiente para la red original no satisfará la demanda de las aristas. Obviamente aquí se puede usar una búsqueda binaria para encontrar el menor valor con el cual todas las restricciones siguen satisfechas. Esto da el flujo mínimo de la red original.