Algoritmos Para Fluxo Máximo Em Redes
B. C. S. Sanches, G. Manić
Centro de Matemática, Computação e Cognição, Universidade Federal do ABC
Av. Dos Estados 5001, Santo André - São Paulo
Durante a elaboração deste trabalho o aluno B. C. S. Sanches recebeu apoio financeiro do CNPq (PIBIC - Edital
01/2008).
Resumo: Muitos problemas do cotidiano de diversas áreas podem ser modelados através de grafos
e resolvidos através de algoritmos padronizados que independem do problema inicial e operam
somente no grafo que representa o problema. O foco deste trabalho é um estudo dirigido sobre alguns
destes algoritmos envolvendo o problema de fluxo máximo em redes. Abordamos os algoritmos de
Ford&Fulkerson, preflow-push genérico e highest label preflow-push. Também, apresentamos uma
aplicação da teoria de fluxos e da dualidade do fluxo máximo-corte mı́nimo para a otimização
de um problema de processamento paralelo relacionado a distribuição de processos entre dois
processadores conectados entre si em uma mesma rede. Fizemos também uma implementação
do algoritmo highest label preflow-push em linguagem C++.
Index Terms: Algoritmos em grafos, fluxo em redes, processamento paralelo.
1. Introdução
A história da teoria dos grafos começou em 1736 em Königsburg, Alemanha, quando Leonhard
Euler precisava resolver o seguinte problema: É possı́vel atravessar todas as sete pontes que
ligam os três distintos territórios sem passar mais de uma vez pela mesma ponte, e ao fim retornar
ao ponto de partida [1]. Euler resolveu então modelar o problema real como uma rede de pontos
ligados por linhas entre si, e então, aos pontos que corresponderiam aos territórios ele atribuiu
o nome de nós, e para as linhas que corresponderiam as pontes deu o nome de arcos. Desta
forma foi possı́vel tornar o problema mais simples e independente de detalhes desnecessários.
Assim, foi possı́vel determinar uma abordagem padronizada para solucionar o problema somente
utilizando um par ordenado formado por dois conjuntos, um de nós e outro de arcos, ao qual
atribuı́-se o nome de grafo. Mais formalmente, definimos um grafo dirigido, ou orientado, G(V, E)
como um par ordenado (V, E), onde V é o conjunto dos nós e E o conjunto dos arcos de G (ou
seja, o conjunto de pares ordenados de elementos de V ) [2], [3].
Uma rede é um grafo G(V, E) orientado onde cada arco que liga i a j tem associada uma
capacidade inteira não negativa uij . O problema do fluxo máximo consiste em, dada uma rede
orientada, determinar o máximo de fluxo que pode ser enviado de um nó que chamaremos de
fonte (denotado por s) até outro que chamaremos de sorvedouro (denotado por t), de forma que
o fluxo xij entre cada par de nós (i, j) não exceda a capacidade uij e de forma que o balanço
de fluxo em cada nó da rede com exceção de s e t seja mantido (ou seja, o fluxo que entra em
cada nó, com exceção de s e t, é igual ao fluxo que sai deste nó). Mais formalmente, queremos
maximizar v, sujeito as seguintes condições.
X
X
xji = v, para i = s
xij −
{j:(i,j)∈E}
{j:(j,i)∈E}
(1)
X
X
xij −
{j:(i,j)∈E}
X
{j:(i,j)∈E}
xji = 0, para i ∈ E \ {s, t}
(2)
xji = −v, para i = t
(3)
{j:(j,i)∈E}
xij −
X
{j:(j,i)∈E}
0 ≤ xij ≤ uij para todo (i, j) ∈ E.
(4)
Chamamos o vetor x = {xij } satisfazendo as condições (1) – (4) acima de fluxo e o correspondente valor de v de valor de fluxo [4], [5]. As condições (1) – (3) acima chamamos de balanço
de fluxo.
Apresentaremos em seguida umas definições que serão necessárias. Dada uma rede G(V, E)
e um fluxo x em G, a capacidade residual rij de arco (i, j) é definida como o valor máximo de
fluxo adicional que pode ser mandado de i a j utilizando somente os arcos (i, j) e (j, i). É útil
construir uma outra rede, chamada rede residual, que tem os mesmos nós da rede original G, e
contém somente os arcos com capacidades residuais rij positivas. Definimos um corte sobre a
rede G(V, E) como uma partição dos nós de V em dois sub-conjuntos S e S̄ := V − S. Um corte
onde ao menos s ∈ S e t ∈ S̄ denotamos por [s, t] [2], [4].
Para solucionar o problema de fluxo máximo existem varias técnicas, que caracterizam as
diferentes classes de algoritmos, sendo as principais a de caminhos aumentantes (Augmenting
Path) e a dos algoritmos preflow-push [4].
Começando com o fluxo de valor zero, os algoritmos de caminhos aumentantes obtém o fluxo
máximo incrementando o valor de fluxo (enquanto possı́vel) por caminhos orientados da fonte
ao sorvedouro na rede residual, criada a partir da rede inicial. Estes algoritmos mantém então o
balanço de fluxo válido a cada etapa. Da prova da corretude deste algoritmo se obtém seguinte
teorema [4].
Teorema 1:
Dada uma rede G com fonte s e sorvedouro t, o valor de fluxo máximo em G de s a t, é igual
ao valor da capacidade mı́nima dentre todos os cortes [s, t].
Observamos que a eficiência computacional dos algoritmos de caminhos aumentantes depende
de como se identificam os caminhos de s a t. Uma possı́vel implementação dos algoritmos de
caminhos aumentantes é o algoritmo de Ford&Fulkerson [6].
Em seguida colocamos em evidencia os pontos fracos dos algoritmos de caminhos aumentantes e assim revelamos a necessidade de umas outras classes de algoritmos.
Os algoritmos preflow-push [7] incrementam o valor de fluxo em arcos individuais, ao invés de
caminhos inteiros de s a t, como nos algoritmos anteriores. Então, estes algoritmos permitem que
haja mais mais fluxo entrando do que saindo em um nó em etapas intermediárias. Portanto, os
algoritmos preflow-push não satisfazem o balanço de fluxo em cada nó da rede a todo instante,
causando assim um fluxo não válido chamado pré-fluxo. Em seguida, estes algoritmos procedem
empurrando o fluxo em excesso para o sorvedouro, até se obter um fluxo válido que também
é máximo. Este trabalho descreve também uma versão otimizada do algoritmo preflow-push
genérico, chamado highest label preflow-push [4].
Descrevemos ainda uma aplicação do Teorema 1 para a otimização de um problema de processamento paralelo relacionado a distribuição de processos entre dois processadores conectados
entre si em uma mesma rede.
Fizemos também uma implementação do algoritmo highest label preflow-push em linguagem
C++.
2. Resultados
Obteve-se o consumo de tempo dos algoritmos de Ford&Fulkerson, preflow-push genérico e
2
2
highest label preflow-push como respectivamente O(|V ||E|U ), O(|V | |E|) e O(|V | |E|1/2 ), de
onde é possı́vel observar que o algoritmo de Ford&Fulkerson não é polinomial devido a dependência de U (a capacidade máxima dos arcos da rede), e que o algoritmo highest label
preflow-push é o mais eficiente destes. Para obter o consumo de témpo dos algoritmos do tipo
preflow-push usamos a técnica de análise amortizada [5].
Também, foi aplicado o resultado do Teorema 1 para resolver o seguinte problema de processamento paralelo. Se P é um conjunto de processos a serem resolvidos em dois processadores,
desejamos soluciona-los de forma a minimizar o custo de comunicação inter-processador e de
processamento total [4], [8]. Para resolver o problema, definimos, para cada pi ∈ P e k ∈ {1, 2},
o número cpk (i) como custo da solução do processo pi no processador k, e ccij como custo de
comunicação para a execução de dois processos pi e pj em processadores diferentes.
Modelaremos agora o problema descrito como uma rede onde cada processo pi ∈ P será
representado por um nó, e de forma similar também representaremos os processadores, onde
o primeiro processador será a fonte s e o segundo o sorvedouro t de nossa rede. Para cada
processo pi incluiremos um arco (i, t) com capacidade cp1 (i), e um arco (s, i) com capacidade
cp2 (i) na nossa rede. Ainda, para cada processo pj que se intercomunica, ou utiliza informações
do processo pi incluiremos um arco (i, j) com a capacidade equivalente ao custo ccij .
Mostraremos agora uma relação entre o problema original e o problema modelado através
da rede. Desta forma tomemos um corte [s, t] genérico em nossa rede, que divide a rede em
dois conjuntos de nós, um que chamaremos de M , e outro de M̄ . Percebemos que a soma das
capacidades dos arcos de M a t é exatamente o custo necessário para resolver os processos
em M \ {s} com o primeiro processador (representado por s). De forma similar temos que
a soma das capacidades dos arcos de s a M̄ \ {t} é o custo necessário para resolver os
processos em M̄ com o segundo processador (representado na rede por t). E ainda, os arcos
(i, j) que vão dos nós pertencentes a M para os nós pertencentes a M̄ (com exceção de s e t),
representam P
os custos de transporte
inter-processador
ccij . Então, a capacidade total de corte
P
P
[s, t] é CT = (i,j)∈MX M̄ cpij + i∈M cp1 (i)+ i∈M̄ cp2 (i). Mas, como vimos, CT é exatamente o
custo computacional necessário para solucionar os processos em M \{s} no primeiro processador
e os processos em M̄ \ {t} no segundo processador. E agora, usando o resultado do Teorema 1,
percebemos que obter mı́nimo custo computacional é equivalente a resolver o problema do fluxo
máximo.
Também, foi implementado o algoritmo highest label preflow-push em linguagem computacional
C++.
3. Conclusão
Estudamos os algoritmos mais conhecidos de fluxo máximo, e obtemos o consumo de tempo
destes algoritmos. Apresentamos ainda uma aplicação ligada a otimização do custo de execução
de uma lista de processos em uma estrutura com dois processadores. Também, realizamos a
implementação do algoritmo mais eficiente conhecido no momento para o problema do fluxo
máximo.
Referências
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
R. E. Bradley and C. E. Sandifer, Leonhard Euler: Life, Work and Legacy. Elsevier Science, 2007.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, 1984.
R. Diestel, Graph Theory. Springer-Verlag New York, 2006.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall,
1993.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. The MIT Press, 2001.
L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,” Canadian Journal of Mathematics, no. 8, pp.
399–404, 1956.
A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum flow problem,” Journal of the ACM, vol. 35, pp.
921–940, 1988.
A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing. Pearson, 2003.