Calculadora de Fluxo em Rede (Fluxo Máximo)

Calculadora de Fluxo em Rede (Fluxo Máximo)

A Calculadora de Fluxo em Rede e Fluxo Máximo computa o fluxo máximo de uma fonte escolhida s para um sumidouro escolhido t em qualquer rede direcionada com capacidades. Por trás dos panos, ela executa o método de Ford-Fulkerson com caminhos de aumento por busca em largura (o algoritmo de Edmonds-Karp), gravando cada caminho encontrado para que você possa rever todo o processo de decisão uma iteração por vez. A página de resultados também apresenta o corte mínimo — a partição gargalo que prova que o valor do seu fluxo é verdadeiramente ótimo.

O Que É o Problema do Fluxo Máximo?

Uma rede de fluxo é um grafo direcionado G = (V, E) junto com uma função de capacidade c: E → ℝ_≥0. Dois vértices são distinguidos: a fonte s (onde o fluxo se origina) e o sumidouro t (onde ele é consumido). Um fluxo f é qualquer atribuição f(u, v) ≥ 0 nas arestas que obedece a:

O problema do fluxo máximo busca o fluxo f que maximiza |f|. Intuitivamente: se as arestas fossem canos de água com as capacidades dadas, quantos litros por segundo você conseguiria enviar de s para t?

Como o Algoritmo Funciona — Ford-Fulkerson com BFS

O algoritmo mantém um grafo residual ao lado do fluxo atual. Para cada aresta (u, v) com capacidade c e fluxo atual f, o grafo residual contém:

• uma aresta residual direta (u, v) com capacidade c − f (quanto mais ainda pode ser empurrado), e
• uma aresta residual reversa (v, u) com capacidade f (quanto do fluxo comprometido ainda pode ser cancelado).

A cada iteração, ele realiza uma busca em largura (BFS) de s para t sobre o grafo residual. Se um caminho for encontrado, a menor capacidade de aresta no caminho — o gargalo — é adicionada ao fluxo em cada aresta direta e subtraída em cada aresta reversa ao longo do caminho. Isso é chamado de caminho de aumento. Quando a BFS não consegue mais alcançar t, o fluxo atual é o ótimo.

Usar BFS (em vez de uma busca de caminho arbitrária) transforma o Ford-Fulkerson em Edmonds-Karp, com um tempo de execução garantido de O(V · E²). Isso também garante a terminação em capacidades irracionais, o que o Ford-Fulkerson simples não faz.

O Teorema do Fluxo Máximo e Corte Mínimo

Um corte é uma partição dos vértices em dois conjuntos (S, T) com s ∈ S e t ∈ T. Sua capacidade é a soma das capacidades das arestas que vão de S para T:

O teorema do fluxo máximo e corte mínimo (Ford & Fulkerson, 1956) afirma:

Esta ferramenta encontra o corte mínimo automaticamente. Após a terminação de Edmonds-Karp, ela executa mais uma BFS a partir de s no grafo residual; os vértices alcançados formam S, o restante forma T, e cada aresta cruzando S → T no grafo original está saturada. Suas capacidades somam exatamente o valor do fluxo máximo — visível no resultado principal como "Capacidade de corte mínimo ✓ confirma a otimalidade".

Recursos Criados para o Aprendizado

• Animação passo a passo. Reveja cada caminho de aumento com controles de play, pausa e passo. Veja qual caminho o BFS escolheu, qual aresta foi o gargalo e como o total acumulado cresceu.
• Três matrizes sincronizadas. Alterne entre a matriz de capacidade C, a matriz de fluxo final f e a matriz residual C − f — as três imagens que juntas caracterizam qualquer fluxo.
• Visualização da partição de corte mínimo. Os vértices do lado S e do lado T são listados como fichas, com as arestas saturadas que cruzam destacadas em vermelho.
• Tabela de aresta por aresta. Para cada aresta: capacidade, fluxo, residual, barra de utilização e um indicador de saturação.
• Layout em camadas da esquerda para a direita. O desenho do grafo é calculado a partir das distâncias BFS da fonte, de modo que a água visivelmente "flui" da esquerda para a direita — exatamente como os livros didáticos desenham.

Formatos de Entrada

1. Lista de arestas com capacidades

Uma aresta por linha. A forma com seta é a mais legível, mas várias alternativas funcionam:

Também aceito: A, B, 10 · A B 10 · A -> B , 10. Múltiplas arestas entre o mesmo par são somadas.

2. Matriz de capacidade

Uma linha por linha, valores separados por espaços ou vírgulas. A entrada C[i][j] é a capacidade da aresta do vértice i para o vértice j. Use 0 para "sem aresta". A matriz deve ser quadrada e a diagonal deve ser 0 (sem auto-loops).

Insira os rótulos dos vértices correspondentes no campo Rótulos da matriz (separados por vírgula ou espaço). Se omitidos, os rótulos padrão serão S, A, B, …, T.

Aplicações do Fluxo Máximo

Exemplo Prático

O exemplo rápido "Livro Didático" codifica uma rede de 6 nós com fonte S e sumidouro T. A execução do Edmonds-Karp produz quatro caminhos de aumento:

1. S → A → B → T com gargalo 4 (a aresta A-B é a limitadora). Total acumulado: 4.
2. S → A → D → T com gargalo 6. Total acumulado: 10.
3. S → C → D → T com gargalo 4 (a aresta D-T agora é a limitadora, restando apenas 4). Total acumulado: 14.
4. S → C → D → B → T com gargalo 5. Total acumulado: 19.

O algoritmo para — não existem mais caminhos de aumento. O corte mínimo é (S = {S, C}, T = {A, B, D, T}) com as arestas cruzadas S → A (capacidade 10) e C → D (capacidade 9), somando 19 — exatamente o valor do fluxo máximo.

Como Usar Esta Calculadora

1. Escolha o formato de entrada usando as abas — lista de arestas (recomendado) ou matriz de capacidade.
2. Insira sua rede. Você pode começar por um exemplo rápido e modificá-lo. Para a entrada de matriz, também forneça os rótulos se quiser nomes diferentes de S, A, B, …, T.
3. Especifique a fonte e o sumidouro (ou deixe em branco para detectar automaticamente S e T).
4. Clique em Calcular Fluxo Máximo. A página de resultados mostra o valor do fluxo máximo, a partição do corte mínimo, uma visualização em camadas do grafo, cada caminho de aumento, uma tabela de utilização de arestas e três matrizes (capacidade, fluxo, residual).
5. Reproduza a animação abaixo do grafo para rever as decisões do algoritmo. Clique em qualquer passo do caminho de aumento para pular diretamente para ele.

Limites

• Vértices: até 30 — mantém a visualização e as matrizes legíveis.
• Arestas: até 200.
• Capacidades: não negativas, até 10⁹. Capacidades fracionárias são permitidas.
• Sem auto-loops. Auto-loops não transportam fluxo em uma formulação padrão de fluxo máximo e são rejeitados.

Perguntas Frequentes

O que é o problema do fluxo máximo?

Dado uma rede direcionada onde cada aresta tem uma capacidade não negativa, o problema do fluxo máximo pergunta: quanto fluxo pode ser empurrado de um vértice de origem designado s para um vértice de destino designado t, sujeito às regras de que o fluxo em cada aresta não pode exceder sua capacidade e o fluxo que entra em cada vértice (que não seja a fonte ou o sumidouro) deve ser igual ao fluxo que sai dele? A resposta é chamada de valor de fluxo máximo.

O que é o método de Ford-Fulkerson?

Ford-Fulkerson é uma técnica geral para computar o fluxo máximo. Ele encontra repetidamente um caminho de aumento da fonte ao sumidouro no grafo residual e empurra o máximo de fluxo possível ao longo desse caminho (a capacidade do gargalo), atualizando então o grafo residual. O procedimento termina quando não existe mais nenhum caminho de aumento. Quando implementado com busca em largura (BFS) para seleção de caminhos, é chamado de Edmonds-Karp e roda em tempo O(V · E²).

O que é o corte mínimo de uma rede de fluxo?

Um corte é uma partição dos vértices em dois conjuntos S e T de modo que a fonte esteja em S e o sumidouro esteja em T. A capacidade do corte é a soma das capacidades das arestas de S para T. Um corte mínimo é um corte de capacidade mínima. O famoso teorema do fluxo máximo e corte mínimo prova que o valor do fluxo máximo é sempre igual à capacidade do corte mínimo, então encontrar um lhe dá o outro gratuitamente.

O que é o grafo residual?

O grafo residual rastreia quanto mais fluxo ainda pode ser empurrado em cada aresta. Para cada aresta original (u, v) com capacidade c e fluxo atual f, o grafo residual contém uma aresta direta (u, v) com capacidade c minus f (capacidade restante) e uma aresta reversa (v, u) com capacidade f (fluxo cancelável). Um caminho de aumento utiliza arestas do grafo residual, permitindo que o algoritmo desfaça decisões anteriores.

Por que a ferramenta usa BFS para caminhos de aumento?

Escolher caminhos de aumento com busca em largura (Edmonds-Karp) garante a terminação em tempo polinomial, independentemente das capacidades das arestas. O Ford-Fulkerson simples com uma estratégia de busca de caminho arbitrária pode entrar em loop por um número exponencial de iterações em entradas patológicas e, em capacidades irracionais, pode nem terminar. O BFS também produz caminhos de aumento mais curtos, que são mais fáceis de ler e entender.

O que significa uma aresta saturada?

Uma aresta está saturada quando seu fluxo é igual à sua capacidade, portanto, nenhum fluxo adicional pode ser empurrado por ela. Arestas saturadas são gargalos da rede, e cada corte mínimo consiste inteiramente de arestas saturadas do lado S para o lado T do corte. A ferramenta destaca as arestas saturadas em vermelho para que você possa ver a estrutura do gargalo rapidamente.

Leitura Adicional

• Problema do fluxo máximo — Wikipédia
• Algoritmo de Ford–Fulkerson — Wikipédia
• Algoritmo de Edmonds–Karp — Wikipédia
• Teorema do fluxo máximo e corte mínimo — Wikipédia