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 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 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 26: Maximum Flow, pp. 643–700.
Categoria:Problemas matemáticos Categoria:Algoritmos Categoria:Teoria dos grafos