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 G(V,E), onde cada aresta u,v tem uma capacidade c(u,v), nos queremos determinar o fluxo máximo f, sujeito a certas limitações. Existem varias maneiras para solucionar este problema:

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

Referência[editar | editar código-fonte]