Flujo máximo - Ford-Fulkerson y Edmonds-Karp

El algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular un flujo máximo en una red de flujo.

Red de flujo

Primero definamos qué es una red de flujo (flow network), un flujo y un flujo máximo.

Una red es un grafo dirigido $G$ con vértices $V$ y aristas $E$ combinado con una función $c$ , que asigna a cada arista $e \in E$ un valor entero no negativo, la capacidad de $e$ . Tal red se llama red de flujo si además etiquetamos dos vértices, uno como fuente (source) y otro como sumidero (sink).

Un flujo en una red de flujo es una función $f$ , que otra vez asigna a cada arista $e$ un valor entero no negativo, a saber el flujo. La función tiene que cumplir las siguientes dos condiciones:

El flujo de una arista no puede exceder la capacidad.

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

Y la suma del flujo entrante de un vértice $u$ tiene que ser igual a la suma del flujo saliente de $u$ excepto en los vértices fuente y sumidero.

$\sum_{(v, u) \in E} f((v, u)) = \sum_{(u, v) \in E} f((u, v))$

El vértice fuente $s$ solo tiene flujo saliente, y el vértice sumidero $t$ solo tiene flujo entrante.

Es fácil ver que se cumple la siguiente ecuación:

$\sum_{(s, u) \in E} f((s, u)) = \sum_{(u, t) \in E} f((u, t))$

Una buena analogía para una red de flujo es la siguiente visualización: Representamos las aristas como tuberías de agua, la capacidad de una arista es la cantidad máxima de agua que puede fluir por la tubería por segundo, y el flujo de una arista es la cantidad de agua que fluye actualmente por la tubería por segundo. Esto motiva la primera condición de flujo. No puede fluir más agua por una tubería que su capacidad. Los vértices actúan como uniones, donde el agua sale de algunas tuberías y luego estos vértices distribuyen el agua de alguna forma a otras tuberías. Esto también motiva la segunda condición de flujo. Toda el agua entrante tiene que distribuirse a las otras tuberías en cada unión. No puede desaparecer ni aparecer mágicamente. La fuente $s$ es el origen de toda el agua, y el agua solo puede drenar en el sumidero $t$ .

La siguiente imagen muestra una red de flujo. El primer valor de cada arista representa el flujo, que inicialmente es 0, y el segundo valor representa la capacidad.

El valor del flujo de una red es la suma de todos los flujos que se producen en la fuente $s$ , o de forma equivalente la suma de todos los flujos que consume el sumidero $t$ . Un flujo máximo es un flujo con el valor máximo posible. Encontrar este flujo máximo de una red de flujo es el problema que queremos resolver.

En la visualización con tuberías de agua, el problema se puede formular de la siguiente forma: ¿cuánta agua podemos empujar por las tuberías desde la fuente hasta el sumidero?

La siguiente imagen muestra el flujo máximo en la red de flujo.

Método de Ford-Fulkerson

Definamos una cosa más. Una capacidad residual de una arista dirigida es la capacidad menos el flujo. Hay que notar que si hay un flujo a lo largo de alguna arista dirigida $(u, v)$ , entonces la arista inversa tiene capacidad 0 y podemos definir su flujo como $f((v, u)) = -f((u, v))$ . Esto también define la capacidad residual para todas las aristas inversas. Podemos crear una red residual a partir de todas estas aristas, que es simplemente una red con los mismos vértices y aristas, pero usamos las capacidades residuales como capacidades.

El método de Ford-Fulkerson funciona de la siguiente forma. Primero, ponemos el flujo de cada arista en cero. Luego buscamos un camino aumentante (augmenting path) de $s$ a $t$ . Un camino aumentante es un camino simple en el grafo residual donde la capacidad residual es positiva para todas las aristas a lo largo de ese camino. Si se encuentra tal camino, entonces podemos aumentar el flujo a lo largo de estas aristas. Seguimos buscando caminos aumentantes y aumentando el flujo. Una vez que ya no existe un camino aumentante, el flujo es máximo.

Especifiquemos con más detalle qué significa aumentar el flujo a lo largo de un camino aumentante. Sea $C$ la menor capacidad residual de las aristas del camino. Luego aumentamos el flujo de la siguiente forma: actualizamos $f((u, v)) \text{+=} C$ y $f((v, u)) \text{-=} C$ para cada arista $(u, v)$ del camino.

Aquí hay un ejemplo para demostrar el método. Usamos la misma red de flujo de arriba. Inicialmente empezamos con un flujo de 0.

Podemos encontrar el camino $s - A - B - t$ con las capacidades residuales 7, 5 y 8. Su mínimo es 5, por lo tanto podemos aumentar el flujo a lo largo de este camino en 5. Esto da un flujo de 5 para la red.

Otra vez buscamos un camino aumentante; esta vez encontramos $s - D - A - C - t$ con las capacidades residuales 4, 3, 3 y 5. Por lo tanto podemos aumentar el flujo en 3 y obtenemos un flujo de 8 para la red.

Esta vez encontramos el camino $s - D - C - B - t$ con las capacidades residuales 1, 2, 3 y 3, y por tanto aumentamos el flujo en 1.

Esta vez encontramos el camino aumentante $s - A - D - C - t$ con las capacidades residuales 2, 3, 1 y 2. Podemos aumentar el flujo en 1. Pero este camino es muy interesante. Incluye la arista inversa $(A, D)$ . En la red de flujo original no se nos permite enviar ningún flujo de $A$ a $D$ . Pero como ya tenemos un flujo de 3 de $D$ a $A$ , esto es posible. La intuición es la siguiente: En lugar de enviar un flujo de 3 de $D$ a $A$ , solo enviamos 2 y lo compensamos enviando un flujo adicional de 1 de $s$ a $A$ , lo que nos permite enviar un flujo adicional de 1 a lo largo del camino $D - C - t$ .

Ahora es imposible encontrar un camino aumentante entre $s$ y $t$ , por lo tanto este flujo de $10$ es el máximo posible. Hemos encontrado el flujo máximo.

Hay que notar que el método de Ford-Fulkerson no especifica un método para encontrar el camino aumentante. Enfoques posibles son usar DFS o BFS, que ambos funcionan en $O(E)$ . Si todas las capacidades de la red son enteras, entonces para cada camino aumentante el flujo de la red aumenta en al menos 1 (para más detalles véase Teorema del flujo integral). Por lo tanto, la complejidad de Ford-Fulkerson es $O(E F)$ , donde $F$ es el flujo máximo de la red. En el caso de capacidades racionales, el algoritmo también termina, pero la complejidad no está acotada. En el caso de capacidades irracionales, el algoritmo podría no terminar nunca, y podría ni siquiera converger al flujo máximo.

Algoritmo de Edmonds-Karp

El algoritmo de Edmonds-Karp es simplemente una implementación del método de Ford-Fulkerson que usa BFS para encontrar caminos aumentantes. El algoritmo fue publicado primero por Yefim Dinitz en 1970, y luego publicado de forma independiente por Jack Edmonds y Richard Karp en 1972.

La complejidad se puede dar de forma independiente del flujo máximo. El algoritmo corre en tiempo $O(V E^2)$ , incluso para capacidades irracionales. La intuición es que cada vez que encontramos un camino aumentante una de las aristas se satura, y la distancia de la arista a $s$ será mayor si aparece más tarde otra vez en un camino aumentante. La longitud de los caminos simples está acotada por $V$ .

Implementación

La matriz capacity guarda la capacidad de cada par de vértices. adj es la lista de adyacencia del grafo no dirigido, ya que también tenemos que usar las inversas de las aristas dirigidas cuando buscamos caminos aumentantes.

La función maxflow devolverá el valor del flujo máximo. Durante el algoritmo, la matriz capacity de hecho guardará la capacidad residual de la red. El valor del flujo en cada arista de hecho no se guardará, pero es fácil extender la implementación —usando una matriz adicional— para guardar también el flujo y devolverlo.


int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;

int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(n);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}

Teorema del flujo integral ## { #integral-theorem}

El teorema dice que si toda capacidad de la red es un entero, entonces el tamaño del flujo máximo es un entero, y existe un flujo máximo tal que el flujo en cada arista también es un entero. En particular, el método de Ford-Fulkerson encuentra un flujo de ese tipo.

Teorema de flujo máximo-corte mínimo

Un $s$ - $t$ -corte es una partición de los vértices de una red de flujo en dos conjuntos, tal que un conjunto incluye la fuente $s$ y el otro incluye el sumidero $t$ . La capacidad de un $s$ - $t$ -corte se define como la suma de las capacidades de las aristas del lado de la fuente al lado del sumidero.

Obviamente, no podemos enviar más flujo de $s$ a $t$ que la capacidad de cualquier $s$ - $t$ -corte. Por lo tanto, el flujo máximo está acotado por la capacidad del corte mínimo.

El teorema de flujo máximo-corte mínimo va aún más lejos. Dice que la capacidad del flujo máximo tiene que ser igual a la capacidad del corte mínimo.

En la siguiente imagen se puede ver el corte mínimo de la red de flujo que usamos antes. Muestra que la capacidad del corte ${s, A, D}$ y ${B, C, t}$ es $5 + 3 + 2 = 10$ , que es igual al flujo máximo que encontramos. Otros cortes tendrán una capacidad mayor, como la capacidad entre ${s, A}$ y ${B, C, D, t}$ es $4 + 3 + 5 = 12$ .

Un corte mínimo se puede encontrar después de realizar un cálculo de flujo máximo usando el método de Ford-Fulkerson. Un posible corte mínimo es el siguiente: el conjunto de todos los vértices que se pueden alcanzar desde $s$ en el grafo residual (usando aristas con capacidad residual positiva), y el conjunto de todos los demás vértices. Esta partición se puede encontrar fácilmente usando DFS empezando en $s$ .