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: Conservação : tudo o que entra em um nó intermediário precisa sair (não há estoque local). Antissimetria : o fluxo de ida e volta se cancelam (se A envia 4 para B, então B envia –4 para A). 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 possibi...