# Fluxo máximo e emparelhamento

Capacidade, conservação, rede residual, Ford-Fulkerson, Edmonds-Karp e o certificado de corte mínimo.

Página: https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/

A origem $s$ pode enviar 3 unidades para $a$ e 2 para $b$. O destino $t$ recebe no máximo 2 de $a$ e 3 de $b$. A ligação $a\to b$ permite redistribuir até 2 unidades entre os dois ramos. Queremos saber quanto chega a $t$ sem exceder nenhum limite e sem acumular fluxo nos vértices intermédios.

Nesta **rede dirigida**, cada aresta tem capacidade $c(u,v)\ge0$ e transporta fluxo $0\le f(u,v)\le c(u,v)$. Em cada vértice intermédio, o total que entra é igual ao que sai. O valor do fluxo é a saída líquida de $s$, saída menos entrada. Pela conservação, coincide com a entrada líquida em $t$. Vários caminhos podem contribuir para esse valor e partilhar capacidades.

## A rede residual permite corrigir decisões

Se uma aresta tem capacidade 5 e já transporta 3, podemos acrescentar 2 no mesmo sentido. Também podemos cancelar até 3, representados por uma aresta residual no sentido inverso.

Para cada aresta original $u\to v$, mantemos uma residual direta de capacidade $c-f$ e a sua inversa de capacidade $f$.

Ideia-chave

Percorrer a inversa **reduz** o fluxo original, não envia fluxo negativo nessa aresta. A conservação continua válida quando fazemos esta alteração ao longo de um caminho completo.

Se o grafo original também tem $v\to u$, são arestas originais diferentes. Uma implementação com pares de arestas residuais mantém separadas as inversas de cada uma e suporta arestas paralelas. Um índice para a aresta inversa evita confundi-las.

## Aumentar ao longo de um caminho

Um caminho aumentante liga $s$ a $t$ por arestas residuais com capacidade positiva. O máximo aumento possível é o gargalo

$$
\Delta=\min_{e\in P}c_f(e).
$$

Para cada aresta residual percorrida, subtrai $\Delta$ à sua capacidade e acrescenta $\Delta$ à capacidade da inversa. Isto conserva a possibilidade de desfazer a operação. O valor do fluxo aumenta exatamente $\Delta$.

Na rede abaixo, os rótulos são `fluxo / capacidade`. A primeira escolha usa $s,a,b,t$ com 2 unidades. Depois de outros dois aumentos, parece que $a\to t$ ainda tem espaço mas a saída $s\to a$ já está cheia. O último caminho $s,b,a,t$ usa a **inversa de $a\to b$** para cancelar uma unidade e redirecioná-la.

Os fluxos finais são $f(s,a)=3$, $f(s,b)=2$, $f(a,b)=1$, $f(a,t)=2$ e $f(b,t)=3$. Em $a$, entram 3 e saem $1+2$; em $b$, entram $2+1$ e saem 3. O valor é 5, ou seja uma implementação que só percorresse as arestas originais ficaria presa no valor 4 desta sequência de escolhas.

## Ford-Fulkerson e Edmonds-Karp

**Ford-Fulkerson** é o método: começa com fluxo zero, encontra um caminho aumentante qualquer e aumenta pelo gargalo até não existir outro. Com capacidades inteiras, cada aumento acrescenta pelo menos uma unidade. Termina em no máximo $|f^*|$ aumentos, onde $|f^*|$ é o valor ótimo, com custo $O(m|f^*|)$ para procura de caminho linear.

Este limite depende do valor numérico das capacidades, não apenas dos seus bits, por isso não transfiras a garantia dos inteiros para qualquer representação real. Com capacidades irracionais e escolhas inadequadas, o método genérico pode não terminar.

**Edmonds-Karp** escolhe por BFS um caminho com o menor número de arestas residuais. Não escolhe o maior gargalo nem o menor custo ponderado.

As distâncias em arestas a partir de $s$ na rede residual nunca diminuem entre aumentos. Cada aumento satura alguma aresta do caminho. Para a mesma aresta voltar a ser um gargalo no mesmo sentido, foi antes necessário usar a sua inversa, o que força um aumento de pelo menos dois na distância da sua origem. Essa distância é inferior a $n$ num caminho simples; cada aresta pode ser crítica $O(n)$ vezes. Existem $O(m)$ arestas, logo $O(nm)$ aumentos. Com BFS de $O(n+m)$ em cada iteração, obtemos o limite habitual $O(nm^2)$ para a parte relevante da rede. A representação usa $O(n+m)$ espaço.

## Corte mínimo como prova do resultado

Um corte $(S,T)$ tem $s\in S$, $t\in T$ e capacidade

$$
c(S,T)=\sum_{u\in S,\,v\in T}c(u,v).
$$

Conta só capacidades **de $S$ para $T$**, não as do sentido contrário. O fluxo líquido através do corte coincide com o valor do fluxo; as saídas são limitadas pelas capacidades e as entradas são não negativas. Por isso $|f|\le c(S,T)$ para todo o corte.

Se não há caminho aumentante, toma $S$ como os alcançáveis de $s$ na rede residual. Toda a aresta original de $S$ para $T$ está saturada; toda a original de $T$ para $S$ tem fluxo zero, pois a sua inversa daria uma saída residual. Logo $|f|=c(S,T)$. Encontrámos simultaneamente um fluxo máximo e um corte mínimo.

No exemplo, $S=\{s\}$ dá capacidade $3+2=5$. O fluxo de valor 5 atinge esse limite, certificando o ótimo. Não precisamos de enumerar todos os fluxos possíveis.

Vídeo complementar em inglês: [Fluxo máximo e corte mínimo, aula 13 de 6.046J, 2015](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/lecture-13-incremental-improvement-max-flow-min-cut/) (MIT OpenCourseWare). Para relacionar a execução com o certificado de otimalidade, observa o papel da rede residual e como um corte limita o valor de qualquer fluxo.

### Valor único, soluções diferentes

O teorema fluxo máximo/corte mínimo iguala dois **valores ótimos**. Não afirma que exista apenas um fluxo máximo ou apenas um corte mínimo.

Na rede com capacidades $s\to a=1$, $s\to b=1$, $a\to v=1$, $b\to v=1$ e $v\to t=1$, o corte $S=\{s,a,b,v\}$ tem capacidade 1. Podemos atingi-la enviando uma unidade por $s,a,v,t$ ou por $s,b,v,t$. São dois fluxos máximos diferentes certificados pelo mesmo corte. Com fluxos reais, qualquer repartição $\lambda$ e $1-\lambda$, para $0\le\lambda\le1$, entre os dois ramos também é máxima.

Na cadeia $s\to a\to t$, com capacidade 1 nas duas arestas, a conservação força o único fluxo máximo: uma unidade em cada aresta. Mas $S=\{s\}$ e $S=\{s,a\}$ são dois cortes mínimos de capacidade 1. Um desempate do algoritmo escolhe uma solução; não demonstra unicidade das soluções possíveis.

## Implementação com inversas explícitas

O programa lê `n m s t`, depois `m` linhas `u v capacidade`. Usa capacidades inteiras, até um milhão, com até 2000 vértices e 20000 arestas. Guarda para cada aresta o índice da inversa e, na BFS, guarda também o **índice da aresta**, não apenas o predecessor. Assim distingue arestas paralelas.

**main.cpp**

```cpp
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

struct Aresta {
    int destino, inversa;
    long long residual;
};

int main() {
    int n, m, s, t;
    if (!(std::cin >> n >> m >> s >> t) || n < 2 || n > 2000 ||
        m < 0 || m > 20000 || s < 0 || s >= n || t < 0 || t >= n || s == t) {
        std::cout << "entrada invalida\n";
        return 0;
    }
    std::vector<std::vector<Aresta>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long c;
        if (!(std::cin >> u >> v >> c) || u < 0 || u >= n || v < 0 ||
            v >= n || c < 0 || c > 1000000) {
            std::cout << "entrada invalida\n";
            return 0;
        }
        if (u == v) continue;
        int iu = static_cast<int>(adj[u].size());
        int iv = static_cast<int>(adj[v].size());
        adj[u].push_back({v, iv, c});
        adj[v].push_back({u, iu, 0});
    }
    long long fluxo = 0;
    std::vector<int> pai(n), via(n);
    while (true) {
        std::fill(pai.begin(), pai.end(), -1);
        std::queue<int> fila;
        fila.push(s);
        pai[s] = s;
        while (!fila.empty()) {
            int u = fila.front();
            fila.pop();
            for (int i = 0; i < static_cast<int>(adj[u].size()); ++i) {
                const auto &e = adj[u][i];
                if (e.residual <= 0 || pai[e.destino] != -1) continue;
                pai[e.destino] = u;
                via[e.destino] = i;
                fila.push(e.destino);
            }
        }
        if (pai[t] == -1) break;
        long long aumento = 1LL << 60;
        for (int v = t; v != s; v = pai[v])
            aumento = std::min(aumento, adj[pai[v]][via[v]].residual);
        for (int v = t; v != s; v = pai[v]) {
            auto &e = adj[pai[v]][via[v]];
            e.residual -= aumento;
            adj[v][e.inversa].residual += aumento;
        }
        fluxo += aumento;
    }
    std::cout << "fluxo " << fluxo << "\nlado s:";
    for (int v = 0; v < n; ++v)
        if (pai[v] != -1) std::cout << ' ' << v;
    std::cout << '\n';
}
```

Devolve `fluxo 5` e `lado s: 0`. Se $t$ for inalcançável, devolve fluxo zero e um corte de capacidade zero. Rejeita `s == t`, porque este exemplo exige origem e destino distintos. Capacidades zero não criam caminhos aumentantes.

## Emparelhamento bipartido

Num grafo bipartido $L\cup R$, um emparelhamento escolhe arestas sem repetir extremos. **Máximo** significa maior cardinalidade possível. **Maximal** significa que já não podemos acrescentar uma aresta sem alterar as escolhidas; pode ser menor do que o máximo.

Acrescenta $s$ e $t$. Liga $s$ a cada vértice de $L$, cada aresta original de $L$ para $R$ e cada vértice de $R$ a $t$, tudo com capacidade 1. Um fluxo inteiro usa no máximo uma unidade por vértice de cada lado. As arestas $L\to R$ com fluxo 1 formam um emparelhamento de cardinalidade igual ao valor do fluxo. Reciprocamente, qualquer emparelhamento produz esse fluxo.

Com $L=\{a,b\}$, $R=\{x,y\}$ e arestas $ax,ay,bx$, escolher $ax$ parece ocupar $x$ e deixar $b$ de fora. Um caminho residual $s,b,x,a,y,t$ cancela $ax$ e escolhe $bx$ e $ay$, obtendo cardinalidade 2: é a mesma correção de decisões da rede de transporte.

A transformação custa $O(n+m)$ e tem $n+2$ vértices e $m+n$ arestas. Não é $O(n)$ em grafos arbitrários: ler as $m$ arestas também conta. Cada aumento transporta uma unidade e acrescenta um par à cardinalidade, embora possa reorganizar pares anteriores. Como o valor não excede $\min(|L|,|R|)$, há no máximo esse número de aumentos. Incluindo a BFS final sem caminho, o emparelhamento custa $O((\min(|L|,|R|)+1)(n+m))$, mais apertado do que o limite geral $O(nm^2)$ quando um dos lados é pequeno. A integridade das capacidades garante que os aumentos e o resultado são inteiros.

Para atribuir vários trabalhos a cada pessoa, aumenta a capacidade $s\to\text{pessoa}$ para o seu limite e a capacidade $\text{trabalho}\to t$ para o número de atribuições exigido. Mantém capacidade 1 nas compatibilidades se uma pessoa não puder repetir o mesmo trabalho. Saturar todas as saídas dos trabalhos certifica que todas as necessidades foram satisfeitas.

## Atribuir revisores a artigos

Cada artigo $j$ precisa de pelo menos $r_j$ revisores distintos e cada revisor $i$ aceita no máximo $b_i$ artigos. Uma compatibilidade indica que o revisor pode avaliar o tema do artigo. Cria a rede

$$
s\to\text{revisor }i\to\text{artigo }j\to t,
$$

com capacidades $b_i$, 1 e $r_j$, respetivamente. A atribuição é possível se e só se o fluxo máximo vale $R=\sum_j r_j$. Como a capacidade total das entradas em $t$ é $R$, atingir esse valor satura **cada** artigo, não apenas uma soma arbitrária de revisões.

Por que impor exatamente $r_j$ se o pedido diz pelo menos? De qualquer atribuição que satisfaça o mínimo, podemos retirar as revisões excedentes de cada artigo. Isso não aumenta a carga de nenhum revisor. Existe uma atribuição com pelo menos os mínimos se e só se existe uma com exatamente esses mínimos, neste modelo sem outras obrigações.

Considera dois artigos $A,B$, ambos com mínimo 2, e revisores $p,q,r$ com limites 2, 1 e 1. As compatibilidades são $pA,pB,qA,rB$. Um fluxo de valor 4 escolhe todas as quatro: $A$ recebe $p,q$ e $B$ recebe $p,r$. Ter capacidade total 4 era necessário, mas só as compatibilidades e o fluxo demonstram que chega.

Para analisar a ausência de um revisor, retira-o da rede e calcula de novo o fluxo a partir de zero. Retirar $q$ neste exemplo deixa $A$ com apenas $p$ compatível, logo não há atribuição completa. Noutros casos, a rede residual pode reorganizar as atribuições: perder uma revisão na solução atual não prova que não exista outra solução.

Testar qualquer conjunto de $K$ ausências diretamente exige $\binom{q}{K}$ redes para $q$ revisores, além do custo de cada fluxo. Esse fator é polinomial em $q$ para $K$ fixo, mas pode ser exponencial quando $K$ faz parte da entrada. As regras de compatibilidade por temas primários e secundários mudam quais são as arestas permitidas; não autorizam o mesmo revisor a contar duas vezes para o mesmo artigo.

## Exercícios

Um valor e um corte que o certifica

Uma rede tem capacidades s→a=4, s→b=3, a→b=2, a→t=2 e b→t=5. Constrói um fluxo máximo e um corte com a mesma capacidade.

Pista

A origem pode emitir no máximo 7. Verifica se consegues usar toda essa saída sem violar a conservação.

Mais uma pista

Envia 2 por s,a,t; 2 por s,a,b,t; e 3 por s,b,t.

Solução

Os fluxos são sa=4, sb=3, ab=2, at=2 e bt=5, valor 7. Em a entram 4 e saem 2+2; em b entram 3+2 e saem 5. O corte S={s}, T={a,b,t} tem capacidade 4+3=7. Todo o fluxo é limitado por esse corte e a construção atinge-o, portanto é máximo.

Confere a tua resposta:

*   Construí um fluxo de valor 7.
*   Verifiquei conservação e capacidades.
*   Dei um corte de capacidade 7.

Erros frequentes

Uma lista de caminhos sem verificar capacidades partilhadas pode exceder uma aresta. A capacidade do corte só conta saídas de S para T.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#corte-m%C3%ADnimo-como-prova-do-resultado)

Corrigir uma escolha de emparelhamento

L={p,q}, R={u,v} e as compatibilidades são p–u, p–v e q–u. Foi escolhido p–u. Mostra o caminho residual que obtém um emparelhamento de tamanho 2 e explica a aresta inversa.

Pista

O novo caminho começa na pessoa q, que ainda está livre.

Mais uma pista

Usa s,q,u,p,v,t. A passagem u→p cancela a atribuição anterior p→u.

Solução

O caminho residual s,q,u,p,v,t aumenta uma unidade. Cancela p–u e cria q–u e p–v. As capacidades s→p e u→t já ocupadas não são excedidas, porque a inversa reorganiza o fluxo anterior. O resultado é de tamanho 2 e é máximo, pois só há duas pessoas e duas tarefas.

Confere a tua resposta:

*   Identifiquei o caminho residual.
*   Expliquei o cancelamento de p–u.
*   Obtive q–u e p–v e um limite superior 2.

Erros frequentes

Ficar com as três compatibilidades violaria a unicidade dos extremos. Um emparelhamento maximal de tamanho 1 não era máximo nesta instância.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#emparelhamento-bipartido)

Capacidade total não chega

Há três artigos A, B e C, cada um com mínimo de dois revisores. Os revisores p, q e r aceitam até dois artigos cada. As únicas compatibilidades são pA, pB, qA, qB e rC. Constrói a rede, encontra o fluxo máximo e decide se há atribuição completa. Justifica com um corte, apesar de a capacidade total dos revisores ser seis.

Pista

Uma pessoa só pode contar uma vez para cada artigo.

Mais uma pista

Usa capacidade 1 em r→C. Experimenta o lado da origem com s e r.

Solução

As arestas s→revisor têm capacidade 2, as compatibilidades capacidade 1 e artigo→t capacidade 2. Atribui p e q a A e B, e r a C: são cinco revisões. O corte S com s e r tem capacidade 2+2+1=5, pelas arestas s→p, s→q e r→C. Assim cinco é máximo. Precisávamos de fluxo seis para saturar os três artigos; C só recebe uma revisão e a atribuição completa é impossível.

Confere a tua resposta:

*   Modelei capacidades 2, 1 e 2 nas três camadas.
*   Obtive fluxo máximo 5 e um corte de capacidade 5.
*   Identifiquei o artigo C com apenas um revisor compatível.

Erros frequentes

Dar capacidade 2 a r→C contaria a mesma pessoa duas vezes, e somar os limites dos revisores ignora onde essa capacidade pode ser usada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#atribuir-revisores-a-artigos)

Contar aumentos e a BFS final

Um grafo bipartido tem lados com a e b vértices. A rede usa capacidades 1 e procura caminhos por BFS até uma procura falhar. Tem $n=a+b+2$ vértices e m arestas originais. Deriva limites para os aumentos e o tempo, incluindo a última BFS. Aplica-os a a=4, b=10, n=16 e m=30, sem tratar O como contagem exata.

Pista

Conta separadamente as procuras bem-sucedidas e a que determina a paragem.

Solução

Cada aumento acrescenta uma unidade ao emparelhamento. O valor não excede $\min(a,b)$, pelo que há no máximo esse número de aumentos. As inversas podem reorganizar pares; o que cresce é a cardinalidade.

Cada BFS custa $O(n+m)$, incluindo inversas, que apenas duplicam as arestas. Há ainda uma BFS final sem caminho. O limite, incluindo construção, é $O((\min(a,b)+1)(n+m))$. No exemplo, são até quatro aumentos e cinco procuras. O produto $5(16+30)=230$ combina os parâmetros do limite; não é uma contagem exata de operações nem um tempo em segundos.

Confere a tua resposta:

*   Limitei os aumentos por min(a,b).
*   Incluí a procura final sem caminho.
*   Derivei o custo parametrizado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#emparelhamento-bipartido)

O mesmo valor não fixa a solução

As únicas arestas da primeira rede são $s\to a$, $s\to b$, $a\to v$, $b\to v$ e $v\to t$, todas de capacidade 1. Constrói dois fluxos máximos distintos e um corte mínimo que certifica ambos. Na segunda rede há apenas $s\to u\to t$, com capacidade 1 nas duas arestas. O fluxo máximo é único? E o corte mínimo? Explica o que o teorema fluxo máximo/corte mínimo realmente iguala.

Solução

Na primeira rede, uma unidade por $s,a,v,t$ e uma unidade por $s,b,v,t$ são soluções alternativas. Em cada uma, as outras arestas têm fluxo zero. O corte $S=\{s,a,b,v\}$ deixa sair apenas $v\to t$, de capacidade 1. Os dois fluxos atingem esse limite e são máximos. **Não** podemos enviar as duas unidades simultaneamente, pois partilham essa saída.

Na cadeia, conservação em u e valor máximo 1 forçam fluxo 1 em ambas as arestas. O fluxo máximo é único. Os cortes $S=\{s\}$ e $S=\{s,u\}$ têm ambos capacidade 1, logo há dois cortes mínimos. O teorema iguala o valor do fluxo máximo à capacidade mínima, sem impor unicidade dos fluxos nem dos cortes.

Confere a tua resposta:

*   Dei dois fluxos máximos de valor 1 na primeira rede.
*   Certifiquei ambos com o corte que só deixa v→t sair.
*   Dei dois cortes mínimos e um único fluxo máximo na cadeia.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#valor-%C3%BAnico-solu%C3%A7%C3%B5es-diferentes)