Maximização de Fluxo em Grafos com Limites Inferiores Positivos
Autores
|
1818 |
3,774
|
|
|
1819 |
3,774
|
Informações:
Publicações do PESC
Analisa-se problemas de maximização de fluxo em grafos com limites inferiores positivos. É implementado o Algoritmo das Duas Fases. A primeira fase consiste em determinar um fluxo viável. Isto é feito transformando o grafo original em um grafo equivalente com limite inferior lij nulo e aplicando a este o algoritmo tradicional. São analisadas condições que permitem uma simplificação do grafo equivalente. Estas condições permitem dispensar a segunda fase na qual se gera o fluxo máximo a partir do fluxo viável. Assim, conseguimos gerar o fluxo máximo com uma única fase.
We examine maximum flow problems with positive lower bounds. The two-phase algorithm is implemented. The first phase determines a feasible flow. We transform the given graph in an equivalent graph with lower bounds lij = 0. Conditions are examined which result in a more simple equivalent graph. These conditions allow us to abstain from using the second phase where a maximum flow is generated starting from a feasible flow. Thus, we get a maximum flow in a one phase algorithm.