Fluxo máximo e emparelhamento

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$.

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

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

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 (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.

#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

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.