Fluxo em REDES

Uma rede é um grafo dirigido e sem laços que possui exatamente uma raiz e uma anti-raiz.

Associando a cada aresta a da rede um valor c(a) que corresponde à capacidade da aresta, podemos definir uma função Ø(a) que correspondente ao fluxo da aresta. Esta função satisfaz as seguinte restrições:

Fluxo Ø :

1. Ø(a) ³ 0 - fluxo é não negativo em cada arco
2. Ø(a) £ c(a) - fluxo não excede a capacidade do arco
3. O fluxo que entra é o mesmo que sai de um vértice
4. O fluxo que entra na fonte (raiz) é o mesmo que chega ao sumidouro (anti-raiz), que é o fluxo máximo Ø₀ da rede

O objetivo é obter o fluxo máximo Ø₀ da rede