Problema da vazão máxima

O problema do fluxo máximo consiste em encontrar fluxo através de uma rede de fluxo que seja máximo O problema do fluxo máximo pode ser visto como um caso especial de um problema de fluxo mais complexo. Ele é o problema fluxo de mutiplas-mercadorias com so uma so mercadoria, e também como o problema de fluxo de custo-minimo com todos os fluxos zerados. O fluxo máximo esta relacionado ao corte em uma rede pelo Teorema do mínimo corte-máximo fluxo.

Soluções editar

Dado um grafo  , onde cada aresta   tem uma capacidade  , nos queremos determinar o fluxo máximo  , sujeito a certas limitações. Existem varias maneiras para solucionar este problema:

Método Complexidade Descrição
Força bruta   Encontra os menor de todos os cortes que separa   e  .
Programação linear Restrições dadas pelas definições de uma fluxo legal. Otimizar  .
Algoritmo de Ford-Fulkerson   Tão logo seja aberto um caminho através da rede, envie o maior fluxo possível através dele.
Algoritmo de Edmonds-Karp   Uma especialização do algoritmo de Ford-Fulkerson, busca caminhos com busca em largura.
Algoritmo de remarcagem-para-frente   Rearranja os nodos em vários pesos tal que o um acréscimo máximo de fluxo corra de   para   "por si proprio".

Referência editar