Flujo en redes

Llamamos red a un grafo orientado $N = (V, X)$ conexo en el que hay dos vértices distinguidos: una fuente $s$ , con grado de salida positivo, y un sumidero $t$ , con grado de entrada positivo. Ademas de los atributos conocidos de un grafo vamos a tener uno nuevo: el flujo.

El flujo es una corriente de una entidad (que depende del contexto) que viaja a traves del grafo. La fuente produce esta corriente de manera indefinida, y el sumidero la consume de igual forma. Los vértices que no son ni la fuente ni el sumidero, no producen ni consumen el material, por lo que la cantidad que entra debe ser igual a la cantidad que sale. El grafo es pesado, pero en este contexto, el peso de cada arista se considera la capacidad maxima de flujo de la misma.

Un ejemplo podria ser una red de cañería, que atraviesa varias ciudades. Los caños son representados por las aristas, y los vértices indican las ciudades. A su vez, cada cañeria tiene su capacidad maxima de liquido. Graficamente, e inventando los numeros, el ejemplo podria verse asi:

flowchart LR

nodeSource((s))
nodeEnd((t))

nodeA((a))
nodeB((b))
nodeC((c))
nodeD((d))

nodeSource -->|2| nodeB
nodeA -->|1| nodeB
nodeA -->|10| nodeC
nodeB -->|2| nodeD
nodeC -->|3| nodeD
nodeC -->|5| nodeEnd
nodeD -->|7| nodeEnd
nodeSource -->|5| nodeA

La idea no se aleja mucho de un digrafo pesado.

Llamamos flujo factible a una función $f : X \to R$ que verifica:

$0 \leq f (e) \leq c (e)$ para toda arista $e \in X$ .
La ley de conversación de flujo, que dice:

\sum_{e \in I n (v)} f (e) = \sum_{e \in O u t (v)} f (e)

para todo vértice $v \in V - {s, t}$ , donde:

I n (v) = {e \in X, e = (w \to v), w \in V}

O u t (v) = {e \in X, e = (v \to w), w \in V}

El valor del flujo es

F = \sum_{e \in I n (v)} f (e) - \sum_{e \in O u t (v)} f (e)

En el ejemplo de antes, un flujo factible (pero no el unico), podria ser:

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

nodeSource -->|2/2| nodeB;
nodeA -->|0/1| nodeB;
nodeA -->|4/10| nodeC;
nodeB -->|2/2| nodeD;
nodeC -->|2/3| nodeD;
nodeC -->|2/5| nodeEnd;
nodeD -->|4/7| nodeEnd;
nodeSource -->|4/5| nodeA;

Una red con valor de flujo

F = 6

, noten como el valor de flujo es igual sobre la fuente o sobre el sumidero (todo lo que entra, debe salir).

Cortes, redes residuales y camino de aumento

Es normal preguntarse si, dada una red $N = (V, X)$ con capacidades en los arcos y dos vértices específicos, una fuente $s$ y un sumidero $t$ , podemos encontrar el valor máximo para el flujo $F$ que se puede enviar desde $s$ hasta $t$ .

En nuestro ejemplo de antes, es facil ver que $F$ no se encuentra maximizado, ya que podriamos definir un flujo de la siguiente manera:

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

nodeSource -->|2/2| nodeB;
nodeA -->|0/1| nodeB;
nodeA -->|5/10| nodeC;
nodeB -->|2/2| nodeD;
nodeC -->|2/3| nodeD;
nodeC -->|3/5| nodeEnd;
nodeD -->|4/7| nodeEnd;
nodeSource -->|5/5| nodeA;

Haciendo que ahora $F = 7$ , que es el valor máximo que podemos lograr en esta situación. Noten que no es la unica forma de lograr ese valor de $F$ , por lo que podrian existir distintos flujos que alcancen el maximo valor de $F$ .

Para resolver el problema del flujo máximo necesitamos definir mas propiedades de las redes.

Llamamos corte en la red $N = (V, X)$ a un subconjunto $S \subseteq V - {t}$ tal que $s \in S$ . En particular, dado una red y un corte, entonces se cumple que:

F = \sum_{e \in S \bar{S}} f (e) - \sum_{e \in \bar{S} S} f (e)

donde $\bar{S} = V - S$ .

Dados

S, T \subseteq V

, definimos

S T = {(u \to v) \in X : u \in S y v \in T}

Todo esto, en criollo, significa que un corte es para una red lo que un subgrafo es para un grafo. Es decir, un corte es una porción de una red. Para contar el valor de $F$ de un corte dado, simplemente contamos la cantidad de flujo que esta escapando del corte, es decir, cuantas flechas

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

subgraph Corte 1
nodeSource;
end

nodeSource -->|2/2| nodeB;
nodeA -->|0/1| nodeB;
nodeA -->|5/10| nodeC;
nodeB -->|2/2| nodeD;
nodeC -->|2/3| nodeD;
nodeC -->|3/5| nodeEnd;
nodeD -->|4/7| nodeEnd;
nodeSource -->|5/5| nodeA;

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

subgraph Corte 2
nodeSource;
nodeA;
end

nodeSource -->|2/2| nodeB;
nodeA -->|0/1| nodeB;
nodeA -->|5/10| nodeC;
nodeB -->|2/2| nodeD;
nodeC -->|2/3| nodeD;
nodeC -->|3/5| nodeEnd;
nodeD -->|4/7| nodeEnd;
nodeSource -->|5/5| nodeA;

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

subgraph Corte 3
nodeSource;
nodeA;
nodeB;
nodeC;
end

nodeSource -->|2/2| nodeB;
nodeA -->|0/1| nodeB;
nodeA -->|5/10| nodeC;
nodeB -->|2/2| nodeD;
nodeC -->|2/3| nodeD;
nodeC -->|3/5| nodeEnd;
nodeD -->|4/7| nodeEnd;
nodeSource -->|5/5| nodeA;

Ejemplos de corte con la red antes expuesta. Noten como todos los cortes cumplen

F = 7

Definimos la capacidad de un corte como la suma de las capacidades de todos las aristas que salen del corte. Por ejemplo, en los dibujos de arriba las capacidades del corte 1, 2 y 3 son 7, 13 y 10 respectivamente. Un problema conocido en redes es el de buscar el corte de capacidad mínima.

Otra definición importante es la de red residual. Dada una red $N = (V, X)$ con función de capacidad $c$ y un flujo factible $f$ , definimos la red residual $R (N, f) = (V, X_{R})$ donde $\forall (v \to w) \in X$ ,

$(v \to w) \in X_{R}$ si $f ((v \to w)) < c ((v \to w))$ .
$(w \to v) \in X_{R}$ si $f ((v \to w)) > 0$ .

Es decir, una red residual es una red que, en base a una red con un flujo factible, indica hacia donde el flujo podria moverse. Nos va a ser util mas adelante para maximizar el valor del flujo final $F$ . Por ver un ejemplo, si tenemos nuestra red de antes (la que cumple $F = 7$ y no tiene cortes), su red residual quedaria:

flowchart LR

nodeSource((s));
nodeEnd((t));

nodeA((a));
nodeB((b));
nodeC((c));
nodeD((d));

nodeC -->|1| nodeD;
nodeA -->|1| nodeB;
nodeA -->|5| nodeC;
nodeC -->|5| nodeA;
nodeD -->|2| nodeB;
nodeD -->|2| nodeC;
nodeC -->|2| nodeEnd;
nodeEnd -->|3| nodeC;
nodeD -->|3| nodeEnd;
nodeEnd -->|4| nodeD;
nodeA -->|5| nodeSource;
nodeB -->|2| nodeSource;

Finalmente, un camino de aumento es un camino orientado de $s$ a $t$ en la red residual $R (N, f)$ . Es decir, un camino en la red residual formada apartir de una red, que vaya desde $s$ a $t$ .