FLUXOS EM REDES
Grafos e Teoria da Complexidade
Fabio Tirelo
Fluxos em Redes



Considere um material percorrendo um sistema
desde a origem, onde é produzido, até o destino,
onde é consumido
Exemplos de fluxos: líquidos em tubulação, peças
em linhas de montagem, corrente em redes
elétricas, informações em redes
Exemplo: Fábrica em Vancouver (s) e depósito em
Winnipeg (t)
Edmonton
Saskatoon
v1
16
Vancouver
12
v3
20
Winnipeg
s
10
4
9
13
Calgary
v2
14
t
7
v4
4
Regina
GTC - Fabio Tirelo
Fluxos em Redes...





Um Fluxo em Rede G = (V,E) é um grafo dirigido em
que cada aresta (u,v)  E possui uma capacidade
associada c(u,v)  0
Se (u,v)  G, consideramos que c(u,v) = 0
Destacam-se os vértices: s, a origem, e t, o destino
Por conveniência, consideramos que todos os outros
vértices estejam em algum caminho de s para t
Um Fluxo em G é uma função f : V  V  , tal que
 Restrição de capacidade: u,v : f (u,v)  c(u,v)
 Simetria oblíqua: u,v : f (u,v) =  f (v,u)
 Conservação de fluxo: para todo u  V  { s,t }
 f (u, v)  0
vV
GTC - Fabio Tirelo
Fluxos em Redes...

O valor de um fluxo f é dado por:
f 
 f (s, v)
vV

O fluxo total positivo de entrada de um vértice v é
dado por:
f (u , v)

vV
f ( u ,v )  0

O fluxo total líquido de um vértice v é igual ao fluxo
total positivo de saída de v menos o fluxo total positivo
de entrada de v
 Para quais vértices o fluxo total líquido pode ser
diferente de zero?
 Somatório implícito: f ( A, B) 
f (a, b)

aA bB
GTC - Fabio Tirelo
Fluxos em Redes...

Exemplo:
v1
11/16
s
1/4
8/13

10
v2
12/12
4/9
11/14
v3
15/20
t
7/7
v4
4/4
Redes com várias origens e vários destinos
s



s1
v3
s2
s3

t
v4

GTC - Fabio Tirelo
Método de Ford-Fulkersen

O método abaixo apresenta várias implementações
possíveis

Entrada: Grafo G = (V,E), vértices s e t
 Saída: Função de fluxo f
 Algoritmo:
iniciar fluxo f como 0
Enquanto existir caminho de aumento p faça
ampliar fluxo f ao longo de p
Retorna f
GTC - Fabio Tirelo
Redes Residuais e Caminhos de Aumento

Seja G = (V,E) um fluxo em redes e f um fluxo em G
 Uma rede residual consiste em arestas que podem
admitir mais fluxo
 A capacidade residual de (u,v) é a quantidade de fluxo
adicional que podemos enviar de u para v sem
ultrapassar a sua capacidade: c f (u, v)  c(u, v)  f (u, v)

A rede residual de G induzida por f é Gf = (V,Ef ), onde
Ef = {(u,v)  V  V : cf (u,v) > 0}
 Seja G = (V,E) um fluxo em redes e f um fluxo em G
 Um caminho de aumento p é um caminho simples de s
para t em Gf
 A capacidade residual de p é a capacidade máxima
pela qual podemos aumentar o fluxo em cada aresta de
um caminho de ampliação: cf (p) = min{cf (u,v) : (u,v)  p}
GTC - Fabio Tirelo
Cortes de Fluxos em Redes

Seja G = (V,E) um fluxo em redes e f um fluxo em G
 Um corte (S,T) de f é uma partição de V em S e T = VS
tal que s  S e t  T
 O fluxo líquido pelo corte (S,T) é igual a f (S,T)
 A capacidade do corte (S,T) é igual a c(S,T)

Exemplo: fluxo = 19, capacidade = 26
11/16
s
1/4
8/13
v1
12/12
10
4/9
v2
11/14
v3
15/20
t
7/7
v4
4/4
GTC - Fabio Tirelo
Fluxo Máximo e Corte Mínimo


Seja G = (V,E) um fluxo em redes e f um fluxo em G
As três condições a seguir são equivalentes:
 f é um fluxo máximo em G
 A rede residual Gf não contém nenhum caminho
de aumento
 | f | = c(S,T) para algum corte (S,T) de T
v1
16
s
10
4
12
9
v3
v2
t
7
13
14
20
v4
4
GTC - Fabio Tirelo
Algoritmo Básico de Ford-Fulkersen
Para cada (u,v)  E faça f [u,v] = 0; f [v,u] = 0
Enquanto existir um caminho p de s para t em Gf faça
c = min { cf (u,v) : (u,v)  p }
Para cada (u,v)  p faça
f [u,v] = f [u,v] + c;
f [v,u] =  f [u,v]
v1
16
s
10
4
12
9
v3
v2
t
7
13
14
20
v4
4
GTC - Fabio Tirelo
Fluxos em Redes e Matching Bipartido

O problema de encontrar o matching máximo em
um grafo bipartido pode ser resolvido como fluxo
em redes
s
t
GTC - Fabio Tirelo
Algoritmo de Edmonds-Karp




O algoritmo de Edmonds-Karp é uma melhoria do
algoritmo básico de Ford-Fulkersen
Neste algoritmo, a busca por um caminho de
aumento é feita via busca em amplitude no grafo
residual
Redução da complexidade de O(e  | f |) para O(ne2)
Caso interessante:
1.000.000
s
1.000.000
v1
1.000.000
1
t
v2
1.000.000
GTC - Fabio Tirelo
Exercícios [CORMEN] 26.1-8 e 26.1- 9]

Enuncie o problema de fluxo máximo como um
problema de programação linear

Dados: o mapa de um local com ruas e esquinas
 Uma esquina origem e uma destino
 Determinar o número de caminhos disjuntos de
arestas da origem para o destino
GTC - Fabio Tirelo
Exercício [CORMEN] 26-1


Dados: um grafo grade GRn e m pontos de partida
Verificar se existem m caminhos disjuntos de
arestas desde os pontos de partida para pontos
diferentes na borda
GTC - Fabio Tirelo
Algoritmos de Push-Relabel






Seja G = (V,E) um fluxo em redes e f um fluxo em G
O fluxo em excesso de um vértice u é dado por
e(u)=f(V,u)
Um vértice u  V  {s,t} está transbordando se e(u) > 0
Um função de altura h deve possuir as seguintes
propriedades: h(s) = n, h(t) = 0 e h(u)  h(v) + 1, para
toda aresta residual (u,v)  Ef
Pré-fluxo: não satisfaz a conservação de fluxo
Algoritmo genérico de Push-Relabel:
INITIALIZE_PREFLOW(G,s)
Enquanto existir empurrão ou elevação aplicável
selecione uma operação aplicável e execute-a
GTC - Fabio Tirelo
Algoritmos de Push-Relabel...

Função INITIALIZE-PREFLOW(G,s):
Para todo vértice u  V faça h[u] = 0; e[u] = 0
Para toda aresta (u,v)  E faça f [u,v] = 0, f [v,u] = 0
h[s] = n
Para todo vértice u adjacente a s faça
f [s,u] = c[s,u]; f [u,s] =  c[s,u];
e[u] = c[s,u]; e[s] = e[s]  c[s,u]

Resultado da função:
 f [s,v] = c [s,v], para todo v
 f [u,s] =  c [s,u], para todo u
 f [u,s] = 0, para u,v  s
GTC - Fabio Tirelo
Algoritmos de Push-Relabel...



A operação PUSH(u,v) pode aplicada quando u
está transbordando e, para h[u] = h[v] + 1
Ação: empurrar d = min { e[u], cf [u,v] } unidades de
fluxo de u para v
Função PUSH(u,v):
d = min(e[u], cf [u,v])
f [u,v] = f [u,v] + d;
f [v,u] =  f [u,v];
e[u] = e[u] - d;
e[v] = e[v]  d;
GTC - Fabio Tirelo
Algoritmos de Push-Relabel...



A operação RELABEL(u,v) pode aplicada quando u
está transbordando e h[u]  h[v] para toda aresta
(u,v) de Ef
Ação: aumentar a altura de u
Função RELABEL(u):
h[u] = 1 + min{ h[v] : (u,v)  Ef }
1.000.000
s
1.000.000
v1
1.000.000
1
t
v2
1.000.000
GTC - Fabio Tirelo
Algoritmo de Relabel-to-Front







Seja G = (V,E) um fluxo em redes e f um pré-fluxo em G
e h uma função de altura
Uma aresta (u,v) é admissível se cf [u,v] > 0 e
h[u]=h[v] + 1
Caso contrário, dizemos que a aresta é inadmissível
A lista de vizinhos de u, N[u], é uma lista que contém os
vértices antecessores ou sucessores diretos de u
O primeiro vértice de N[u] é designado por início[N[u]]
O vértice que segue v em uma lista de vizinhos é
indicado por próximo[v]; se próximo[v] = null, então v é o
último vértice da lista
atual [u] é definido como o vértice que está sendo
atualmente considerado em N[u]
GTC - Fabio Tirelo
Algoritmo de Relabel-to-Front...

Algoritmo RELABEL-TO-FRONT(G,s,t):
INITIALIZE-PREFLOW(G,s)
L = V  {s,t}
Para cada u  V {s,t} faça
atual[u] = início[N[u]]
u = início[L]
Enquanto u  null faça
altura-antiga = h[u];
DISCHARGE(u);
Se h[u] > altura-antiga então
mover u para a frente da lista L
u = próximo[u]
GTC - Fabio Tirelo
Algoritmo de Relabel-to-Front...

Função DISCHARGE(u):
Enquanto e[u] > 0 faça
v = atual[u];
Se v == null então
RELABEL(v);
atual[u] = início[N[u]]
Senão se cf [u,v] > 0 e h[u] == h[v] + 1 então
PUSH(u,v)
Senão
atual[u] = próximo[v]
GTC - Fabio Tirelo