Fluxo máximo e corte mínimo

Fluxo máximo e corte mínimo

Uma rede de fluxo é um grafo dirigido em que cada aresta tem uma capacidade (o peso). Há uma fonte S, de onde o fluxo sai, e um sumidouro T, onde ele chega. O problema é mandar o máximo de fluxo de S a T sem passar de nenhuma capacidade, e sem que sobre ou falte nada nos vértices do meio.

Caminhos aumentantes

O algoritmo de Edmonds-Karp repete: procura um caminho de S a T em que ainda sobra capacidade em todas as arestas (usando busca em largura, que dá o caminho com menos arestas), empurra a maior quantidade possível por esse caminho, que é o gargalo (a menor capacidade sobrando no caminho), e atualiza as capacidades. Quando não há mais caminho, o fluxo é máximo.

A rede residual faz as contas corretas: empurrar fluxo por uma aresta também cria capacidade no sentido contrário, que permite desfazer fluxo mais tarde. Por isso o algoritmo pode corrigir escolhas feitas antes.

Corte mínimo

Um corte separa os vértices em dois lados, com S de um lado e T do outro. Sua capacidade é a soma das capacidades das arestas que saem do lado de S. Todo fluxo é limitado pela capacidade de qualquer corte, então o fluxo máximo é menor ou igual à capacidade mínima de corte. O teorema do fluxo máximo = corte mínimo diz que a igualdade sempre vale, e o algoritmo a alcança. Ao fim da animação, o painel mostra o corte encontrado: o conjunto de vértices alcançáveis por S na rede residual.

Onde aparece

Redes de transporte, distribuição de água e energia, emparelhamentos e seleção de projetos com recursos são problemas de fluxo.