{djcs, hcs}@cin.ufpe.br

Diêgo João Costa Santiago

Hallan Cosmo dos Santos

O Problema Fluxo MáximoO que é o problema de encontrar fluxo

máximo?Uma empresa possui uma fábrica localizada na

cidade X onde são fabricados produtos que necessitam ser transportados para o centro de distribuição na cidade Y.

Dados as estradas direcionadas que ligam os pares de cidades do país, bem como o número máximo de caminhões que pode se conduzir ao longo de cada estrada. Qual é o número máximo de caminhões que a empresa pode enviar para o centro de distribuição?

O Problema Fluxo MáximoDe acordo com a Teoria dos Grafos:

Dado uma rede – um grafo direcionado, em que cada aresta tem uma capacidade c associada a ele, um vértice de partida (source) e um vértice de chegada (sink). Devemos associar um valor não-negativo f , com f <= c para cada aresta, onde para cada vértice, exceto o source e o sink, a soma dos valores associados às arestas que entram deve ser igual a soma dos valores associados às arestas que o deixam. Nós chamaremos f de o fluxo ao longo da aresta. Devemos maximizar a soma dos valores associados às arestas que deixam o source, o fluxo total da rede.

O Problema Fluxo MáximoA Imagem abaixo mostra uma solução ótima

para uma instância deste problema. Cada aresta apresentada com f/c .

Como resolver o problemaPrecisamos de duas definições básicas para

entender como resolver fluxo em redes:A rede residual

Tem o mesmo número vértices da rede original e uma ou duas arestas para cada aresta na rede original. Se o fluxo ao longo da aresta a-b é menor do que a capacidade, existe uma aresta a-b com uma capacidade igual à diferença entre a capacidade e o fluxo (capacidade residual), e se o fluxo é positivo há uma aresta b-a com a capacidade igual ao fluxo de a-b.

O caminho de aumento

Como resolver o problema

Como resolver o problema

Como resolver o problema

Como resolver o problema

Problema Resolvido!O exemplo sugeriu o seguinte algoritmo:

Inicie com nenhum fluxo em todas as arestas e aumente o fluxo total na rede enquanto há um aumento caminho desde o source até o sink - um caminho de aumento na rede residual.

O algoritmo (conhecido como o método Ford-Fulkerson) sempre termina: devido às capacidades e fluxos inteiros não-negativos, a cada passo obtemos um novo fluxo que está mais próximo do máximo.

Problema Resolvido!A função max_flow será similar a esta,

independente do método que utilizamos para encontrar caminhos de aumento:

Algoritmos para Caminho de AumentoO algoritmo Ford-Fulkerson descrito obtém o

resultado correto, não importa como resolvermos o sub-problema de encontrar um caminho de aumento.

No entanto, a cada novo caminho podemos aumentar o fluxo total muito pouco, daí o número de iterações do algoritmo pode ser muito grande se nos descuidarmos ao escolher qual caminho de aumento o algoritmo deve usar.

Algoritmos para Caminho de AumentoAgora é necessário uma implementação para

a função find_path.A primeira abordagem que me vem à mente é

a de usar uma busca em profundidade, pois ela é provavelmente a mais fácil de implementar. Infelizmente, seu desempenho é muito ruim em algumas redes, e normalmente é menos preferida em relação à que vamos mostrar a seguir.

Algoritmos para Caminho de AumentoA próxima idéia na simplicidade é uma usar uma

busca em largura. Sabemos que esta pesquisa normalmente retorna o

caminho mais curto em um grafo não-ponderado. Essa era a base da idéia de Edmonds-Karp.

No psedo-código a seguir, nós iremos basicamente: Encontrar o menor caminho do source ao sink e

determinar a capacidade da aresta de menor capacidade desse caminho. Então, para cada aresta, ao longo do caminho, reduzimos a capacidade dela e aumentarmos a capacidade da aresta oposta.

Algoritmos para Caminho de Aumento

Algoritmos para Caminho de Aumento

Algoritmos para Caminho de AumentoComo podemos ver, isto é muito fácil de

implementar.Devido ao O(E) da execução da Busca em

Largura (implementada com listas de adjacência), o pior caso do algoritmo é O (V*E²), mas, geralmente, o algoritmo roda num tempo muito melhor.

Problemas RelacionadosComo reconhecer problemas de fluxo

máximo? Muitas vezes eles são difíceis de detectar.

Geralmente, precisamos prestar muita atenção nas restrições quando achamos que temos uma solução baseada em fluxo máximo - que deve, pelo menos, sugerir uma solução O(N³). Se o número de vértices é grande, um outro algoritmo (como a programação dinâmica ou o guloso), pode ser mais adequado.

Problemas RelacionadosProblema 1:

A descrição do problema poder sugerir múltiplos sources e/ou múltiplos sinks.

Problemas RelacionadosProblema 1:

A descrição do problema poder sugerir múltiplos sources e/ou múltiplos sinks.

Problemas RelacionadosProblema 2:

E se também fosse dado o número máximo de caminhões que podem passar através de cada uma das cidades do país (exceto as cidades onde a fábrica e o centro de distribuição estão localizados)? Em outras palavras, se tivermos de lidar com a capacidade dos vértices também.

Problemas RelacionadosProblema 2:

E se também fosse dado o número máximo de caminhões que podem passar através de cada uma das cidades do país (exceto as cidades onde a fábrica e o centro de distribuição estão localizados)? Em outras palavras, se tivermos de lidar com a capacidade dos vértices também.

Problemas RelacionadosProblema 3:

E se, além das capacidades nas cidades, as estradas se tornarem não-direcionadas?

Problemas RelacionadosProblema 3:

E se, além das capacidades nas cidades, as estradas se tornarem não-direcionadas?

Emparelhamento Máximo em Grafos BipartidosEsta é uma das mais importantes aplicações

de fluxo máximo, e muitos problemas podem ser reduzidos a ela. O emparelhamento em um grafo bipartido é um conjunto de arestas tal que nenhum vértice é tocado por mais de uma aresta. Obviamente, um emparelhamento com máxima cardinalidade é um emparelhamento máximo. Para um grafo geral, este é um problema bem mais difícil de resolver.

Emparelhamento Máximo em Grafos BipartidosA redução para fluxo máximo é bem simples,

vamos a um exemplo:Seja o grafo bipartido: o primeiro conjunto de

vértices de empregados, enquanto o segundo contém um conjunto de trabalhos a ser feito. Existe uma aresta de um empregado para cada um dos trabalhos que podem ser atribuídos a ele.

Emparelhamento Máximo em Grafos BipartidosAo ver o grafo, percebemos que este

problema é semelhante a encontrar o fluxo máximo num grafo de múltiplos sources e multiplos sinks, que já resolvemos.

Algoritmo de Hopcroft-KarpAgora descreveremos um algoritmo mais

rápido. A sua complexidade é .

Dado um grafo bipartido não-direcionado G(X,Y), seja M um emparelhamento em G. Dizemos que um caminho simples P em G é um caminho de aumento com respeito a M se ele começa em um vértice não emparelhado em X, termina em um vértice não emparelhado em Y e suas arestas pertencem alternadamente a M e a M.

Algoritmo de Hopcroft-KarpAqui está ele:

Algoritmo de Hopcroft-KarpProblema 1:

Precisamos de um algoritmo O(E) para encontrar um conjunto máximo de caminhos disjuntos de aumento, P1, P2, P3,...

Problema 2:Mostrar que o número máximo de iterações do

algoritmo é 2 . E concluir que o tempo de execução total do Hopcroft-karp é

ReferênciasCormen, Thomas H.; Leiserson, Charles E.;

Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms, second edition, MIT Press and McGraw-Hill.

www.wikipedia.comwww.topcoder.com/tc