Algoritmo de Fluxo Máximo

Fluxo Máximo
Algoritmo de Ford-Fulkerson

Alberto Emanuel da Silva        

 Departamento de Informática – Universidade Federal Tecnológica Federal do Paraná – Campus Ponta Grossa (UTFPR)
Av. Monteiro Lobato, s/n - Jardim Carvalho, Ponta Grossa - PR, 84016-210

[e-mail]

Abstract. This article discusses the problem of maximum flow in simple graphs, oriented and with evaluated edges. The use of a known algorithm to solve the problem of "maximum paths" and a brief discussion about its complexity.

Resumo. Este artigo comenta sobre o problema do fluxo máximo em grafos simples, orientados e com arestas valoradas. O uso de um algoritmo conhecido para resolver o problema de “caminhos máximos” e uma breve discussão sobre sua complexidade.

1. Introdução

Da mesma forma que podemos elaborar um modelo de um mapa rodoviário como um grafo orientado com a finalidade de encontrar o menor caminho de um ponto até outro, também podemos interpretar um grafo orientado como um “fluxo de rede” e usá-lo para responder a perguntas sobre fluxos de materiais. O fluxo em redes pode ser usado para modelar líquidos fluindo por tubos, peças por linhas de montagem, corrente por redes elétricas, informações por redes de comunicação e assim por diante. Cada aresta orientada em um fluxo de rede pode ser imaginada como um canal por onde o material vai passar, cada canal tem uma capacidade estabelecida, dada como uma taxa máxima na qual o material poderá fluir pelo canal, como por exemplo         duzentos galões de liquido por hora através de um tubo ou vinte ampères de corrente elétrica por um fio.         (CORMEN, 2002)

Partindo deste princípio, o problema do fluxo máximo consiste em encontrar caminhos máximos de uma origem s até um destino t, a fim de que passem por estes caminhos os maiores valores possíveis de fluxo.

2. Fluxo Máximo (The Maximum Flow Problem)

Um grafo capacitado é um grafo com números positivos associados as suas arestas, este número associado a aresta é chamado de capacidade da aresta, agora considere dois vértices especiais Origem e Destino, respectivamente s e t, o objetivo é encontrar o fluxo máximo de uma rede entre esses dois vértices. Já citados alguns exemplos, também pode ser modelado para maximizar o fluxo de óleo por oleodutos (a fim de aumentar o escoamento da extração), maximizar o fluxo de veículos através de uma rede de transportes, entre muitas outras aplicações.

Um algoritmo eficiente para a solução deste problema é baseado em dois conceitos intuitivos; primeiro uma Rede Residual ou Grafo Residual, os valores das arestas da rede na figura 1 representam as capacidades máximas de cada vértice e seus respectivos fluxos, os valores dos vértices da figura 2 representam os resíduos, ou seja, a diferença entre a capacidade e o fluxo do vértice; Segundo um Caminho de Aumento, é um caminho orientado a partir de uma origem s para o destino na Rede Residual todo arco deste caminho possuindo capacidade positiva. A menor capacidade deste Caminho de Aumento é popularmente chamando de “gargalo”, ou seja, onde está a dificuldade no escoamento do fluxo, a aresta que comporta menor fluxo no Caminho de Aumento.

[pic 1]

Figura 1

[pic 2]

Figura 2

3. Algoritmo/Método de Ford-Fulkerson

Esta seção apresenta o método de Ford-Fulkerson, chamado de método pois engloba diversas implementações com variados tempos de execução. O nome do método foi escolhido em honra de Lester Randolph Ford, Jr e Delbert Ray Fulkerson, desenvolvedores do método. Sua história está relacionada à análise da rede ferroviária da União Soviética, tanto por russos como também por americanos nas décadas de 1930, 1940, e 1950. Como vimos anteriormente neste documento, a solução do problema de fluxo é baseada em dois conceitos, o método de Ford-Fulkerson, usa também o conceito de corte mínimo, é o particionamento do Grafo original onde o valor de qual        quer fluxo é menor que a capacidade de qualquer corte.

3.1 Redes Residuais

Dados um fluxo em uma rede e um fluxo, a rede residual consiste em arestas que podem admitir mais fluxo. De modo mais formal, suponha que temos um fluxo em rede G=(V, E) com origem s e destino t; seja f um fluxo em G, e considere um par de vértices u,v ∈ V. A quantidade de fluxo         adicional que podemos empurrar desde u até v antes de exceder a capacidade c (u, v) é a capacidade residual de (u,v) dada por (CORMEN, 2002):

[pic 3]

3.2 Caminhos Aumentantes

Dados um fluxo em rede G = (V, E) e um fluxo f, um caminho aumentante é um caminho simples desde a origem s ate t na rede residual Gf. Pela definição de rede residual, cada aresta (u, v) em um caminho aumentante admite algum fluxo positivo adicional de u até v sem violar a restrição de capacidade sobre a aresta.

Para encontrar um caminho aumentante, executa-se uma BFS no grafo G como mostra a figura 3 (será utilizada a busca em relação aos vértices de G em ordem crescente), e a aresta de gargalo presente nesse caminho, será a quantidade máxima de fluxo que podemos aumentar em G.

[pic 4]

Figura 3

Após a execução da BFS o caminho (descrito pelas arestas na cor cinza) 0 > 1 > 2, foi encontrado, com capacidade residual máxima de 2, pois a capacidade da aresta (1,2) é a menor entre o caminho. Assim essa capacidade será usada na criação das arestas residuais, que será utilizada para “empurrar” o fluxo máximo.