Teorema do fluxo máximo e corte mínimo

No campo da Otimização, o teorema do fluxo máximo-corte mínimo afirma que em um fluxo de rede, o valor máximo do fluxo passando de um ponto-origem até um ponto destino é igual à sua capacidade mínima, que quando removida da rede de uma forma específica ocasiona a situação onde nenhum fluxo passa mais entre a origem e o destino..

O teorema do fluxo máximo-corte mínimo é um caso especial do teorema da dualidade e pode ser usado pra derivar o Teorema de Menger e o Teorema de König-Egerváry.

Seja ${\displaystyle N=(V,E)}$ uma rede (digrafo) com ${\displaystyle s}$ e ${\displaystyle t}$ sendo a origem e o destino de ${\displaystyle N}$ respectivamente.

A capacidade de uma aresta é um mapeamento c: E→R⁺, escrito como c_uv ou c(u,v). Ele representa a quantidade máxima de fluxo pode passar por uma aresta.

O fluxo é um mapeamento f: E→R⁺, escrito como f_uv or f(u,v), sujeito às seguintes duas restrições:

1. ${\displaystyle f_{uv}\leq c_{uv}}$ para cada ${\displaystyle (u,v)\in E}$ (restrição de capacidade)
2. ${\displaystyle \sum _{u:\,\,(u,v)\in E}f_{uv}=\sum _{u:\,\,(v,u)\in E}f_{vu}}$ para cada ${\displaystyle v\in V\setminus \{s,t\}}$ (conservação dos fluxos).

O valor do fluxo é definido por | f | = Σ_v∈Vf_sv, onde s é a origem de N. Ele representa a quantidade de fluxo passando da origem ao destino.

O problema do fluxo máximo é maximizar | f |, ou seja, transportar o maior quantidade possível de fluxo de s até t.

Um corte s-t C = (S,T) é definido como o particionamento de V tal que s∈S e t∈T. O conjunto de corte de C é o conjunto {(u,v)∈E | u∈S, v∈T}. Note que se as arestas no conjunto de corte de C forem removidas, | f | = 0.

A capacidade de um corte s-t é definida por ${\displaystyle c(S,T)=\sum _{(u,v)\in S\times T}c_{uv}}$.

O problema do corte mínimo é minimizar ${\displaystyle c(S,T)}$, ou seja, determinar S e T tal que a capacidade do corte S-T é mínimo.

O teorema do Fluxo Máximo-Corte Mínimo afirma que

O valor máximo de um fluxo s-t é igual a capacidade mínima de um corte s-t.

• Portal da matemática