Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fluxo em Grafos - Coggle Diagram
Fluxo em Grafos
🔹 Conceito
. Representa a transferência de um recurso quantificável (como água, energia, dados, veÃculos, etc.) de uma origem (fonte) até um destino (sumidouro).
. O fluxo percorre arestas com capacidades máximas (limites de quanto pode passar).
-
🔹 Modelagem
Se houver arestas em sentidos opostos (u,v) e (v,u), cria-se um novo vértice intermediário para eliminar arestas antiparalelas.
Super-fonte e super-destino: Usados quando há múltiplas origens ou destinos.
Ligados às fontes/destinos com capacidade infinita.
-
-
-
🔹 Exemplo
Em um grafo com várias possibilidades de cortes:
O corte de menor capacidade (c = 23) determina que o fluxo máximo é 23
-