Fluxo em Redes: do Caminhão ao Máximo da OTAN

Hoje mergulhei em um dos temas mais fascinantes da Teoria dos Grafos: fluxo em redes.

Mais do que uma abstração matemática, esse conceito aparece em situações muito concretas — da logística de caminhões até a coordenação militar da OTAN

O que é uma Rede de Fluxo?

Podemos imaginar uma rede de fluxo como um sistema de canos de água ou de caminhões em estradas:

  • Existe uma fonte (source) que gera o recurso.

  • Um sorvedouro (sink) onde esse recurso precisa chegar.

  • E arestas com capacidades que limitam quanto pode ser transportado por cada conexão.

Três propriedades fundamentais governam esse sistema:

  1. Conservação: tudo o que entra em um nó intermediário precisa sair (não há estoque local).

  2. Antissimetria: o fluxo de ida e volta se cancelam (se A envia 4 para B, então B envia –4 para A).

  3. Valor do fluxo: corresponde ao total que sai da fonte (ou entra no sorvedouro).

Rede Residual: onde a mágica acontece

Quando já usei parte de uma estrada, sempre sobra a possibilidade de:

  • Usar o que restou (capacidade residual).

  • Desfazer parte do caminho (voltar com fluxo).

Exemplo:

  • Capacidade A→B = 10.

  • Se já mandei 7, sobram 3 no sentido A→B.

  • E existe agora a possibilidade de “devolver até 7” pelo caminho B→A.

Essa estrutura, chamada rede residual, é a base de todos os algoritmos de fluxo máximo.

Caminhos Aumentantes

Na rede residual, procuramos caminhos do início ao fim que ainda têm espaço. Se encontramos, empurramos mais fluxo. Quando não há mais, atingimos o fluxo máximo.

 Algoritmos de Fluxo Máximo

  • Ford-Fulkerson: empurra fluxo repetidamente por caminhos aumentantes até saturar.

  • Edmonds-Karp: garante eficiência escolhendo sempre o caminho mais curto (BFS).

  • Dinitz: organiza a rede em camadas (level graph) e empurra blocos de fluxo.

  • Push-Relabel: permite excesso temporário em nós, usando a ideia de alturas para “empurrar” recursos.

Cada um tem aplicações práticas diferentes, mas todos partem da mesma ideia: expandir até não haver caminho aumentante.

O Exemplo da OTAN

Para fixar, apliquei esses conceitos em um cenário de logística inspirado na OTAN:

  • Fontes: Estados Unidos e Alemanha (produção).

  • Hubs: Rotterdam, Nápoles e República Tcheca (trânsito).

  • Sorvedouros: Estados Bálticos, Polônia Oriental e Romênia (linhas de defesa).

  • Capacidades: limites de rotas (portos, estradas, ferrovias).

Esse exercício mostrou como gargalos (bottlenecks) determinam o fluxo máximo que chega a cada frente, independentemente da demanda ou da capacidade de produção inicial.

 Meu Aprendizado do Dia

  1. O fluxo máximo não depende apenas da produção ou da demanda, mas das arestas que conectam a rede.

  2. A rede residual é a chave para entender como o fluxo pode crescer ou ser revertido.

  3. Gargalos são inevitáveis — e entendê-los é essencial para otimizar qualquer sistema: logística, internet ou até redes de energia.

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Questão 2 – Quiz sobre Interpretação de Estrutura

No grafo de emendas parlamentares, você encontra que apenas 10% dos vértices estão em SCCs com mais de 3 nós, e os outros 90% estão em SCCs unitários. Analise as afirmações: A rede apresenta alta reciprocidade estrutural, já que a maioria dos nós pertence a SCCs. O fato de existirem muitos SCCs unitários indica baixa reciprocidade estrutural. Apenas olhar o grau de entrada e saída dos nós seria suficiente para explicar essa distribuição de SCCs. Emendas que formam SCCs maiores podem indicar blocos fechados de influência política. Qual alternativa está correta? A) Apenas 1 e 2 são verdadeiras. B) Apenas 2 e 4 são verdadeiras.  C) Apenas 1, 3 e 4 são verdadeiras. D) Apenas 2, 3 e 4 são verdadeiras. E) Nenhuma das anteriores.
Leia mais

Fofoca, Vinho e Redes

Nos últimos dias, fiquei com uma dúvida interessante ao ler um exemplo do livro de redes: a história da festa em que alguém descobre qual é o melhor vinho e essa informação acaba se espalhando entre os convidados. A minha primeira interpretação foi: “ah, claro, isso mostra como a fofoca se espalha rápido”. Mas, na aula, o professor me corrigiu — e aí começou meu aprendizado. O que eu entendi depois? O texto, na verdade, está descrevendo o modelo de redes aleatórias (Erdős–Rényi). Nesse modelo: As conexões entre as pessoas surgem ao acaso. A propagação da informação só decola quando a rede atinge um limiar crítico de conectividade . Nesse ponto, aparece a chamada componente gigante — e qualquer informação consegue se espalhar para quase todos. Esse é o momento em que a rede “ganha vida” : de repente, ela deixa de ser um conjunto de pares isolados e passa a funcionar como um todo conectado. As redes aleatórias são a base, mas na realidade não descrevem as redes sociais humanas. Isso por...
Leia mais

Questão 3 - Quiz sobre Fluxo em Redes

NATO Logistics Flow — Quiz Question NATO is coordinating the shipment of military supplies to reinforce its eastern flank. Units are produced in the United States and Germany , entering Europe through the ports of Rotterdam and Naples . From there, they move to the logistics hubs of Rotterdam and the Czech Republic , with final delivery to three defense lines: Baltic States (demand 50) , Eastern Poland (demand 60) , and Romania (demand 40) . Capacities (in units/week): US → Rotterdam : 15 US → Naples : 15 Germany → Rotterdam : 15 Germany → Czech Republic : 15 Rotterdam → Baltics : 20 Rotterdam → Eastern Poland : 15 Czech Republic → Eastern Poland : 15 Czech Republic → Romania : 15 Naples → Romania : 10 Based on the maximum flow model in directed graphs : What is the maximum supply that can reach Romania ? Why can Eastern Poland not receive more than 30 units, even if production is sufficient at the sources? If the Baltic States demand 50 but can o...
Leia mais