Problema da vazão máxima

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 | editar código-fonte]

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 | editar código-fonte]