VT PO 2

Definição
Seja uma rede (digrafo) com e sendo a origem e o destino de respectivamente.
A capacidade de uma aresta é um mapeamento c: E→R+, 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: E→R+, escrito como fuv or f(u,v), sujeito às seguintes duas restrições:
1. para cada (restriço de capacidade)
2. para cada (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 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 . O problema do corte mínimo é minimizar , ou seja, determinar S e T tal que a capacidade do corte S-T é mínimo.

Fluxo Máximo

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.

Problema
Uma rede G = (V, A) com capacidade nos arcos, desejamos determinar o fluxo máximo que pode ser enviado de um vértice s (Fonte) a um vértice t (destino).

Fluxo máximo: modelo em programação matemática

Um vetor x = [xij : (i, j) ∈ A] satisfazendo as restrições acima é dito fluxo e o escalar v correspondente é dito valor do fluxo. Surge em aplicações e como elemento-chave de algoritmos mais complexos. Por exemplo, encontrar um fluxo factível para o problema de fluxo de custo mínimo. O Teorema Fluxo-Máximo Corte-Mínimo diz que o valor do fluxo