Fluxos em rede

José afonso
José adelmo
Douglas
rifas

Fluxo em Redes: Ford-Fulkerson - Fluxo Máximo
Trabalho entregue ao professor jeferson como requisito para aprovação na disciplina Teória dos Grafos.

FAA\IESA, 05 de junho de 2013.
Fluxo em redes:
Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta
(u,v)∈ E e tem uma capacidade não negativa c(u,v) ≥ 0. Onde u equivale a origem e v o destino. Em uma rede G=(V,E), cada vértice reside em algum caminho de u até v.
O Fluxo em redes deve respeitar as três propriedades seguintes:
• Restrição de capacidade: o fluxo que circulará em um grafo deve ser igual ou menor que a capacidade máxima deste fluxo.
F(u,v) ≤ c(u,v).
• Anti-simetria oblíqua: o fluxo em uma direção deve ser igual ao que sai, exceto na origem e no sorvedouro.
Capacidade residual:
A Capacidade Residual é representada por: (cf), onde é a capacidade restante em uma aresta ou arco após passar um fluxo f na mesma. A
Capacidade Residual é dada pela equação:
• Capacidade Residual (cf):
– cf (u, v) = c(u,v) ‐ f (u, v)

Aresta Residual:
Uma Aresta Residual é uma aresta ou arco que pode admitir ainda algum fluxo maior que seja maior que zero. Chama-se Aresta Residual Gf.
Caminhos de aumento:
Dado um fluxo em rede G = (V;E) e um fluxo f, um caminho em ampliação (ou caminhos de aumento) é um caminho simples de s a t na rede residual Gf . A quantidade máxima pela qual o fluxo pode ser aumentado em um caminho de ampliação é chamada de capacidade residual de p, e é expressa por: cf (p) = minfcf (u; v) : (u; v) está em pg
Isso quer dizer que a capacidade residual de um caminho em ampliação p corresponde à menor dentre as capacidades das arestas que fazem parte de p.
Fluxo Máximo:
Para resolver o problema do fluxo máximo foram propostos os seguintes algoritmos: O método dos caminhos de aumento de Ford e Fulkerson.
Goldberg e Tarjan propuseram um novo método conhecido como método do pré-fluxo.

Algoritmo de Edmonds-Karp