nada

Fluxo em Redes
Erika Morais
Instituto de Informática
Universidade Federal de Goiás

Fluxo em Redes

Definições
Uma rede é um grafo orientado G = (V , E ) em que:
1. a cada aresta e ∈ E está associado um número real positivo c(e) denominado capacidade da aresta e.
2. há dois vértices especiais e distintos s, t ∈ V chamados origem e destino, respectivamente, com as seguintes propriedades:
◮
◮

A origem, s, é uma fonte que alcança todos os outros vértices;
O destino, t é um sumidouro alcançado também por todos.

Fluxo em Redes
Definições
Um fluxo f de s a t em G é uma função que associa a cada aresta e ∈ E um número real não negativo f (e) satisfazendo às seguintes condições: ◮

0 ≤ f (e) ≤ c(e), para toda aresta e ∈ E

◮

para todo vértice v = s, t: f (w1 , v ) = w1 f (v , w2 ) w2 Fluxo na rede
O valor do fluxo na origem é denominado valor do fluxo na rede e denotado por f (G ).

Fluxo Máximo em Redes

O problema de Fluxo Máximo
◮

O valor do fluxo em uma rede pode variar de um mínimo igual a zero até um certo máximo.

◮

O problema do fluxo máximo consiste em, dada uma rede, determinar o fluxo de valor máximo.

Fluxo Máximo em Redes

Aplicações:
◮

Escoamento de água de uma origem s a um destino t, através de uma rede de tubulação.

◮

Correntes por redes elétricas.

◮

Informações por redes de comunicação.

Fluxo Máximo em Redes

Exemplo 1-a) Um fluxo em rede
89:;
?>=< a ③a y ❉❉❉
❉❉
③③
❉❉ 3(2)
③③
4(2) ③③
❉❉
❉❉
③③ 1(1) 2(1)
❉❉
③③
❉❉
③③
③

❉4
③③
?>=<
89:;
?>=<
G 89:;
89:;
?>=< s❂ dt d b ❃❃
❂❂ 2(2) ✁✁
✁✁
❃❃4(3)
❂❂
✁✁
❃❃
✁✁
❃0 ✁✁✁ 5(2)
3(0) ❂❂
✁✁ 3(1)
0 ✁
89:;
?>=<
89:; o
?>=<
c d 3(1)

Fluxo Máximo em Redes

Exemplo 1-b) Um fluxo ilegal
89:;
?>=< a ③a y ❉❉❉
❉❉
③③
❉❉ 3(2)
③③
4(2) ③③
❉❉
❉❉
③③ 1(1) 2(1)
❉❉
③③
❉❉
③③
③

❉4
③③
?>=<
89:;
?>=<
G 89:;
89:;
?>=< s❂ dt d b ❃❃
❂❂ 2(2) ✁✁
✁✁
❃❃4(3)
❂❂
✁✁
❃❃
✁✁
❃0 ✁✁✁ 5(3)