PAA-14-fluxoEmRedes

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
GRAFOS 
Agenda 
 Fluxos em rede 
 Aplicação 
 Conceitos 
 
 Problema do Fluxo Máximo 
 
 Método clássico de Ford e Fulkerson 
 
 
Introdução 
 Grafos orientados podem ser usados para 
modelar o fluxo de materiais numa rede: 
 Líquidos fluindo por tubos 
 Peças por linhas de montagem 
 Corrente por redes elétricas 
 Informações por redes de comunicação 
 
 O material percorre uma rede desde uma origem, 
onde ele é produzido, até um sorvedor, onde ele é 
consumido 
Introdução 
 No grafo, cada aresta é um canal para o material 
 Cada canal tem uma capacidade estabelecida, ou seja, 
uma taxa máxima na qual o material pode fluir pelo canal 
 200 litros/h de líquido através de um tubo 
 
 Vértices são junções de canais 
 Material também flui pelos vértices 
 
 A origem produz o material numa taxa fixa e o 
sorvedor consome o material na mesma taxa (não há 
acúmulo de material nos vértices) 
Fluxo em rede 
 Um fluxo em rede G = (V, E) é um grafo orientado 
em que cada aresta (u, v) ∈ E tem uma capacidade 
c(u,v) 
 Se (u, v) ∉ E, assume-se que c(u,v) = 0 
 Dentre os vértices, há a origem e o sorvedor 
 ∀v ∈ V, assume-se que existe um caminho entre a 
origem e sorvedor que passa por v 
 Portanto, o grafo é conectado 
 |E| ≥ |V| - 1 
Fluxo em rede: Exemplo 
 Rotas de carregamento de discos de hóquei de 
Vancouver até Winnipeg 
 Apenas c(u,v) caixotes por dia podem ir da cidade u 
para a cidade v 
 
origem 
(fábrica que 
produz os discos) 
sorvedor 
(armazém que 
mantém estoque) 
capacidade 
Fluxo 
 Seja G = (V, E) um fluxo em rede com função de 
capacidade c, s a origem da rede e t um sorvedor 
 
 Um fluxo em G é uma função f:V×V → R que satisfaz as 
seguintes propriedades: 
 Restrição de capacidade: ∀u,v ∈ V, f(u,v) ≤ c(u,v) 
 O fluxo de um vértice até outro não deve exceder a capacidade 
dada 
 Simetria: ∀u,v ∈ V, f(u,v) = -f(v,u) 
 Conveniência de notação que afirma que o fluxo de um vértice u até 
um vértice v é o valor negativo do fluxo no sentido inverso 
 Conservação do fluxo: ∀u ∈ V – {s, t}, Σv∈V f(u, v) = 0 
 O fluxo total para fora de um vértice que não seja a origem e nem o 
sorvedor é 0 
 O saldo em t é igual ao saldo em s com sinal trocado 
Fluxo 
 A quantidade f(u,v) indica o fluxo da rede a partir do 
vértice u até o vértice v 
 Valor positivo, negativo ou nulo 
 
 O fluxo total da rede é |f| = Σv∈V f(s,v) 
 Ou seja, o fluxo total que sai da origem 
 
 Quando nem (u,v) nem (v,u) está em E, então não 
pode haver nenhum fluxo entre u e v 
 f(u,v) = f(v,u) = 0 
 Rotas de carregamento de discos de hóquei 
 Se o arco (u,v) tem f(u,v) > 0: arco é identificado por 
f(u,v)/c(u,v) 
 “/” é um delimitador 
 Se o arco (u,v) tem f(u,v) < 0: arco é identificado por 
c(u,v) 
 
 
 
 
 
 
 Fluxo total: |f| = 19 
Fluxo: Exemplo 1 
Fluxo: Exemplo 2 
 
 
 
 
 
 O fluxo de v1 para v2 é 8 
 Pela propriedade de simetria, o fluxo de v2 para 
v1 é -8 
 No entanto, apenas o fluxo positivo é mostrado 
Fluxo: Exemplo 3 
 
 
 
 
 
 
 O fluxo de v1 para v2 é 8-3 = 5 
 O fluxo de v2 para v1 é 3-8 = -5 
Equivalente 
Redes com várias origens e vários 
sorvedores 
 No exemplo de rotas de carregamento de discos 
de hóquei 
m fábricas {s1, s2, …, sm} 
 n armazéns {t1, t2, …, tn} 
Redes com várias origens e vários 
sorvedores 
 É possível representar 
como uma rede comum, 
com apenas uma origem 
e um sorvedor 
 Adicionar uma super-
origem s’ 
 Fornece tanto fluxo 
quanto desejado para 
as várias origens 
 Adicionar um super-
sorverdor t’ 
 Consome tanto fluxo 
quanto necessário para 
os vários sorvedores 
Problema do Fluxo Máximo 
 Temos um fluxo em rede G com origem s e sorvedor 
t e desejamos encontrar um fluxo de valor máximo 
 Exemplo: Qual o número máximo de carregamentos 
por dia que podem ser enviados de Vancouver para 
Winnipeg? 
Método de Ford-Fulkerson 
 Resolve o problema do fluxo máximo 
 
 É considerado método e não simplesmente um algoritmo 
 
 A idéia básica é aumentar o fluxo iterativamente em uma 
rede até que ele não possa mais ser aumentado 
 
 Para entender, é necessário conhecer os seguintes conceitos 
 Rede residual 
 Caminho aumentante 
 Corte de fluxo em redes 
 Dado um fluxo em rede G = (V, E), a função 
capacidade c, um fluxo f em G, uma fonte s e um 
sorvedor t 
 
 De maneira informal, a rede residual consiste em 
arcos do fluxo em rede que podem admitir mais 
fluxo 
Rede residual: Definição informal 
Rede residual: Definição formal 
 Capacidade residual de (u,v): Quantidade de fluxo 
adicional que podemos empurrar desde u até v antes 
de exceder a capacidade c(u,v) 
 cf(u,v) = c(u,v) – f(u,v) 
 Exemplo: Se c(u,v) = 16 e f(u,v) = 11, podemos aumentar 
f(u,v) em cf (u,v) = 5 unidades antes de excedermos a 
restrição de capacidade sobre o arco (u,v) 
 
 A rede residual induzida por f é Gf = (V, Ef), em que 
Ef = {(u,v) ∈ V×V : cf(u,v) >0} 
Rede residual: Exemplo 
s 
v1 
v2 v4 
t 
v3 
12/12 
11/14 
1
0
 
1
/4
 
7
/7
 
Fluxo de rede G 
Rede residual Gf s 
v1 
v2 v4 
t 
v3 
12 
3 
1
1
 
3
 
7
 
11 
Caminho aumentante 
 Seja G = (V, E) um fluxo em rede e f um fluxo, um 
caminho aumentante p é um caminho de s para t na 
rede residual Gf 
 
 A capacidade residual de um caminho aumentante 
é a quantidade máxima pela qual podemos 
aumentar o fluxo em cada aresta do caminho 
 cf(p) = min{cf(u,v) : (u,v) está em p} 
Caminho aumentante: Exemplo 
Caminho aumentante 
em Gf 
Rede residual Gf 
cf(p) = cf (v2,v3) = 4 
s 
v1 
v2 v4 
t 
v3 
12 
3 
1
1
 
3
 
7
 
11 
s 
v1 
v2 v4 
t 
v3 
12 
3 
1
1
 
3
 
7
 
11 
Podemos transportar até 4 
unidades de fluxo adicional sem 
violar restrição de capacidade 
alguma 
Algoritmo básico de Ford-Fulkerson 
 FORD-FULKERSON(G, s, t) 
1 for cada aresta (u,v) ← E[G] 
2 do f[u, v] ← 0 
3 f[v, u] ← 0 
4 while existir um caminho p de s até t na rede residual Gf 
5 do cf(p) ← min{cf(u,v): (u,v) está em p} 
6 for cada aresta (u,v) em p 
7 do f[u, v] ← f[u, v] + cf(p) 
8 f[v, u] ← - f[u, v] 
Inicializa o fluxo f como 0 
Encontra repetidamente um caminho aumentante p em Gf e amplia o 
fluxo f ao longo de p pela capacidade residual cf(p). Quando não existe 
nenhum caminho aumentante, o fluxo f é um fluxo máximo. 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
Rede residual Gf s 
v1 
v2 v4 
t 
v3 
12 
14 
1
0
 
4
 
7
 
s 
v1 
v2 v4 
t 
v3 
12/12 
11/14 
1
0
 
1
/4
 
7
/7
 
Fluxo de rede G 
(Linhas 1-3: fluxos valem 0; 
logo, cada arco é representado 
apenas por sua capacidade) 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
(a) 
Rede residual Gf inicial com 
um caminho aumentante 
sombreado p 
 
cf(p) = min {16, 12, 9, 14, 4} = 4 
Fluxo resultante da 
adição de cf(p) ao fluxo 
de cada arco em p 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
(b) 
Rede residual Gf resultante de 
(a-2) com um caminho 
aumentante sombreado p 
 
cf(p) = min {12, 10, 10, 7, 20} = 7 
 
Fluxo resultante da 
adição de cf(p) ao fluxo 
de cada arco em p 
(vide figura a-2)Algoritmo básico de Ford-Fulkerson: 
Exemplo 
(c) 
Rede residual Gf resultante de 
(b-2) com um caminho 
aumentante sombreado p 
 
cf(p) = min {13, 11, 8, 13} = 8 
 
Fluxo resultante da 
adição de cf(p) ao fluxo 
de cada arco em p 
(vide figura b-2) 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
 Atenção! 
 
 
 
 
 
 f(v2, v1) = 1- 8 = -7 
 Para aumentar esse f(v1, v2) em 8 unidades 
 f(v2,v1)= 1 – 0 = 1 
 De fato, fdepois – fantes = 1 – (-7) = 1 + 7 = 8 
v1 
v2 
7
/1
0
 
4
 
v1 
v2 
8
/1
0
 
1
/4
 
v1 
v2 
1
0
 
1
/4
 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
(d) 
Rede residual Gf resultante de 
(c-2) com um caminho 
aumentante sombreado p 
 
cf(p) = min {5, 4, 5} = 4 
 
Fluxo resultante da 
adição de cf(p) ao fluxo 
de cada arco em p 
(vide figura c-2) 
Algoritmo básico de Ford-Fulkerson: 
Exemplo 
 Resultado final é a rede residual referente ao fluxo 
obtido em (d) 
(e)