Grafos: Fluxo em Redes

Introdução Teórica

Problemas de fluxo modelam o transporte de itens através de uma rede com capacidades limitadas. Exemplos incluem tráfego em rodovias, fluidos em canos ou dados na internet.

Conceitos

  • Capacity: Limite de fluxo em uma aresta.
  • Source (s) & Sink (t): Pontos de origem e destino.
  • Residual Graph: Grafo que mostra a capacidade restante (ida) e o fluxo que pode ser cancelado (volta).
  • Max Flow Min Cut Theorem: O fluxo máximo é igual à capacidade do “gargalo” (corte mínimo) que separa origem e destino.

Algoritmo Edmonds-Karp

Implementação do método Ford-Fulkerson usando BFS para encontrar caminhos aumentantes (caminhos com capacidade sobrando). O BFS garante encontrar o caminho com menor número de arestas, o que garante complexidade \(O(V E^2)\).

Problema Clássico

Problema: Minha Camiseta Me Serve? (Matching Bipartido) Link: Beecrowd 1362

Descrição: Voluntários aceitam apenas certos tamanhos de camisetas (ex: M ou G). Temos estoque limitado de cada tamanho. É possível atender a todos?

Solução: Este é um problema de Matching Bipartido, que é um caso especial de fluxo. 1. Crie um nó Fonte e ligue a cada Voluntário (Capac. 1). 2. Ligue cada Voluntário aos Tamanhos que ele aceita (Capac. 1). 3. Ligue cada Tamanho ao Sumidouro com capacidade igual ao estoque daquele tamanho. 4. Se Max Flow == Número de Voluntários, a resposta é “YES”.

Variações e Exercícios

  1. [Comércio de Vinhos na Gergóvia]
    • Foco: Mover fluxo (venda/compra) com custo. Pode ser resolvido com guloso simples se for linear, mas fluxo modela casos complexos.
    • Link: Beecrowd 1661 (Resolvível com Greedy, mas mentalidade de fluxo ajuda).
  2. [Alocação (Matching)]
    • Foco: Encaixar pares com restrições.
    • Link: Beecrowd 1490 (Torres que atacam - Max Independent Set em Bipartido).
  3. [Internet Bandwidth]
    • Foco: Fluxo máximo direto com soma de arestas paralelas.
    • Link: [UVa 820] (Clássico fora do Beecrowd).
Back to top