Diêgo João Costa Santiago
Hallan Cosmo dos Santos
{djcs, hcs}@cin.ufpe.br
O Problema Fluxo Máximo
 O 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áximo
 De 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áximo
 A Imagem abaixo mostra uma solução ótima para uma
instância deste problema. Cada aresta apresentada
com f/c .
Como resolver o problema
 Precisamos 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 FordFulkerson) 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 Aumento
O
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 Aumento
 Agora é 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 Aumento
 A 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 Aumento
 Como 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 Relacionados
 Como 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 Relacionados
 Problema 1:
 A descrição do problema poder sugerir múltiplos sources
e/ou múltiplos sinks.
Problemas Relacionados
 Problema 1:
 A descrição do problema poder sugerir múltiplos sources
e/ou múltiplos sinks.
Problemas Relacionados
 Problema 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 Relacionados
 Problema 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 Relacionados
 Problema 3:
 E se, além das capacidades nas cidades, as estradas se
tornarem não-direcionadas?
Problemas Relacionados
 Problema 3:
 E se, além das capacidades nas cidades, as estradas se
tornarem não-direcionadas?
Emparelhamento Máximo em Grafos
Bipartidos
 Esta é 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
Bipartidos
 A 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
Bipartidos
 Ao 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-Karp
 Agora 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-Karp
 Aqui está ele:
Algoritmo de Hopcroft-Karp
 Problema 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ências
 Cormen, Thomas H.; Leiserson, Charles E.; Rivest,
Ronald L.; Stein, Clifford (2001). Introduction to
Algorithms, second edition, MIT Press and McGrawHill.
 www.wikipedia.com
 www.topcoder.com/tc