Teorema do Fluxo Máximo–Corte Mínimo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde março de 2011).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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.

Definição[editar | editar código-fonte]

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

A capacidade de uma aresta é um mapeamento c: ER+, escrito como cuv ou c(u,v). Ele representa a quantidade máxima de fluxo pode passar por uma aresta.
O fluxo é um mapeamento f: ER+, escrito como fuv or f(u,v), sujeito às seguintes duas restrições:
  1. f_{uv} \le c_{uv} para cada (u,v)\in E (restriço de capacidade)
  2. \sum_{u:\,\,(u,v)\in E} f_{uv} = \sum_{u:\,\,(v,u)\in E} f_{vu} para cada v \in V\setminus\{s,t\} (conservação dos fluxos).
O valor do fluxo é definido por | f | = Σv∈Vfsv, 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 sS e tT. O conjunto de corte de C é o conjunto {(u,v)∈E | uS, vT}. Note que se as arestas no conjunto de corte de C forem removidas, | f | = 0.
A capacidade de um corte s-t é definida por c (S,T) = \sum_{(u,v) \in S \times T} c_{uv}.

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

Declaração[editar | editar código-fonte]

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.