Fluxo Máximo: Ford-Fulkerson, Edmonds-Karp e Dinic

Published

16/06/2026

Modified

03/06/2026

1. O Problema do Encanamento

Temos uma rede de tubulações conectando uma represa (Fonte \(s\)) a uma cidade (Sorvedouro \(t\)). Cada cano tem um diâmetro (Capacidade) diferente. Qual é a quantidade máxima de água que consegue chegar na cidade por segundo?

Este é o Problema do Fluxo Máximo — um dos problemas mais fundamentais em grafos, com aplicações que vão desde redes de transporte e telecomunicações até segmentação de imagens e bioinformática.

2. Definição Formal: Rede de Fluxo

Uma Rede de Fluxo é um grafo dirigido \(G = (V, E)\) com:

  • Uma fonte \(s \in V\): vértice onde o fluxo é produzido.
  • Um sorvedouro \(t \in V\): vértice onde o fluxo é consumido.
  • Uma função de capacidade \(c : V \times V \to \mathbb{R}_{\geq 0}\), onde \(c(u,v) = 0\) se \((u,v) \notin E\).
  • Sem arestas anti-paralelas: se \((u,v) \in E\), então \((v,u) \notin E\).

Fluxo: Definição e Propriedades

Um fluxo \(f : V \times V \to \mathbb{R}\) satisfaz:

  1. Restrição de capacidade: \(0 \leq f(u,v) \leq c(u,v)\) para todo \((u,v)\).
  2. Conservação de fluxo: \(\sum_v f(v,u) = \sum_v f(u,v)\) para todo \(u \neq s, t\) (o que entra = o que sai).
  3. Valor do fluxo: \(|f| = \sum_v f(s,v) - \sum_v f(v,s)\) (fluxo líquido saindo de \(s\)).

Objetivo: encontrar \(f\) que maximize \(|f|\).

Múltiplas Fontes e Sorvedouros

Para redes com várias fontes \(s_1, \ldots, s_k\) e vários sorvedouros \(t_1, \ldots, t_m\):

  • Crie um super-source \(S\) com arestas \(S \to s_i\) de capacidade \(\infty\).
  • Crie um super-sink \(T\) com arestas \(t_j \to T\) de capacidade \(\infty\).

3. Caminho Aumentante e Grafo Residual

Caminho Aumentante

Um caminho aumentante é um caminho de \(s\) a \(t\) no grafo residual onde todas as arestas têm capacidade residual \(> 0\). O gargalo é a menor capacidade residual ao longo dele.

Teorema: O fluxo é máximo se e somente se não existe caminho aumentante.

Grafo Residual: Construção

Dado fluxo \(f\) na aresta \((u,v)\) de capacidade \(c\):

  • Aresta de ida \((u,v)\): capacidade residual \(c_f(u,v) = c - f\) (quanto ainda cabe).
  • Aresta reversa \((v,u)\): capacidade residual \(c_f(v,u) = f\) (quanto podemos “devolver”).

O Grafo Residual \(G_f\) contém todas as arestas com capacidade residual \(> 0\).

Por que Arestas Reversas?

Sem elas, o algoritmo pode ficar preso em soluções subótimas. As arestas reversas permitem “redirecionar” fluxo para caminhos mais eficientes, efetivamente “desfazendo” decisões anteriores.

Exemplo (Diamante): Grafo com 4 nós, todas caps = 1. Se primeira iteração escolhe \(s \to A \to B \to t\), sem reversa ficamos com \(|f|=1\) (subótimo). Com reversa \(B \to A\), segunda iteração encontra \(s \to B \to A \to t\), resultando em \(|f|=2\) (ótimo).

4. Ford-Fulkerson: O Método Genérico

Pseudocódigo

  1. Inicialize \(f(u,v) = 0\) para todas as arestas.
  2. Enquanto existir caminho aumentante \(P\) de \(s\) a \(t\) em \(G_f\):
    • Calcule o gargalo: \(c_f(P) = \min\{c_f(u,v) : (u,v) \in P\}\).
    • Para cada aresta \((u,v) \in P\): aumente \(f(u,v)\) pelo gargalo e diminua \(f(v,u)\).
  3. Retorne \(|f|\).

Complexidade e Caso Patológico

  • Complexidade: \(O(E \cdot |f^*|)\) — pode ser exponencial com DFS!
  • Caso patológico: Com aresta de capacidade 1 entre dois nós de alta capacidade, DFS pode oscilar enviando 1 unidade por iteração.
  • Com capacidades irracionais: pode não convergir!

5. Edmonds-Karp: BFS ao Resgate

Edmonds-Karp = Ford-Fulkerson + BFS para encontrar o caminho mais curto.

Por que BFS?

Aspecto DFS (Ford-Fulkerson) BFS (Edmonds-Karp)
Caminho Qualquer (pode ser longo) Mais curto
Iterações Até \(|f^*|\) No máximo \(O(VE)\)
Complexidade \(O(E \cdot |f^*|)\) \(O(V \cdot E^2)\)
Caps irracionais Pode não convergir Sempre termina

Lema-chave: A distância \(d(s,v)\) no residual nunca diminui ao longo das iterações.

Demonstração Passo a Passo

Rede: \(s \xrightarrow{10} A \xrightarrow{7} t\), \(s \xrightarrow{8} B \xrightarrow{10} t\), \(A \xrightarrow{5} B\).

Iter Caminho (BFS) Gargalo Fluxo
1 \(s \to A \to t\) \(\min(10,7)=7\) 7
2 \(s \to B \to t\) \(\min(8,10)=8\) 15
3 \(s \to A \to B \to t\) \(\min(3,5,2)=2\) 17
4 Sem caminho — 17 (máximo)

6. Implementação Java

Para Fluxo, a Matriz de Adjacência (cap[u][v]) é mais prática que lista de adjacência, desde que \(V \le 500\).

import java.util.*;

public class MaxFlow {
    static final int INF = Integer.MAX_VALUE;
    
    public static int edmondsKarp(int N, int[][] cap, int s, int t) {
        int flow = 0;
        int[] parent = new int[N];
        
        while (true) {
            // 1. BFS no grafo residual
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<>();
            q.add(s); parent[s] = s;
            
            while (!q.isEmpty()) {
                int u = q.poll();
                if (u == t) break;
                for (int v = 0; v < N; v++)
                    if (parent[v] == -1 && cap[u][v] > 0)
                        { parent[v] = u; q.add(v); }
            }
            
            if (parent[t] == -1) break; // Sem caminho
            
            // 2. Gargalo do caminho
            int push = INF;
            for (int v = t; v != s; v = parent[v])
                push = Math.min(push, cap[parent[v]][v]);
            
            // 3. Atualizar residual
            flow += push;
            for (int v = t; v != s; v = parent[v]) {
                cap[parent[v]][v] -= push; // Diminui ida
                cap[v][parent[v]] += push; // Aumenta volta
            }
        }
        return flow;
    }
}

Encontrando o Corte Mínimo

Após Edmonds-Karp, BFS no residual a partir de \(s\):

boolean[] reachable = new boolean[N];
Queue<Integer> q = new LinkedList<>();
q.add(s); reachable[s] = true;
while (!q.isEmpty()) {
    int u = q.poll();
    for (int v = 0; v < N; v++)
        if (!reachable[v] && cap[u][v] > 0) {
            reachable[v] = true; q.add(v);
        }
}
// Arestas do corte: originalCap[u][v] > 0 && reachable[u] && !reachable[v]

7. Teorema Max-Flow Min-Cut

Teorema (Ford & Fulkerson, 1956): O valor do fluxo máximo é exatamente igual à capacidade do corte mínimo.

\[\max_{f} |f| = \min_{(S,T)} c(S, T)\]

O que é um Corte \(s\)-\(t\)?

Partição de \(V\) em \(S\) (com \(s\)) e \(T\) (com \(t\)). Capacidade = soma das caps das arestas de \(S\) para \(T\).

Intuição da Prova

  1. \(|f| \leq c(S,T)\) para qualquer corte: todo fluxo atravessa o corte, e \(f \leq c\).
  2. Igualdade no ótimo: quando BFS falha no residual, os vértices alcançáveis formam \(S^*\). Arestas de \(S^*\) para \(T^*\) estão saturadas, logo \(|f^*| = c(S^*, T^*)\).

8. Algoritmo de Dinic

Melhora o Edmonds-Karp com:

  1. Level Graph: BFS constrói níveis. Só arestas que avançam um nível são mantidas.
  2. Blocking Flow: DFS satura múltiplos caminhos de uma vez no Level Graph.
  3. Repete até BFS não alcançar \(t\).

Complexidade

Caso Complexidade Justificativa
Geral \(O(V^2 \cdot E)\) \(\leq V\) fases, cada \(O(VE)\)
Caps unitárias \(O(E\sqrt{V})\) \(\leq \sqrt{V}\) fases

Para matching bipartido, Dinic em \(O(E\sqrt{V})\) equivale a Hopcroft-Karp.

9. Comparação de Algoritmos

Algoritmo Complexidade Quando usar
Ford-Fulkerson (DFS) \(O(E \cdot |f^*|)\) Evitar!
Edmonds-Karp (BFS) \(O(V \cdot E^2)\) Caso geral
Dinic \(O(V^2 \cdot E)\) Grafos grandes
Dinic (caps unitárias) \(O(E\sqrt{V})\) Matching bipartido
Push-Relabel \(O(V^2 \cdot E)\) Alternativa
Push-Relabel (FIFO) \(O(V^3)\) Grafos densos

10. Modelagem e Aplicações

Vertex Splitting (Capacidade nos Vértices)

Quando vértice \(v\) tem capacidade \(c_v\): divida em \(v_{in}\) e \(v_{out}\) com aresta interna de capacidade \(c_v\).

Matching Bipartido via Fluxo

Super-source \(\to\) lado esquerdo (cap 1), lado direito \(\to\) super-sink (cap 1). Fluxo máximo = matching máximo.

Circulação com Demandas

Cada aresta tem mínimo \(d\) e máximo \(c\). Transforme para fluxo padrão com super-source/sink auxiliares.

Project Selection (Closure Problem)

Projetos com lucros/custos e dependências. Lucro máximo = \(\sum\)(lucros positivos) − Min-Cut.

Dicas de Modelagem

Padrão Modelagem
Matching bipartido Caps 1, super-\(s\)/super-\(t\)
Alocação com limites Caps = limites de produção/demanda
Conectividade de arestas Caps 1, corte mínimo
Conectividade de vértices Vertex splitting + caps 1
Seleção com dependências Closure Problem (min-cut)

Dica de Maratona: Palavras-chave: “capacidade”, “gargalo”, “vazão”, “corte mínimo”, “matching” → Fluxo!

11. Exercícios

Conceituais

  1. Explique o grafo residual e a importância das arestas reversas.
  2. Enuncie o Teorema Max-Flow Min-Cut. Como extrair o corte mínimo?
  3. Por que Ford-Fulkerson com DFS pode ser exponencial?
  4. Compare Edmonds-Karp vs Dinic.
  5. Explique vertex splitting e quando é necessário.

Analíticos

  1. Trace manual: Simule Edmonds-Karp no grafo: \(s \xrightarrow{4} A \xrightarrow{3} C \xrightarrow{4} t\), \(s \xrightarrow{3} B \xrightarrow{5} t\), \(A \xrightarrow{2} B\). Fluxo máximo = 7.
  2. Aresta reversa: Em qual iteração do trace uma aresta reversa é usada?
  3. Todos os cortes: Enumere os 4 cortes da rede básica e identifique o mínimo.
  4. Modelagem: Fábricas/lojas com super-source/sink.
  5. Matching: Alunos/projetos como fluxo bipartido.

Programação

  1. Implemente Edmonds-Karp com corte mínimo.
  2. Resolva matching bipartido via fluxo.
  3. Desafio: Implemente Dinic com Level Graph e Blocking Flow.
  4. Problemas online: UVa 820, UVa 10480, UVa 259.
Back to top