Fluxos em redes

Questões-guia:

1. Problemas de fluxo máximo são estudados em certos tipos especiais de grafos chamados redes.  O que é uma rede?  O que é um fluxo numa rede?  Como se define o valor de um fluxo?
2. Cormen evita arestas antiparalelas no grafo inicial, e explica como eliminá-las.  Uma abordagem alternativa, que permite arestas antiparalelas no grafo inicial, é dada por Goldberg e Tarjan num artigo de 1988.  Quais as diferenças entre as duas abordagens?
3. O que é a rede residual?  Ela tem arestas antiparalelas?  Curiosidade: como se relacionam o fluxo máximo no grafo inicial com o fluxo máximo na rede residual?
4. O que é um caminho aumentante numa rede residual?  Como ele é usado no método de Ford-Fulkerson?
5. O que é um corte numa rede?  Como se define sua capacidade?  Qual a relação entre capacidades de cortes e valores de fluxos?
6. O que diz o teorema Max-Flow Min-Cut?  Como encontrar um corte mínimo numa rede residual sem caminho aumentante?
7. Como funciona o algoritmo de Edmonds-Karp?  Qual é sua complexidade?
8. Como se pode reduzir o problema de achar um emparelhamento máximo num grafo bipartido ao problema de fluxo máximo?  Onde entra o teorema da integralidade nesta redução?

Exercícios:

1. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.1 do Cormen.  O valor do fluxo deu igual ao do livro?  Qual foi o corte mínimo retornado pelo algoritmo?
2. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.3b do Cormen.  Como você codificou as capacidades infinitas?  Quanto deu o fluxo máximo?
3. Use um algoritmo de fluxo máximo do LEMON para achar um emparelhamento de cardinalidade máxima no grafo bipartido da Figura 26.8a do Cormen.