Fluxo Máximo

Uma rede de fluxo é um grafo direcionado com origem s, destino t e capacidades de aresta não negativas. Um fluxo viável respeita as capacidades e conserva o fluxo em todos os demais vértices. O objetivo é maximizar o fluxo líquido de s para t.

Rede residual

A capacidade residual descreve quanto fluxo adicional uma aresta pode transportar e quanto fluxo existente pode ser desfeito por uma aresta residual reversa. Ignorar arestas reversas faz com que aumentos gulosos se comprometam permanentemente com suas escolhas e pode impedir que se alcance um ótimo.

Método de Ford–Fulkerson

Encontre repetidamente um caminho de s a t no grafo residual, aumente o fluxo pela menor capacidade residual do caminho e atualize as arestas residuais diretas e reversas. Com capacidades inteiras, cada aumento eleva o fluxo em pelo menos um; portanto, o método termina. Um limite dependente do fluxo máximo é pseudopolinomial, não fortemente polinomial no número de bits da entrada.

Edmonds–Karp e Dinic

Edmonds–Karp escolhe por BFS um caminho residual mais curto e executa em tempo O(VE²). Dinic constrói grafos de níveis por BFS e envia fluxos bloqueantes; seu limite geral é O(V²E), com limites melhores para classes importantes de redes.

Teorema do fluxo máximo e corte mínimo

Para qualquer fluxo viável e qualquer corte entre s e t, o valor do fluxo é no máximo a capacidade do corte. Quando não resta caminho aumentante, os vértices alcançáveis a partir de s na rede residual definem um corte cuja capacidade é igual ao fluxo atual. O fluxo é máximo e o corte é mínimo.

Reduções

Fluxo máximo modela emparelhamento bipartido, caminhos disjuntos em arestas, alocação de recursos e variantes de circulação. Uma redução deve preservar integralidade, capacidades, direção e o significado de uma solução viável.

Exercícios

1. Mostre por que as arestas residuais reversas são necessárias.
2. Reduza o emparelhamento bipartido a um fluxo com capacidades unitárias.
3. Extraia um corte mínimo após a busca residual final.