O que são redes de fluxo e como são formadas? Qual o objetivo do estudo de redes de fluxo?
Passo 1
Beleza, vamos recapitular o que o exercício pede e o que precisamos saber.
– Enunciado: “O que são redes de fluxo e como são formadas? Qual o objetivo do estudo de redes de fluxo?”
– Conteúdo: É teoria de grafos aplicada a fluxos, também chamada de “Fluxo Máximo”.
– O que vamos precisar:
– Enunciado: “O que são redes de fluxo e como são formadas? Qual o objetivo do estudo de redes de fluxo?”
– Conteúdo: É teoria de grafos aplicada a fluxos, também chamada de “Fluxo Máximo”.
– O que vamos precisar:
- Entender o que é um grafo direcionado.
- Saber o que são capacidades nas arestas.
- Conhecer as regras de conservação de fluxo.
Passo 2
O que são redes de fluxo?
– É um grafo direcionado onde cada aresta
tem uma capacidade máxima
.
– Temos dois nós especiais:
– É um grafo direcionado
– Temos dois nós especiais:
- Fonte (
), de onde sai o fluxo. - Sumidouro (ou sorvedouro) (
), para onde o fluxo vai.
– Chamamos de função fluxoa quantidade que realmente passa de para .
Passo 3
Como elas são formadas (regras básicas):
- Capacidade: para toda aresta
, - Conservação de fluxo (pra todo vértice
): Ou seja, o que chega em tem que sair de , não sobra nem falta nada.
Passo 4
Qual é o objetivo do estudo?
– A ideia central é achar uma atribuição de valores que respeite as regras acima e maximize o fluxo total saindo de
(ou chegando em
).
– Isso vira o problema do “Fluxo Máximo”:
– A ideia central é achar uma atribuição de valores
– Isso vira o problema do “Fluxo Máximo”:
– Além disso, tem a relação bonita com cortes mínimos (teorema Max-Flow Min-Cut) e várias aplicações:
• Roteamento em redes de computadores
• Distribuição de água ou energia
• Logística de transporte
• Roteamento em redes de computadores
• Distribuição de água ou energia
• Logística de transporte
Resposta
Redes de fluxo são grafos direcionados com capacidades em cada aresta, contendo uma fonte
e um sumidouro
. Elas são formadas impondo-se duas regras: 1) o fluxo
em cada aresta não pode ultrapassar sua capacidade
e 2) em qualquer nó “intermediário” o fluxo que entra deve igualar o que sai. O objetivo de estudar essas redes é descobrir como enviar a maior quantidade possível de fluxo de
até
, respeitando essas regras, o que dá origem ao clássico problema do Fluxo Máximo e suas aplicações práticas.