Fluxo máximo e emparelhamento

Rede e residual

Capacidades $c\ge0$, fluxos $0\le f\le c$, conservação em intermédios. Valor é saída líquida de $s$.

Para cada original $u\to v$: residual direta $c-f$ e inversa $f$. Percorrer inversa reduz original, sem fluxo negativo. Com original nos dois sentidos, separa inversas por índice. Paralelas exigem índice da aresta, não só predecessor.

Aumentar e terminar

Caminho $s\to t$ em residuais positivas com gargalo $\Delta=\min c_f$. Subtrai nas percorridas e soma nas inversas. Valor sobe $\Delta$.

• Ford-Fulkerson: qualquer caminho; inteiras dão $O(m\lvert f^*\rvert)$. Irracionais com más escolhas podem não terminar.
• Edmonds-Karp: BFS por menos arestas. Distâncias desde $s$ nunca descem; cada aresta é crítica $O(n)$ vezes. Total $O(nm^2)$.

Corte como certificado

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

Conta só $S\to T$. Todo fluxo cumpre $\lvert f\rvert\le c(S,T)$. Sem caminho, $S$ com alcançáveis de $s$ dá $\lvert f\rvert=c(S,T)$: fluxo máximo e corte mínimo simultâneos.

Valor único não implica solução única, em fluxos nem em cortes.

Emparelhamento

$s\to L\to R\to t$ com capacidade 1. Fluxo inteiro corresponde a arestas sem extremos repetidos. O emparelhamento cabe em $\min(\lvert L\rvert,\lvert R\rvert)$, por isso esse valor é um limite superior, não o valor atingido em qualquer grafo. Com dois vértices de cada lado e uma só aresta, o máximo é 1. Custo $O((\min(\lvert L\rvert,\lvert R\rvert)+1)(n+m))$.

Máximo é maior cardinalidade; maximal só resiste a acrescentar uma aresta.

Para várias vagas por pessoa, aumenta $s\to\text{pessoa}$ e $\text{trabalho}\to t$; mantém 1 em compatibilidades.

Execução e modelos.