Aula12_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 12
Fluxo Máximo em Redes
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Con
eitos bási
os e
resultados prin
ipais
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Considere uma rede D(V,E) em que a 
ada aresta e ∈ E está asso
iado
um número real positivo c denominado 
apa
idade da aresta e.
Suponha que a rede D possua:
■ Um vérti
e s ∈ V 
hamado origem (fonte).
■ Um vérti
e t ∈ V 
hamado destino (sumidouro).
De�nição Um �uxo f de s a t em D é uma função que a 
ada aresta
e ∈ E asso
ia um número real não negativo f(e) satisfazendo as
seguintes 
ondições:
i) 0 ≤ f(e) ≤ c(e),∀e ∈ E (
apa
idade)
ii) ∀v ∈ V tal que v 6= s and v 6= t:
∑
vj∈V
f(vj , v) =
∑
vj∈V
f(v, vj)
(
onservação do �uxo)
iii)
∑
vj∈V
f(s, vj) = F , onde F é o valor do �uxo na rede.
iv)
∑
vj∈V
f(vj , t) = F
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Exemplo Na Figura 1 é exibido um �uxo em uma rede.
Figura 1: Fluxo em uma rede [2℄
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Note que:
- Em 
ada aresta o termo antes do parentesis indi
a sua 
apa
idade e
o termo entre parentesis o �uxo na aresta.
- a aresta (v2, v3) possui 
apa
idade 2 e �uxo 1.
- O valor do �uxo no vérti
e v2 é 3 e no vérti
e s é 4 (valor do �uxo
na rede).
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Exer
í
io
1) Veri�
ar que o �uxo exibido na Figura 1 é um Fluxo Legal, ou seja,
satisfaz as 
ondições i) a iv).
2) Considerando esta mesma rede, de�nir uma atribuição de �uxos para
as arestas que não satisfaça ii).
3) Qual o valor máximo de �uxo para esta rede?
De�nição Seja F um �uxo em uma rede D(V,E). Uma aresta é dita
saturada se f(e) = c(e). Um vérti
e v ∈ V é dito saturado quando
todas as arestas 
onvergentes a v ou divergentes de v estão saturadas.
Exemplo Veri�que se há vérti
es ou arestas saturados na rede exibida
na Figura 1
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
De�nição O problema de �uxo máximo em redes 
onsiste em
dada uma rede e um vérti
e origem s e um verti
e destino t, determinar
uma atribuição de �uxo para as arestas da rede satisfazendo as 
ondições
i) a iv) tal que �uxo na rede seja o maior possível.
De�nição Um �uxo é dito maximal quando todo 
aminho de s a t em
D 
ontém pelo menos uma aresta saturada.
Obs1: Todo �uxo máximo é maximal, mas a re
ípro
a não é verdadeira.
Na Figura 2 temos um �uxo maximal que não é máximo e na Figura 3
um �uxo máximo (e maximal).
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Figura 2: Fluxo maximal em uma rede [2℄
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Figura 3: Fluxo maximo em uma rede [2℄
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Exer
í
io De�na um �uxo maximal que não seja máximo na rede da
Figura 1.
De�nição Seja S ⊂ V um sub
onjunto de vérti
es tal que s ∈ S e
t /∈ S, e seja S¯ = V − S. Um 
orte (S, S¯) relativo a s e t em D é um
sub
onjunto de arestas de D que possuem uma extremidade em S e
outra em S¯. Assim todo 
aminho da origem s ao destino t em D 
ontém
alguma aresta de (S, S¯).
Exemplo Considere a rede da Figura 1:
1) Sejam S = {s} e S¯ = {v1, v2, v3, v4, t}. Então:
(S, S¯) = {(s, v1), (s, v2), (s, v3)}
2) Sejam S = {s, v1} e S¯ = {v2, v3, v4, t}. Então:
(S, S¯) = {(s, v2), (s, v3), (v1, v3), (v4, v1)}
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Notação:
- (S, S¯)+ = {(v, w) ∈ E tal que v ∈ S e w ∈ S¯
- (S, S¯)− = {(v, w) ∈ E tal que w ∈ S e v ∈ S¯
De�nição A 
apa
idade c(S, S¯) do 
orte (S, S¯) é igual a soma das
apa
idades das arestas de (S, S¯)+, ou seja, c(S, S¯) =
∑
ej∈(S,S¯)+
c(ej).
Um 
orte mínimo é aquele que possui 
apa
idade mínima (cmin).
Exer
í
io Veri�
ar a 
apa
idade dos 
ortes do exemplo anterior.
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
De�nição Seja F um �uxo e (S, S¯) um 
orte em D. Então, f(S, S¯) é o
�uxo no 
orte (S, S¯) e é de�nido por:
f(S, S¯) =
∑
ej∈(S,S¯)+
f(ej)−
∑
ej∈(S,S¯)−
f(ej).
Exer
í
io Veri�
ar o �uxo nos 
ortes do exemplo anterior.
Obs 2: O valor do �uxo em uma rede é igual ao valor do �uxo no 
orte:
(S, S¯) = (s, V − s).
Obs 3: Note que o valor do �uxo na rede não pode ultrapassar a
apa
idade de qualquer 
orte (S, S¯). Assim, temos que:
F = f(S, S¯) =
∑
ej∈(S,S¯)+
f(ej)−
∑
ej∈(S,S¯)−
f(ej) ≤ c(S, S¯),∀(S, S¯).
Em parti
ular: F ≤ cmin
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Lema 1 [2℄ Seja F um �uxo em uma rede D e (S, S¯) um 
orte em D.
Então f(S, S¯) = f(D). Ou seja: o valor do �uxo numa rede é igual ao
valor do �uxo num 
orte qualquer de D.
De�nição Uma aresta e tal que c(e)− f(e) > 0, denomina-se aresta
direta. Uma aresta e, tal que f(e) > 0, denomina-se aresta 
ontrária.
De�nição Dado um �uxo F em uma rede D(V,E), de�ne-se rede
residual D(f) 
omo sendo uma rede tal que:
i) O 
onjunto de vérti
es de D(f) 
oin
ide 
om o 
onjunto de vérti
es
de D.
ii) Se (v, w) é uma aresta direta em D então (v, w) também será uma
aresta direta em D(f) 
om 
apa
idade c′(v, w) = c(v, w)− f(v, w).
iii) Se (v, w) é uma aresta 
ontrária em D, então (w, v) é uma aresta
ontrária em D(f) 
om 
apa
idade c′(v, w) = f(v, w).
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Exer
í
io Construir as redes residuais das redes exibidas nas Figuras 1 e
2.
De�nição Um 
aminho de s a t na rede residual é 
hamado de
aminho aumentante (ou 
aminho de aumento de �uxo).
Lema 2 [2℄ Seja F um �uxo em uma rede D(V,E) e D(f) a rede
residual asso
iada. Suponha que exista em D(f) um 
aminho
aumentante {v1, v2, ..., vk} da origem v1 = s ao destino vk = t. Então o
�uxo na rede pode ser aumentado de:
F ′ = min{c′(vj , vj+1), 1 ≤ j ≤ k}.
Teorema [2℄ O valor do �uxo máximo em uma rede D(V,E) é igual à
apa
idade do 
orte mínimo.
De�nições e Exemplos
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Corolário [2℄ Um �uxo em uma rede D(V,E) é máximo se e somente se
não existe 
aminho aumentante na rede residual asso
iada.
Estes resultados foram usados por Ford e Fulkersonpara de�nir um
algoritmo para resolver o problema de �uxo máximo em redes (e.g. [2℄,
[1℄).
O Algoritmo de Ford e
Fulkerson
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Algoritmo de Fluxo Máximo em redes [1℄ (Ford e Fulkerson,
1956,1957,1962)
Dados de entrada: Um digrafo G(V,E); para 
ada aresta ej ∈ E,
um número inteiro positivo c(ej); um vérti
e origem s; e um vérti
e
destino t.
1. Iní
io
2. F = 0
3. Para todo ej ∈ E faça f(ej) = 0
4. Construa a rede residual D(f)
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
1. enquanto existir um 
aminho v1, v2, ..., vk de v1 = s a vk = t em
D(f) faça:
2. F ′ = min{c′(vj, vj + 1), 1 ≤ j ≤ k}
3. para j = 1, ....k faça:
4. se (vj, vj+1) é aresta direta então f(vj , vj+1) = f(vj, vj+1) + F
′
5. 
aso 
ontrário f(vj , vj+1) = f(vj , vj+1)− F
′
6. �m para
7. F = F + F ′
8. Construa a nova rede residual D(f)
9. �m enquanto
10. �m
Exer
í
ios
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Exer
í
io Apli
ar o algoritmo na rede da Figura 1.
Exer
í
ios
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Exer
í
io Resolva o problema de �uxo máximo 
onsiderando a rede
exibida na Figura 4. Dis
uta a 
omplexidade 
omputa
ional do Algoritmo
de Fluxo Máximo de Ford e Fulkerson usando esta rede 
omo exemplo.
Figura 4: Pior 
aso - Algoritmo de Ford e Fulkerson [2℄
Exer
í
ios
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Veri�
ar que para determinar o 
orte mínimo na rede asso
iado ao
�uxo máximo basta fazer:
Seja F o �uxo máximo na rede e f(vi, vj) o �uxo na aresta (vi, vj).
Então o 
orte mínimo é dado por:
i) s ∈ S
ii) Se vi ∈ S e f(vi, vj) < c(vi, vj) então vj ∈ S.
iii) Se vi ∈ S e f(vi, vj) > 0 então vj ∈ S.
Maiores detalhes ver na pagina 157 de [1℄ e o 
apítulo 6 de [2℄.
Con
eitos bási
os e resultados prin
ipais O Algoritmo de Ford e Fulkerson
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
[1℄ Boaventura, P. O., Grafos : teoria, modelos, algoritmos, Edgard
Blu
her, 2003 (Pg. 157).
[2℄ Szwar
�ter, J.L. - Grafos e Algoritmos Computa
ionais, Ed.
Campos, 1988 (Cap. 6).
[3℄ Mirzaian, A. - Algorithms Animation Worshop, York University,
última visita dezembro 2014 (http://www.
se.yorku.
a/ aaw/;
http://www.
se.yorku.
a/ aaw/Wang/MaxFlowStart.htm)
	Conceitos básicos e resultados principais
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	Definições e Exemplos
	O Algoritmo de Ford e Fulkerson
	 
	 
	Exercícios
	Exercícios