Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fluxo em Grafos e Algoritmo de Ford-Fulkerson - Coggle Diagram
Fluxo em Grafos e Algoritmo de Ford-Fulkerson
1. Conceito Geral
Fluxo em rede: transferência de recursos (produtos, veículos, dados) de um nó origem (s) para um nó destino (t).
Cada aresta possui uma capacidade máxima c(u,v).
O fluxo f(u,v) deve respeitar restrições de capacidade e conservação.
Usado para modelar redes de transporte, comunicação, energia e logística
2. Propriedades do Fluxo
Restrição de capacidade: f(u,v) ≤ c(u,v)
Antissimetria: f(u,v) = –f(v,u)
Conservação de fluxo: o que entra em um vértice = o que sai (exceto s e t).
Fluxo máximo: quantidade máxima possível enviada de s a t sem violar restrições
3. Modelagem
O grafo é orientado e não deve conter arestas antiparalelas.
Se houver (u,v) e (v,u), cria-se um novo nó intermediário para corrigir.
Para múltiplas origens/destinos, cria-se:
Uma super-fonte, ligada a todas as origens;
Um super-sumidouro, ligado a todos os destinos
4. Algoritmo de Ford-Fulkerson
Objetivo: determinar o fluxo máximo em uma rede.
Ideia central: aumentar o fluxo enquanto existir caminho possível de s → t.
Etapas:
Inicializa todas as arestas com fluxo zero.
Procura um caminho aumentante (de s a t) com capacidade disponível.
Determina o valor mínimo de capacidade no caminho.
Aumenta o fluxo nesse caminho e atualiza a rede residual.
Repete até que não exista mais caminho possível.
Quando não há mais caminhos → o fluxo máximo está definido
5. Conceitos Importantes
Rede residual: representa as capacidades ainda disponíveis.
cf(u,v) = c(u,v) – f(u,v)
Caminho aumentante: sequência de vértices de s até t onde cf(u,v) > 0.
Capacidade residual do caminho: o menor cf(u,v) do percurso
6. Cortes e Teorema do Fluxo Máximo
Um corte (S,T) divide o conjunto de vértices em dois subconjuntos:
s ∈ S (origem) e t ∈ T (sumidouro).
A capacidade do corte é a soma das arestas de S → T.
O corte mínimo tem a menor capacidade possível.
Teorema:
“O fluxo máximo é igual ao valor do corte mínimo.”
7. Aplicações
Transporte de produtos e pessoas.
Linhas de montagem e redes elétricas.
Envio de dados, voz e imagem.
Planejamento logístico e rotas industriais