Teoria dos Grafos - ibilce.unesp.br · Exercício 5. Construir as redes residuais das redes exibidas nas Figuras 1 e 2. Deﬁnição 10. Um caminho de sa tna rede residual é chamado

Teoria dos Grafos

Valeriano A. de OliveiraSocorro Rangel

Silvio A. de AraujoDepartamento de Matemática Aplicada

[email protected], [email protected], [email protected]

Fluxo Máximo em Redes

Preparado a partir do texto:Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Conceitos básicos e

resultados principais

Conceitos básicos e resultados principais O Algoritmo de Ford e Fulkerson

Definições e ExemplosConceitos básicos e resultados principais O Algoritmo de Ford e Fulkerson

Teoria dos Grafos (Antunes Rangel&Araujo) – 3

Considere uma rede D(V,E) em que a cada aresta e ∈ E está associadoum número real positivo c denominado capacidade da aresta e.Suponha que a rede D possua:

■ Um vértice s ∈ V chamado origem (fonte).

■ Um vértice t ∈ V chamado destino (sumidouro).

Definição 1. Um fluxo f de s a t em D é uma função que a cadaaresta e ∈ E associa um número real não negativo f(e) satisfazendo asseguintes condições (F é o valor do fluxo na rede):

i) 0 ≤ f(e) ≤ c(e),∀e ∈ E (capacidade)

ii) ∀v ∈ V , v 6= s and v 6= t:∑

vj∈V

f(vj , v) =∑

vj∈V

f(v, vj)

(conservação do fluxo)

iii)∑

vj∈V

f(s, vj) = F e iv)∑

vj∈V

f(vj, t) = F



Exemplo 1. Na Figura 1 é exibido um fluxo em uma rede.

Figura 1: Fluxo em uma rede [2]



Note que:

- Em cada aresta o termo antes do parentesis indica sua capacidade eo termo entre parentesis o fluxo na aresta.

- a aresta (v2, v3) possui capacidade 2 e fluxo 1.

- O valor do fluxo no vértice v2 é 3 e no vértice s é 4 (valor do fluxona rede).



Exercício 1.

1. Verificar que o fluxo exibido na Figura 1 é um Fluxo Legal, ouseja, satisfaz as condições i) a iv).

2. Considerando esta mesma rede, definir uma atribuição de fluxospara as arestas que não satisfaça ii).

3. Qual o valor máximo de fluxo para esta rede?

Definição 2. Seja F um fluxo em uma rede D(V,E). Uma aresta édita saturada se f(e) = c(e). Um vértice v ∈ V é dito saturado

quando todas as arestas convergentes a v ou divergentes de v estãosaturadas.

Exemplo 2. Verifique se há vértices ou arestas saturados na redeexibida na Figura 1



Definição 3. O problema de fluxo máximo em redes consiste emdada uma rede e um vértice origem s e um vertice destino t, determinaruma atribuição de fluxo para as arestas da rede satisfazendo as condiçõesi) a iv) tal que fluxo na rede seja o maior possível.

Definição 4. Um fluxo é dito maximal quando todo caminho de s a tem D contém pelo menos uma aresta saturada.

Observação 1. Todo fluxo máximo é maximal, mas a recíproca não éverdadeira. Na Figura 2 temos um fluxo maximal que não é máximo e naFigura 3 um fluxo máximo (e maximal).



Figura 2: Fluxo maximal em uma rede [2]



Figura 3: Fluxo máximo em uma rede [2]



Exercício 2. Defina um fluxo maximal que não seja máximo na rede daFigura 1.

Definição 5. Seja S ⊂ V um subconjunto de vértices tal que s ∈ S et /∈ S, e seja S̄ = V − S. Um corte (S, S̄) relativo a s e t em D é umsubconjunto de arestas de D que possuem uma extremidade em S eoutra em S̄. Assim todo caminho da origem s ao destino t em D contémalguma aresta de (S, S̄).

Exemplo 3. 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)}



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̄}

Definição 6. A capacidade c(S, S̄) do corte (S, S̄) é igual a soma das

capacidades das arestas de (S, S̄)+, ou seja, c(S, S̄) =∑

ej∈(S,S̄)+c(ej).

Um corte mínimo é aquele que possui capacidade mínima (cmin).

Exercício 3. Verificar a capacidade dos cortes do exemplo anterior.



Definição 7. Seja F um fluxo e (S, S̄) um corte em D. Então, f(S, S̄)é o fluxo no corte (S, S̄) e é definido por:

f(S, S̄) =∑

ej∈(S,S̄)+f(ej)−

∑

ej∈(S,S̄)−f(ej).

Exercício 4. Verificar o fluxo nos cortes do exemplo anterior.

Observação 2. O valor do fluxo em uma rede é igual ao valor do fluxono corte:(S, S̄) = (s, V − s).



Observação 3. Note que o valor do fluxo na rede não pode ultrapassara capacidade de qualquer corte (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 particular: F ≤ cmin

Lema 1. [2] Seja F um fluxo em uma rede D e (S, S̄) um corte em D.Então f(S, S̄) = f(D). Ou seja: o valor do fluxo numa rede é igual aovalor do fluxo num corte qualquer de D.

Definição 8. 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 contrária.



Definição 9. Dado um fluxo F em uma rede D(V,E), define-se rede

residual D(f) como sendo uma rede tal que:

i) O conjunto de vértices de D(f) coincide com o conjunto de vérticesde D.

ii) Se (v, w) é uma aresta direta em D então (v, w) também será umaaresta direta em D(f) com capacidadec′(v, w) = c(v, w)− f(v, w).

iii) Se (v, w) é uma aresta contrária em D, então (w, v) é uma arestacontrária em D(f) com capacidade c′(w, v) = f(v, w).



Exercício 5. Construir as redes residuais das redes exibidas nas Figuras1 e 2.

Definição 10. Um caminho de s a t na rede residual é chamado decaminho aumentante (ou caminho de aumento de fluxo).

Lema 2. [2] Seja f um fluxo em uma rede D(V,E) e D(f) a rederesidual associada. Suponha que exista em D(f) um caminhoaumentante {v1, v2, ..., vk} da origem v1 = s ao destino vk = t. Então ofluxo na rede pode ser aumentado de:

f ′ = min{c′(vj , vj+1), 1 ≤ j ≤ k}.



Teorema 1. [2] O valor do fluxo máximo em uma rede D(V,E) é igualà capacidade do corte mínimo.

Corolário 1. [2] Um fluxo em uma rede D(V,E) é máximo se esomente se não existe caminho aumentante na rede residual associada.

Observação 4. Estes resultados foram usados por Ford e Fulkersonpara definir um algoritmo para resolver o problema de fluxo máximo emredes ( e.g. [2], [1]).

O Algoritmo de Ford e

Fulkerson




Algoritmo de Fluxo Máximo em redes [1] (Ford e Fulkerson,1956,1957,1962)

Dados de entrada: Um digrafo G(V,E); para cada arestaej ∈ E, um número inteiro positivo c(ej); um vértice origem s; eum vértice destino t.

1. Início

2. F = 0

3. Para todo ej ∈ E faça f(ej) = 0

4. Construa a rede residual D(f)



1. enquanto existir um caminho 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. caso contrário f(vj, vj+1) = f(vj , vj+1)− F ′

6. fim para

7. F = F + F ′

8. Construa a nova rede residual D(f)

9. fim enquanto

10. fim

ExercíciosConceitos básicos e resultados principais O Algoritmo de Ford e Fulkerson


Exercício 6. Aplicar o algoritmo na rede da Figura 1.



Exercício 7. Resolva o problema de fluxo máximo considerando a redeexibida na Figura 4. Discuta a complexidade computacional do Algoritmode Fluxo Máximo de Ford e Fulkerson usando esta rede como exemplo.

Figura 4: Pior caso - Algoritmo de Ford e Fulkerson [2]



Verificar que para determinar o corte mínimo na rede associado aofluxo máximo basta fazer:Seja F o fluxo máximo na rede e f(vi, vj) o fluxo na aresta (vi, vj).Então o corte 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 capítulo 6 de [2].



[1] Boaventura, P. O., Grafos : teoria, modelos, algoritmos, EdgardBlucher, 2003 (Pg. 157).

[2] Szwarcfiter, J.L. - Grafos e Algoritmos Computacionais, Ed.Campos, 1988 (Cap. 6).

[3] Mirzaian, A. - Algorithms Animation Worshop, York University,última visita maio 2015:(http://www.cse.yorku.ca/ aaw/;(http://www.cse.yorku.ca/ aaw/Wang/MaxFlowStart.htm)

Documents

Teoria dos Grafos - ibilce.unesp.br · Exercício 5. Construir as redes residuais das redes exibidas nas Figuras 1 e 2. Deﬁnição 10. Um caminho de sa tna rede residual é chamado