Análise e Síntese de Algoritmos
Fluxos Máximos em Grafos
CLRS, Cap. 26
Contexto
• Algoritmos elementares em grafos
(CLR, Cap. 22)
• Árvores abrangentes de menor custo (CLR, Cap. 23)
• Caminhos mais curtos com fonte única (CLR, Cap. 24)
• Caminhos mais curtos entre todos os pares (CLR, Cap. 25)
• Fluxos máximos em grafos (CLR, Cap. 26)
2003/2004
Análise e Síntese de Algoritmos
2
Resumo
• Fluxos Máximos em Grafos
–
–
–
–
–
–
–
–
–
Motivação
Definições & Propriedades
Método de Ford-Fulkerson
Teorema do Fluxo Máximo Corte Mínimo
Análise do algoritmo genérico
Algoritmo de Edmonds-Karp
Análise do algoritmo de Edmonds-Karp
Emparelhamento Bipartido Máximo
Algoritmos baseados em Pré-Fluxos
• Fluxos de Custo Mínimo
2003/2004
Análise e Síntese de Algoritmos
3
Um Problema: fornecer água a Lisboa
• Pretende-se determinar qual o volume de água
máximo (por segundo), que é possível fazer chegar a
Lisboa a partir da Barragem do Castelo do Bode
– Existe uma rede de condutas de água que permitem o envio
da água do Castelo do Bode para Lisboa
– Cada conduta apresenta uma capacidade limite, de metros
cúbicos por segundo
– Encontrar um algoritmo eficiente para resolver este
problema
2003/2004
Análise e Síntese de Algoritmos
4
Fluxos Máximos em Grafos
• Dado um grafo dirigido G=(V, E):
– Com um vértice fonte s e um vértice destino t
– Em que cada arco (u,v) é caracterizado por uma capacidade
não negativa c(u,v)
• A capacidade de cada arco (u,v) indica o valor limite de
“fluxo” que é possível enviar de u para v através do arco
(u,v)
– Pretende-se calcular o valor máximo de “fluxo” que é possível
enviar do vértice fonte s para o vértice destino t, respeitando as
restrições de capacidade dos arcos
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
5
Fluxo Máximo em Grafos  Aplicações
• Envio de materiais em rede de transportes
–
–
–
–
–
2003/2004
Petróleo ou gás
Água
Electricidade
Bytes
…
Análise e Síntese de Algoritmos
6
Fluxo Máximo em Grafos  Aplicações
• Para redes de fluxo com múltiplas fontes e/ou destinos
– Definir super-fonte que liga a todas as fontes
– Definir super-destino ao qual ligam todos os destinos
– Capacidades infinitas entre super-fonte e fontes, e entre
destinos e super-destino
2003/2004
Análise e Síntese de Algoritmos
7
Fluxo Máximo em Grafos  Definições
• Uma rede de fluxo G = (V, E) é um grafo dirigido em que
cada arco (u,v) tem capacidade c(u, v)  0
– Se (u,v)  E, então c(u,v) = 0
• Dois vértices especiais: fonte s e destino t
• Todos os vértices de G num caminho de s para t
– Grafo ligado, |E|  |V| - 1
• Um fluxo G = (V, E) é uma função f : V  V  R tal que:
– f(u, v)  c(u, v) para u, v  V
– f(u, v) = - f(v, u) para u, v  V
– para u  V - { s, t }:
 f u, v   0
(restrição de capacidade)
(simetria)
(conservação de fluxo)
vV
2003/2004
Análise e Síntese de Algoritmos
8
Fluxo Máximo em Grafos  Definições
• Valor de um fluxo: f   f s, v 
vV
• Problema do Fluxo Máximo:
– Dada rede de fluxo G com fonte s e destino t, calcular o
fluxo de valor máximo de s para t
• Exemplo:
u
5/10
s
5/10
2003/2004
1/5
v
4/10
t
Valor do fluxo: 10
Fluxo máximo: 20
6/10
Análise e Síntese de Algoritmos
9
Fluxo Máximo em Grafos 
Propriedades
• Dados conjuntos de vértices X e Y: f X, Y     f x, y 
xX yY
• Rede de fluxo G = (V, E); f fluxo em G; X, Y, Z  V:
– f(X,X) = 0
– f(X,Y) = -f(Y,X)
– Se X  Y = :
• f(X  Y,Z) = f(X,Z) + f(Y,Z)
• f(Z,X  Y) = f(Z,X) + f(Z,Y)
2003/2004
(cancelamento de termos)
(expansão do somatório)
(expansão do somatório)
Análise e Síntese de Algoritmos
10
Método de Ford-Fulkerson
• Definições:
–
–
–
–
Perspectiva
Redes residuais
Caminhos de aumento
Cortes em redes de fluxo
• Teorema do Fluxo Máximo Corte Mínimo
• Método de Ford-Fulkerson
– Algoritmo
– Complexidade
• Problemas de convergência
2003/2004
Análise e Síntese de Algoritmos
11
Método Genérico
Ford-Fulkerson-Method(G,s,t)
inicializar fluxo f a 0
while existe caminho de aumento p
aumentar fluxo f utilizando p
return f
2003/2004
Análise e Síntese de Algoritmos
12
Redes Residuais
• Dado G = (V, E), um fluxo f, e u,v  V
– capacidade residual de (u,v):
• Fluxo líquido adicional que é possível enviar de u para v
– cf(u,v) = c(u,v) - f(u,v)
– rede residual de G:
• Gf = (V, Ef), onde Ef = { (u,v)  V  V : cf(u,v) > 0 }
– Cada arco (residual) de Gf permite apenas fluxo líquido
positivo
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
13
Redes Residuais (Cont.)
• G = (V, E), f um fluxo, Gf rede residual; f’ fluxo em Gf
• Fluxo de soma f + f’ definido para cada par u,v  V:
(f + f’)(u,v) = f(u,v) + f’(u,v)
• Fluxo de soma é um fluxo com valor |f + f’| = |f| + |f’|
– Propriedades de um fluxo são verificadas: restrição de
capacidade, simetria e conservação de fluxo
• Obs: f’ é definido em Gf e é um fluxo
– Cálculo do valor de fluxo:
f  f '   f  f 's, v 



2003/2004
vV
 f s, v   f ' s, v 
vV
 f s, v    f ' s, v 
vV
f  f'
vV
Análise e Síntese de Algoritmos
14
Caminhos de Aumento
• Dado G = (V, E) e um fluxo f
– caminho de aumento p:
• caminho simples de s para t na rede residual Gf
– capacidade residual de p:
• cf(p) = min { cf(u,v) : (u,v) em p }
– cf(p) permite definir fluxo fp em Gf, |fp| = cf(p) > 0
– f’ = f + fp é um fluxo em G, com valor |f’| = |f| + |fp| > |f|
• Exemplos
2003/2004
Análise e Síntese de Algoritmos
15
Recapitular
• Fluxos Máximos em Grafos
– Definições
• Capacidades (dos arcos)
• Fluxos
• Capacidades residuais
• Redes residuais
• Caminhos de aumento
– Para aumento de fluxo
– Método de Ford-Fulkerson
2003/2004
Análise e Síntese de Algoritmos
16
A Seguir
• Fluxos Máximos em Grafos
– Teorema do fluxo máximo corte mínimo
– Método de Ford-Fulkerson
• Análise do algoritmo genérico
– Algoritmo de Edmonds-Karp
2003/2004
Análise e Síntese de Algoritmos
17
Algoritmo de Ford-Fulkerson Básico
Ford-Fulkerson(G,s,t)
foreach (u,v)  E[G]
f[u,v] = 0
f[v,u] = 0
while existe caminho de aumento p na rede residual Gf
calcular cf(p)
foreach (u,v)  p
f[u,v] = f[u,v] + cf(p) // Incrementar valor do fluxo
f[v,u] = - f[u,v]
2003/2004
Análise e Síntese de Algoritmos
18
Cortes em Redes de Fluxo
• Um corte (S, T) de G = (V, E) é uma partição de V em
S e T = V - S, tal que s  S e t  T
– fluxo líquido do corte (S, T): f (S, T ) 
  f u, v 
uS vT
– capacidade do corte (S, T): c(S, T ) 
  cu, v 
uS vT
• Se G = (V, E) com fluxo f, então o fluxo líquido através
de um corte (S, T) é f(S,T) = |f|
– T = V - S; f(S,TS) = f(S,T) + f(S,S); f(S,T) = f(S,V) - f(S,S)
– f(S,T) = f(S,V) - f(S,S) = f(S,V) = f(s,V) + f(S - s,V) = f(s,V) = |f|
• Obs: para u  S - s, f(u, V) = 0
2003/2004
Análise e Síntese de Algoritmos
19
Cortes em Redes de Fluxo (Cont.)
• Qualquer valor de fluxo é limitado superiormente pela
capacidade de qualquer corte de G
– (S,T) qualquer corte, e f um fluxo:
f  f S, T  
  f u, v     cu, v   c(S, T )
uS vT
uS vT
S
2003/2004
T
Análise e Síntese de Algoritmos
20
Fluxo Máximo Corte Mínimo
• Seja G = (V, E), com fonte s e destino t, e um fluxo f.
Então as proposições seguintes são equivalentes:
1. f é um fluxo máximo em G
2. A rede residual G não contém caminhos de aumento
3. |f| = c(S,T) para um corte (S,T) de G
• 1.  2.
– Admitir que f é fluxo máximo em G mas que Gf tem caminho de
aumento
– Então é possível definir um novo fluxo f + fp com valor |f| + |fp| > |f|;
uma contradição
2003/2004
Análise e Síntese de Algoritmos
21
Fluxo Máximo Corte Mínimo (Cont.)
• 2.  3.
– Gf sem caminhos de aumento
– S = { v  V : existe caminho de s para v em Gf }; T = V - S;
sSetT
– Com u  S e v  T, temos f(u,v) = c(u,v), pelo que
• |f| = f(S,T) = c(S,T)
• 3.  1.
– Dado que |f|  c(S,T), para qualquer corte (S,T) de G
– Como |f| = c(S,T) (definido acima), então f é fluxo máximo
2003/2004
Análise e Síntese de Algoritmos
22
Análise do Algoritmo Básico
• Número de aumentos de fluxo pode ser elevado
u
u
1000000
1000000
1000000
1000000
s
t
s
t
1000000
1000000
1000000
1
v
1
v
1000000
caminho de aumento com
capacidade residual = 1
rede de fluxo
• Fluxo máximo = 2000000
– No pior caso: número de caminhos de aumento é 2000000
2003/2004
Análise e Síntese de Algoritmos
23
Análise de Algoritmo Básico (Cont.)
• Para valores racionais das capacidades
– Converter todas as capacidades para valores inteiros
– Número de caminhos de aumento limitado por valor máximo
do fluxo |f*|
– Complexidade: O(E |f*|)
• Por exemplo: DFS para encontrar caminho de aumento
• Para valores irracionais das capacidades
– Algoritmo básico pode não terminar
– Algoritmo básico pode convergir para valor incorrecto
– Exemplo
2003/2004
Análise e Síntese de Algoritmos
24
Algoritmo de Edmonds-Karp
• Escolher caminho de aumento mais curto no número
de arcos
– Utilizar BFS em Gf para identificar caminho mais curto
– Complexidade: O(V E2)
• Exemplos
2003/2004
Análise e Síntese de Algoritmos
25
Recapitular
• Fluxos Máximos em Grafos
–
–
–
–
–
2003/2004
Definições
Método de Ford-Fulkerson
Teorema do fluxo máximo corte mínimo
Análise do algoritmo genérico de Ford-Fulkerson
Algoritmo de Edmonds-Karp
Análise e Síntese de Algoritmos
26
A Seguir
• Fluxos Máximos em Grafos
– Algoritmo de Edmonds-Karp
• Análise da complexidade
– Método de Ford-Fulkerson
• Análise do algoritmo genérico com valores irracionais
– Complexidade do algoritmo
– Convergência para valor correcto
2003/2004
Análise e Síntese de Algoritmos
27
Algoritmo de Edmonds-Karp — Análise
• Definições:
– f(s,v): distância mais curta de s para v na rede residual Gf
– f’(s,v): distância mais curta de s para v na rede residual Gf’
– Sequência de acontecimentos considerada:
• f  Gf  BFS  p  f’  Gf’  BFS  p’
• Resultados:
– f(s,v) cresce monotonicamente com cada aumento de fluxo
– Número de aumentos de fluxo é O(V E)
– Tempo de execução é O(V E2)
• O(E) devido a BFS & aumento de fluxo a cada passo
2003/2004
Análise e Síntese de Algoritmos
28
Algoritmo de Edmonds-Karp — Análise
• f(s,v) cresce monotonicamente com cada aumento de
fluxo
– Prova por contradição
– Após aumento de fluxo (de f para f’) existe v  V tal que
distância do caminho mais curto diminui
• f’(s,v) < f(s,v)
– Sem perda de generalidade, admitir f’(s,v) < f’(s,u) para
qualquer vértice u tal que f’(s,u) < f(s,u)
• i.e. escolher vértice v com a menor distância entre todos
os vértices que não verificam a propriedade de f(s,v)
crescer monotonicamente
• equivalente a: f’(s,u) < f’(s,v) implica que f(s,u)  f’(s,u)
2003/2004
Análise e Síntese de Algoritmos
29
Algoritmo de Edmonds-Karp — Análise
– Seja p’ um caminho mais curto em Gf’, de s para v e com arco de
u para v
• f’(s,u) = f’(s,v) - 1 (p’ é caminho mais curto em Gf’)
• E, por hipótese, f(s,u)  f’(s,u)
– Analisar fluxo f de u para v antes de aumento de fluxo
• Se f[u,v] < c[u,v]:
– f(s,v)  f(s,u) + 1  f’(s,u) + 1 = f’(s,v)
– o que contradiz hipótese inicial !
• Caso contrário f[u,v] = c(u,v):
–
–
–
–
–
2003/2004
(u,v)  Ef
caminho p em Gf (escolhido para obter Gf’) contém arco (v,u)
f(s,u) = f(s,v) + 1
f(s,v) = f(s,u) - 1  f’(s,u) - 1 = f’(s,v) - 2 < f’(s,v)
o que também contradiz hipótese inicial !
Análise e Síntese de Algoritmos
30
Algoritmo de Edmonds-Karp — Análise
• Número de aumentos de fluxo é O(V E)
– arco (u,v) na rede residual Gf é crítico se capacidade residual de
p é igual à capacidade residual do arco
• arco crítico desaparece após aumento de fluxo
– Quantas vezes pode arco (u,v) ser arco crítico?
• Como caminhos de aumento são caminhos mais curtos,
f(s,v) = f(s,u) + 1
• (u,v) só volta à rede residual após arco (v,u) aparecer em
caminho de aumento (com fluxo f ’)
– Como,
– Dado que,
– Obtem-se,
2003/2004
f’(s,u) = f’(s,v) + 1
f(s,v)  f’(s,v) (resultado anterior)
f’(s,u) = f’(s,v) + 1  f(s,v) + 1 = f(s,u) + 2
Análise e Síntese de Algoritmos
31
Algoritmo de Edmonds-Karp — Análise
– Distância de s a u aumenta pelo menos de duas unidades
entre cada par de vezes que (u,v) é crítico
• No limite, distância de s a u é não superior a |V| - 2
• Pelo que arco (u,v) pode ser crítico O(V) vezes
• Existem O(E) pares de vértices
• Na execução do algoritmo de Edmonds-Karp o número
total de vezes que arcos podem ser críticos é O(V E)
• Como cada caminho de aumento tem um arco crítico
– Existem O(V E) caminhos de aumento
• Complexidade de Edmonds-Karp é O(V E2)
– Complexidade de BFS é O(V+E) = O(E)
– Aumento de fluxo em O(V+E) = O(E)
(dado V = O(E))
2003/2004
Análise e Síntese de Algoritmos
32
Recapitular
• Fluxos Máximos em Grafos
– Método de Ford-Fulkerson
• Análise do algoritmo genérico
• Complexidade (valores inteiros):
• Com valores irracionais pode não terminar
– Algoritmo de Edmonds-Karp
• Análise da complexidade
2003/2004
Análise e Síntese de Algoritmos
O(E |f*|)
O(V E2)
33
A Seguir
• Fluxos Máximos em Grafos
– Emparelhamento Bipartido Máximo
2003/2004
Análise e Síntese de Algoritmos
34
Emparelhamento Bipartido Máximo
• G = (V, E) não dirigido
• Emparelhamento:
– M  E, tal que para qualquer vértice v em V não mais do
que um arco em M é incidente em v
• Emparelhamento Máximo:
– Emparelhamento cardinalidade máxima (na dimensão de M)
• Grafo Bipartido:
– Grafo pode ser dividido em V = L  R, em que L e R são
disjuntos e em que todos os arcos de E estão entre L e R
• Emparelhamento Bipartido Máximo:
– Emparelhamento máximo em que G é bipartido
2003/2004
Análise e Síntese de Algoritmos
35
Emparelhamento Bipartido Máximo
• Construir G’:
– V’ = V  {s, t}
E' 
s,u : u  L
 u, v  : u  L, v  R, e u, v   E
v, t  : v  R
– Atribuir capacidade unitária a cada arco de E’
• Emparelhamento bipartido máximo em G equivale a
encontrar fluxo máximo em G’
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
36
Emparelhamento Bipartido Máximo
• Dados G e G’:
1. Se M é um emparelhamento em G, existe um fluxo f de valor
inteiro em G’, com |f| = |M|
2. Se |f| é um fluxo de valor inteiro em G’, existe um
emparelhamento M em G, com |f| = |M|
– Seja M um emparelhamento, e (u,v)  M.
• Definir f utilizando arcos de M, f(s,u) = f(u,v) = f(v,t) = 1.
• Para restantes arcos (u,v)  E’, f(u,v) = 0
– Os caminhos s  u  v  t para todo o (u,v)  M são
disjuntos em termos dos vértices, com excepção de s e t
– Como existem |M| caminhos, cada um com uma contribuição
de uma unidade de fluxo para o fluxo total f, |f| = |M|
2003/2004
Análise e Síntese de Algoritmos
37
Emparelhamento Bipartido Máximo
• Se todas as capacidades têm valor inteiro, então para
fluxo máximo f, |f| é inteiro
– Indução no número de iterações do algoritmo genérico de
Ford-Fulkerson
• Emparelhamento bipartido máximo |M| em G
corresponde a |f|, em que f é o fluxo máximo de G’
– Se |M| é emparelhamento máximo em G, e |f| não é máximo
em G’, então existe f’ que é máximo
– f’é inteiro, |f’| > |f|
– e f’ corresponde a emparelhamento |M’|, com |M’| > |M|;
contradição
– …
2003/2004
Análise e Síntese de Algoritmos
38
Emparelhamento Bipartido Máximo
• A aplicação do algoritmo genérico de Ford-Fulkerson
tem complexidade O(E |f*|)
• Emparelhamento bipartido máximo é não superior a
min(L,R) = O(V) e tem valor inteiro
– i.e., no caso do emparelhamento máximo, |f*| = O(V)
• Complexidade de identificação do emparelhamento
bipartido máximo é O(V E)
2003/2004
Análise e Síntese de Algoritmos
39
Recapitular
• Fluxos Máximos em Grafos
–
–
–
–
2003/2004
Definições e Propriedades
Método de Ford-Fulkerson
Algoritmo de Edmonds-Karp
Emparelhamento Bipartido Máximo
Análise e Síntese de Algoritmos
40
A Seguir
• Fluxos Máximos em Grafos
–
–
–
–
2003/2004
Algoritmos de Pré-Fluxo (push-relabel)
Correcção do algoritmo genérico
Análise do algoritmo genérico
Algoritmo Relabel-To-Front
• Análise do algoritmo Relabel-To-Front
Análise e Síntese de Algoritmos
41
Fluxo Máximo Utilizando Pré-Fluxos
•
•
•
•
•
Motivação & Intuição
Operações Básicas
Algoritmo Genérico
Correcção do Método
Análise do Método
2003/2004
Análise e Síntese de Algoritmos
42
Pré-Fluxos — Intuição
• Operação mais localizada do que Ford-Fulkerson
– Não identificar caminhos de aumento
• Propriedade da conservação de fluxo não é mantida
durante execução do algoritmo
• Cada vértice u contém reservatório de fluxo
– Representa excesso de fluxo e(u)
– Começar por enviar todo o fluxo possível de s para vértices
adjacentes
• Noção de altura de cada vértice, que evolui com
aplicação do algoritmo
– Envio de fluxo só de vértices mais altos para vértices mais baixos
– Fazer subir altura de vértices em caso de necessidade de envio
de fluxo
2003/2004
Análise e Síntese de Algoritmos
43
Pré-Fluxos — Definições
f:VVR
• Pré-Fluxo:
– Verifica restrições de capacidade, simetria e f(V, u)  0 para
vértices u  V - { s }
– Não verifica necessariamente conservação de fluxo
• Excesso de fluxo:
e(u) = f(V, u)
– u  V - { s, t } transborda se e(u) > 0
• Uma função h : V  N é uma função de alturas se
h(s) = |V|, h(t) = 0, e h(u)  h(v) + 1 para todo o arco
residual (u,v)  Ef
– Função de alturas permite estabelecer condições para ser
possível enviar fluxo de u para v
2003/2004
Análise e Síntese de Algoritmos
44
Pré-Fluxos — Operações Básicas
Enviar fluxo de u para v:
Push(u,v)
df(u,v) = min(e[u], cf[u,v])
f[u,v] = f[u,v] + df(u,v)
f[v,u] = - f[u,v]
e[u] = e[u] - df(u,v)
e[v] = e[v] + df(u,v)
Aplica-se quando u
transborda, cf[u,v] > 0,
e h[u] = h[v] + 1
Subir altura de u:
Relabel(u)
h[u] = 1 + min{h[v] : (u,v)  Ef}
2003/2004
Análise e Síntese de Algoritmos
Aplica-se quando u
transborda, e (u,v)  Ef
implica h[u]  h[v]
45
Pré-Fluxos — Operações Básicas
• Operação de envio de fluxo de u para v, Push(u, v):
– Saturating push: arco (u, v) fica saturado após aplicação da
operação Push (i.e. f(u,v) = c(u,v))
• Caso contrário: Nonsaturating push
– OBS: Após um Push(u, v) nonsaturating, u deixa de transbordar
2003/2004
Análise e Síntese de Algoritmos
46
Pré-Fluxos — Operações Básicas
Initialize-Prefow(G, s)
foreach v  V[G]
h[u] = 0
e[u] = 0
foreach (u,v)  E[G]
f[u,v] = 0
f[v,u] = 0
h[s] =|V[G]|
foreach u  Adj[s]
f[s,u] = c(s,u)
f[u,s] = -c(s,u)
e[u] = c(s,u)
2003/2004
Análise e Síntese de Algoritmos
V
hu  
0
se u  s
caso contrário
47
Pré-Fluxos — Algoritmo Genérico
Generic-Push-Relabel(G)
Initialize-Preflow(G, s)
while existe operação de Push ou Relabel aplicável
seleccionar e executar operação de Push ou Relabel
return f
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
48
Pré-Fluxos — Correcção do Método
• G = (V, E), rede de fluxo com fonte s e destino t, f um
pré-fluxo, e h uma função de alturas para f. Se
vértice u transborda, então u pode ser sujeito a uma
operação de Relabel ou de Push
– h é função de alturas, pelo que h(u)  h(v) + 1
– Se operação de Push não aplicável a u, então para qualquer
arco residual (u, v), h(u) < h(v) + 1, pelo que h(u)  h(v)
• Assim, operação de Relabel pode ser aplicada a u
2003/2004
Análise e Síntese de Algoritmos
49
Pré-Fluxos — Correcção do Método
• h[u] nunca decresce; se operação de Relabel é
aplicada, h[u] aumenta de pelo menos 1 unidade
– Valor de h[u] apenas alterado em Relabel
– Aplicar Relabel se, para todo o (u, v)  Ef, h[u]  h[v]
• h[u] < 1 + min { h[v] : (u,v)  Ef }
– Pelo que valor de h[u] aumenta (de pelo menos 1 unidade)
após Relabel
2003/2004
Análise e Síntese de Algoritmos
50
Pré-Fluxos — Correcção do Método
• Durante a execução do algoritmo genérico o valor de
h é mantido como função de alturas
– Inicialmente h é uma função de alturas
– Relabel(u) mantém h como função de alturas
• Arco (u, v) em Ef
– h[u]  h[v] + 1 após Relabel, pela definição de Relabel
• Arco (w, u) em Ef
– h[w]  h[u] + 1 antes de Relabel implica h[w] < h[u] + 1
após Relabel de u
– Push(u,v) mantém h como função de alturas
• (v, u) incluído em Ef
– h[v] = h[u] - 1 (novo arco não afecta função de alturas)
• (u, v) removido de Ef
– deixa de existir restrição em h devido a (u, v)
2003/2004
Análise e Síntese de Algoritmos
51
Pré-Fluxos — Correcção do Método
• Recapitular
– G = (V, E), rede de fluxo com fonte s e destino t, f um préfluxo, e h uma função de alturas para f. Se vértice u
transborda, então u pode ser sujeito a uma operação de
Relabel ou de Push
– h[u] nunca decresce; se operação de Relabel é aplicada,
h[u] aumenta de pelo menos 1 unidade
– Durante a execução do algoritmo genérico valor de h é
mantido como função de alturas
2003/2004
Análise e Síntese de Algoritmos
52
Pré-Fluxos — Correcção do Método
• Em Gf não existe caminho de s para t
– Prova por contradição
– Admitir caminho p = v0, v1, , vk de s para t em Gf, com v0=s
e vk=t
• Podemos admitir p caminho simples, k < |V|
– i = 0, 1, …, k-1
• (vi, vi+1)  Ef, e h[vi]  h[vi+1] + 1
(função de alturas)
– Pelo que, h[s]  h[t] + k
– Como h[t] = 0, então h[s]  k < |V|
– Mas h[s] = |V|; uma contradição !
2003/2004
Análise e Síntese de Algoritmos
53
Pré-Fluxos — Correcção do Método
• Se algoritmo genérico termina, o pré-fluxo calculado é o
fluxo máximo para G
– Inicialmente temos um pré-fluxo
• Devido a Initialize-Preflow
– Algoritmo mantém a existência de pré-fluxo invariante
• Push e Relabel não alteram invariante
– Se algoritmo termina, e[u] = 0 para qualquer vértice u
• Caso contrário poderia aplicar-se Push ou Relabel !
– Nesta situação, pré-fluxo é um fluxo
• Porque não existem vértices a transbordar !
– E não existe caminho de s para t na rede residual
• Porque h é função de alturas !
– Pelo teorema do fluxo máximo corte mínimo, f é o fluxo máximo !!
2003/2004
Análise e Síntese de Algoritmos
54
Pré-Fluxos — Análise do Método
• Para cada vértice u que transborda existe um
caminho simples de u para s em Gf
– OBS: Fluxo enviado tem de poder ser cancelado
• h[u]  2|V|-1 para u  V
– h[s] e h[t] são constantes
– Relabel a u apenas aplicado quando vértice u transborda
• Existe caminho simples p de u para s
– p = v0, v1, , vk, v0 = u, vk = s, k  |V|-1
• h[vi]  h[vi+1] + 1, i = 0, 1, …, k
• h[u] = h[v0]  h[vk] + k  h[s] + (|V|-1) = 2|V| - 1
2003/2004
Análise e Síntese de Algoritmos
55
Pré-Fluxos — Análise do Método
• O número de operações de Relabel é não superior a
2|V|-1 para cada vértice e a (2|V| - 1)(|V| - 2) < 2|V|2 no
total
– Relabel apenas pode ser aplicado a vértices em V - {s, t}, i.e.
|V|-2 vértices
– Relabel faz subir valor de h[u] em pelo menos 1 unidade
– Para u  V - {s, t}, valores possíveis para h[u] entre 0 e 2|V|-1
– Relabel aplicado a u não mais do que 2|V| - 1 vezes
– Número total de operações de Relabel não superior a:
• (2|V| - 1)(|V| - 2) < 2|V|2
2003/2004
Análise e Síntese de Algoritmos
56
Pré-Fluxos — Análise do Método
• O número de saturating pushes é < 2|V||E|
– Analisar saturating pushes de u para v e de v para u
• Após Push(u,v), Push(v,u) requer aumento em h[v] de pelo
menos 2 unidades
• Análise da soma de valores de h[u] com h[v], h[u]+h[v]
– Valor inicial é pelo menos 1
– Para último Push h[u]+h[v]  (2|V|-1) + (2|V|-2) = 4|V|-3
» Número de valores possíveis é não superior a 4|V| - 3
– Número de pushes é não superior a ((4|V|-3) -1)/2 + 1 = 2|V|-1
para o par de vértices u, v
– Para todos os pares de vértices obtemos (2|V| - 1)|E| < 2|V||E|
2003/2004
Análise e Síntese de Algoritmos
57
Pré-Fluxos — Análise do Método
• O número de nonsaturating pushes é 4|V|2(|V|+|E|)
– Seja X  V o conjunto de vértices que transborda
– Seja   vX hv
– Operação de Relabel(u) aumenta  em menos de 2|V|
• Limitação da máxima altura possível para um vértice
– Saturating push aumenta  em menos de 2|V|
• Apenas um novo vértice pode ficar a transbordar e
alturas não variam
– Nonsaturating push (u,v) decrementa  em pelo menos 1
• u deixa de transbordar; v pode passar a transbordar e
h[v] - h[u] = -1
– O total de aumento de  é < 2|V|(2|V|2) + 2|V|(2|V||E|) =
4|V|2(|V|+|E|)
2003/2004
Análise e Síntese de Algoritmos
58
Pré-Fluxos — Análise do Método
– Como   0, número de nonsaturating pushes é menor do
que 4|V|2(|V|+|E|)
• Número de operações elementares é O(V2E)
– Utilizar resultados anteriores
• Número de operações limitado pelo número de
nonsaturating pushes
• Complexidade do algoritmo genérico é O(V2E)
– O(V) para operação Relabel
– O(1) para operação Push
2003/2004
(calcular novo valor de h)
(actualizar valores)
Análise e Síntese de Algoritmos
59
Algoritmo Relabel-To-Front
• Complexidade: O(V3)
• Descarga de um vértice u:
– Enviar todo o fluxo em excesso para os vértices vizinhos de u
• Lista de vizinhos de u: N[u]
– v em lista N[u] se: (u,v)  E ou (v,u)  E
• i.e. vértices para os quais um arco residual (u, v) pode existir
– Primeiro vizinho: head[N[u]]
– Próximo vizinho de u (a seguir a v): next-neighbor[v]
2003/2004
Análise e Síntese de Algoritmos
60
Algoritmo Relabel-To-Front
• Operação de descarga de um vértice:
Discharge (u)
while e[u] > 0
v = current[u]
if v = NIL
Relabel(u)
current[u] = head[N[u]]
else if cf(u,v) > 0 and h[u] = h[v] + 1
Push(u,v)
else
current[u] = next-neighbor[v]
2003/2004
Análise e Síntese de Algoritmos
61
Algoritmo Relabel-To-Front
Relabel-To-Front(G, s, t)
Initialize-Preflow(G, s)
L = V - {s, t} por qualquer ordem
foreach u  V - {s, t}
current[u] = head[N[u]]
u = head[L]
while u  NIL
oldh = h[u]
Discharge(u)
if h[u] > oldh
colocar u na frente da lista L
u = next[u]
return f
2003/2004
Análise e Síntese de Algoritmos
62
Análise de Relabel-To-Front
• Complexidade do ciclo principal:
O(V3)
– Não contabilizando o tempo de Discharge
– Fase: tempo entre operações de relabel
– Número de fases = número de operações de Relabel = O(V2)
• O(V2) para qualquer algoritmo de Pré-Fluxo
– Cada fase consiste de O(V) execuções de Discharge
• Total de execuções de Discharge é O(V3)
– Complexidade (sem contabilizar Discharge) é O(V3)
2003/2004
Análise e Síntese de Algoritmos
63
Análise de Relabel-To-Front
• Complexidade acumulada das operações de Discharge:
– Operações Relabel:
• Complexidade:
O(V E) para O(V2) operações de Relabel
– Actualizações de current[u]:
• Executadas O(degree(u)) vezes após Relabel de u
• Executadas O(V degree(u)) no total para cada vértice u
– (cada vértice pode ser sujeito a O(V) operações de relabel)
– Total:
O(V E)
– Operações Push:
• Saturating pushes:
O(V E)
• Nonsaturating pushes:
– Limitado pelo número de operações Discharge, porque retorna
após nonsaturating push, i.e. O(V3)
2003/2004
Análise e Síntese de Algoritmos
64
Análise de Relabel-To-Front
• Complexidade do algoritmo:
– Complexidade (total) das operações de Discharge
O(V3)
– Complexidade do algoritmo sem operações de Discharge O(V3)
– Complexidade do algoritmo Relabel-To-Front:
2003/2004
Análise e Síntese de Algoritmos
O(V3)
65
Fluxos de Custo Mínimo
• G = (V,E), com custos cij e capacidades uij para cada
arco (i,j)  E, e valor b(i) associado com cada i  V
– Calcular fluxo xij para cada arco (i,j)
minimizar
z x  
sujeito a :

j:i, j E
 c ij x ij
i, j E
x ij 
 x ji  bi
j: j,i E
0  x ij  uij
i V
i, j  E
– OBS: Fluxos xij são não negativos
• Propriedade de simetria não considerada nesta formulação
2003/2004
Análise e Síntese de Algoritmos
66
Fluxos de Custo Mínimo
• Problema genérico de optimização em grafos. É
possível reduzir outros problemas em grafos ao
problema de fluxos de custo mínimo
– Exemplos:
• Caminhos Mais Curtos
• Fluxo Máximo
2003/2004
Análise e Síntese de Algoritmos
67
Caminhos Mais Curtos com Fonte s
minimizar
sujeito a :
cij: peso do arco i,j
xij: fluxo entre vértices i e j
Enviar uma unidade de
fluxo de s para cada um
dos restantes vértices
 c ij x ij
i, j E
 V  1 i  s
 x ij   x ji  
j:i, j E
j: j,i E
 1
i  V  s
0  x ij
i, j  E
uij = 
Cada vértice recebe
uma unidade de fluxo
Admitir todos os vértices
atingíveis a partir de s
2003/2004
Fluxo que sai
de s é |V|-1
Análise e Síntese de Algoritmos
68
Fluxos Máximos
conservação de fluxo
minimizar
sujeito a :
csi = -1
cji = 0, j  s

 x si
s,i E

j:i, j E
x ij 
 x ji  0
j: j,i E
0  x ij  uij
xij: fluxo entre i e j
2003/2004
i  V  s, t
i, j  E
simétrico do fluxo enviado
de s para V - {s, t}
Análise e Síntese de Algoritmos
69
Revisão
• Fluxos Máximos em Grafos
–
–
–
–
–
–
–
–
Definições & Propriedades
Método de Ford-Fulkerson
Teorema do Fluxo Máximo Corte Mínimo
Análise do algoritmo genérico
Algoritmo de Edmonds-Karp
Análise do algoritmo de Edmonds-Karp
Emparelhamento Bipartido Máximo
Algoritmos baseados em Pré-Fluxos
• Fluxos de Custo Mínimo
• A seguir:
– Emparelhamento de caracteres
2003/2004
Análise e Síntese de Algoritmos
(CLR, Cap. 32)
70