Índice i
Índice
Índice
Capítulo 5 – Grafos e redes
1. Conceitos fundamentais de grafos......................................................... 1
2. Conceitos fundamentais de redes ......................................................... 2
3. O problema do Caminho Mais Curto ....................................................... 3
3.1. Conceitos gerais .......................................................................... 3
3.2. Algoritmo de Dijkstra .................................................................... 4
3.3. Algoritmo de Floyd ...................................................................... 10
4. O problema da Árvore Abrangente Mínima ............................................. 13
4.1. Conceitos gerais ......................................................................... 13
4.2. Algoritmo de Prim (1ª versão) ......................................................... 13
4.3. Algoritmo de Prim (2ª versão) ......................................................... 16
5. O problema do Fluxo Máximo ............................................................. 20
5.1. Conceitos gerais ......................................................................... 20
5.2. Algoritmo de Ford−Fulkerson .......................................................... 22
Conceitos fundamentais de grafos 1
Cap. 5 - Grafos e redes
Capítulo 5 – Grafos e redes
1. Conceitos fundamentais de grafos
Em muitos problemas que nos surgem, a forma mais simples de o descrever, é
representá-lo em forma de grafo, uma vez que um grafo oferece uma representação visual
que trará vantagens na construção de um modelo matemático com vista à resolução do
problema.
Um grafo é uma estrutura constituída por dois conjuntos finitos: de vértices (nós ou
nodos) e de arestas (arcos ou ramos). Um grafo pode ser representado por G = (N, A), em
que N = {1, …, n} e A = {1, …, m} são os conjuntos de vértices e arestas, respetivamente,
em que A ⊆ N×N.
Cada aresta é representada por um par (i, j), com i ≠ j e i, j ∈ N, em que i é o vértice
origem e j o vértice destino. Uma aresta (i, j) diz-se não dirigida (não orientada) se o arco
(j, i) ∈ A, e diz-se dirigida (orientada) se o arco (j, i) ∉ A.
Existem 3 tipos de grafos:
- orientado (dirigido) todas as arestas são dirigidas,
- não orientado (não dirigido) todas as arestas são não dirigidas e,
- misto algumas arestas são dirigidas e outras são não dirigidas.
Um grafo diz-se completo, se entre quaisquer dois vértices existir uma aresta dirigida
(grafos dirigidos) ou não dirigida (grafos não dirigidos).
A densidade de um grafo é a razão entre a quantidade de arestas do grafo e a
quantidade de arestas do grafo completo com igual quantidade de vértices.
Dois vértices são adjacentes (vizinhos), se estiverem ligados por uma aresta. Duas
arestas são adjacentes se forem ambas incidentes relativamente ao mesmo vértice. Um
vértice é de ordem k, se tiver k arestas a ele adjacente.
2 Conceitos fundamentais de redes
Cap. 5 - Grafos e redes
Considere-se dois vértices, S e T, do grafo G. Um caminho de S para T, é uma
sucessão de vértices e arestas, p = [ S = n1, (n1, n2), n2, …, (nk-1, nk), nk = T ]. No entanto,
aquele caminho também pode ser representado apenas pela sucessão de vértices (p = [S =
n1, n2, …, nk-1, nk = T]) ou de arestas (p = [(S, n2), ..., (nk-1, T)]). O caminho p diz-se
simples, se cada vértice e aresta pertencem à sucessão uma única vez.
Um ciclo é um caminho em que S = T. Num ciclo simples, todos os vértices são
distintos. Um circuito (ciclo dirigido) é um ciclo formado por arestas dirigidas.
Um grafo dirigido sem ciclos dirigidos, diz-se acíclico. Um grafo diz-se ligado
(conexo), se existir um caminho entre quaisquer dois vértices.
Uma árvore é um grafo orientado com um e um só caminho simples entre quaisquer
dois vértices. Um subgrafo que seja uma árvore e contenha todos os vértices do grafo, é
designado por árvore abrangente (árvore total ”Spanning Tree”).
2. Conceitos fundamentais de redes
Quando se associam valores aos vértices e/ou às arestas, o grafo designa-se
geralmente por rede. Neste caso, fala-se em nós/nodos e arcos, e em vez de vértices e
arestas, respetivamente.
Uma rede pode ser representada por G = (N, A, C), em que (N, A) é um grafo e C
corresponde ao conjunto de valores associados aos arcos (“comprimentos“): ao arco (i, j)
está associado o valor cij. De uma maneira geral, os conceitos utilizados em grafos são
extensíveis às redes.
Considere-se um caminho p de S para T, na rede G. O “comprimento“ do caminho p
corresponde à soma dos “comprimentos“ dos arcos que pertencem àquele caminho:
C(p) = ∑∈ p)j,i(
ijc
Numa rede G, o conjunto de todos os caminhos de S para T identifica-se por P.
Define-se árvore mínima (árvore de caminhos mais curtos) com raiz em S, como a
árvore que contém todos os nós de N acessíveis a partir de S, em que para cada nó n2 o
único caminho de S para n2 é o caminho mais curto (de comprimento mínimo) na rede G
que liga S a n2.
O problema do Caminho Mais Curto 3
Cap. 5 - Grafos e redes
3. O problema do Caminho Mais Curto
3.1. Conceitos gerais
O problema do Caminho Mais Curto (“Shortest Path problem”) é um modelo
matemático fundamental e frequentemente usado quando se pretende estudar redes de
transportes e de comunicação. Este problema surge quando se pretende determinar o
caminho mais curto, mais barato ou mais fiável, entre um ou vários pares de nós de uma
rede. Existem três tipos de problemas de caminho mais curto:
(1) de um nó para outro,
(2) de um nó para todos os outros,
(3) entre todos os pares de nós.
No entanto, os dois primeiros são essencialmente o mesmo problema.
Sejam S e T dois nós de uma rede G = (N, A, C), em que a cada arco é associado
apenas um valor (comprimento do arco). O comprimento de um caminho de S para T, é a
soma dos comprimentos dos arcos que o compõem.
O problema do caminho mais curto entre os nós S e T tem por objetivo determinar o
caminho de valor mínimo existente em P. Isto é, pretende-se determinar o caminho p ∈ P
tal que C(p) ≤ C(q), ∀ q ∈ P. Considere-se algumas observações relacionadas com este tipo
de problemas:
− o comprimento de um caminho é maior do que o de qualquer dos seus subcaminhos;
− qualquer subcaminho de um caminho mais curto, é ele próprio um caminho mais curto
(princípio da optimalidade);
− para uma rede com n nós, qualquer caminho mais curto tem no máximo n-1 arcos (no
caminho mais curto entre dois nós, não existem nós repetidos).
Matematicamente, este problema pode ser formulado da seguinte forma:
∑ ∑∈ ∈
=Ni Nj
ijij xcZMinimizar
sujeito a
1xNj
Sj =∑∈
}T,S{Nj,0xxNk
jkNi
ij −∈∀=− ∑∑∈∈
∑∈
=Ni
iT 1x
4 O problema do Caminho Mais Curto
Cap. 5 - Grafos e redes
em que,
=caminho ao pertence ãon j) (i, se,0
caminho ao ertencep j) (i, se,1x ij
Existem vários algoritmos eficientes para resolver problemas de caminho mais curto,
sendo os mais conhecidos os algoritmos de Dijkstra (1 e 2) e de Floyd (3).
3.2. Algoritmo de Dijkstra
Este algoritmo, que foi apresentado por Dijkstra e que só pode ser aplicada a redes
cujos arcos têm associados comprimentos não negativos, baseia-se num processo de
rotulação dos nós da rede e classificação dos respetivos rótulos. A cada nó i é atribuído um
rótulo [ξi, πi], o qual pode ser permanente ou temporário. Isto quer dizer o seguinte:
[ξi, πi] permanente, representa o caminho mais curto de S para i
ξi ← nó que antecede i no caminho mais curto de S para i
πi ← valor do caminho mais curto de S para i
[ξi, πi] temporário, representa um caminho mais curto de S para i
ξi ← nó que antecede i no melhor caminho, até ao momento, de S para i
πi ← valor do melhor caminho, até ao momento, de S para i
O rótulo temporário de um nó representa um limite superior da distância mais curta
de S a esse nó, uma vez que o caminho que lhe está associado pode ser ou não o mais
curto.
O algoritmo consiste em rotular os nós da rede, começando pelo S, de uma forma
ordenada, segundo as distâncias de cada nó a S: escolher o nó com rótulo temporário com
menor valor de π, que se torna permanente, para depois serem varridos todos os seus
adjacentes, de forma a atualizar os rótulos destes (temporários). O algoritmo termina
quando não existirem nós com rótulos temporários. Inicialmente apenas o nó S é
permanente, sendo os restantes temporários.
O problema do Caminho Mais Curto 5
Cap. 5 - Grafos e redes
Algoritmo:
Passo 1.
[ξS, πS] = [S, 0] (caminho mais curto para S custa 0 e não tem nós intermédios)
[ξi, πi] = [S, CSi], ∀ i ∈ N − { S } e (S, i) ∈ A
[ξi, πi] = [−, ∞], ∀ i ∈ N − { S } e (S, i) ∉ A
Temporários = N − { S } (Temporários = conjunto de nós com rótulos temporários)
Permanentes = { S } (Permanentes = conjunto de nós com rótulos permanentes)
Passo 2.
Se Temporários = ∅ (todos os nós têm rótulos permanentes)
Então STOP
k = nó de Temporários tal que πk é mínimo (k : πk = min { πx , x ∈ Temporários })
Temporários = Temporários − { k }
Permanentes = Permanentes ∪ { k } (k passou a permanente)
Passo 3.
Para todo o j ∈ N tal que (k, j) ∈ A e j ∈ Temporários Fazer
Se πk + Ckj < πj
Então
πj = πk + Ckj
ξj = k
Regressar ao Passo 2.
Este algoritmo determina o caminho mais curto entre um dado nó S e todos os outros
nós da rede. Portanto, no fim do algoritmo, para se verificar se existe caminho entre S e
um qualquer nó k, bastando analisar o valor de πk; se πk = ∞ então não existe caminho. Se
existir caminho mais curto de S para k, este pode ser determinado percorrendo (em sentido
inverso) a 1ª parte dos rótulos dos nós (ξ) de k até S, da seguinte forma:
Caminho = { k }
i = k
Enquanto i ≠ S Fazer
i = ξi
Caminho ← Caminho ∪ { i }
6 O problema do Caminho Mais Curto
Cap. 5 - Grafos e redes
Exemplo: Determinar o caminho mais curto entre o nó S = 1 e todos os outros nós da
seguinte rede:
Passo 1.
Colocar rótulo permanente no nó 1 e rótulos temporários nos restantes nós.
Permanentes = { 1 }
Temporários = { 2, 3, 4, 5, 6, 7, 8 }
Passo 2.
k = 4, pois π4 = min { π2, π3, π4, π5, π6, π7, π8 } = min { 4, 5, 2, 12, ∞, ∞, ∞ }
Permanentes = Permanentes ∪ { 4 } = { 1, 4 }
Temporários = Temporários − { 4 } = { 2, 3, 5, 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 4, com rótulos temporários e atualizar os seus rótulos:
π3 = min { π3, π4 + C43 } = min { 5, 2 + 1 } = 3 ⇒ [ξ3, π3] = [4, 3]
π6 = min { π6, π4 + C46 } = min { ∞, 2 + 11 } = 13 ⇒ [ξ6, π6] = [4, 13]
O problema do Caminho Mais Curto 7
Cap. 5 - Grafos e redes
Passo 2.
k = 3, pois π3 = min { π2, π3, π5, π6, π7, π8 } = min { 4, 3, 12, 13, ∞, ∞ }
Permanentes = Permanentes ∪ { 3 } = { 1, 3, 4 }
Temporários = Temporários − { 3 } = { 2, 5, 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 3, com rótulos temporários e atualizar os seus rótulos:
π2 = min { π2, π3 + C32 } = min { 4, 3 + 3 } = 4 ⇒ [ξ3, π3] = [1, 4] (sem alteração)
π8 = min { π8, π3 + C38 } = min { ∞, 3 + 13 } = 16 ⇒ [ξ8, π8] = [3, 16]
Passo 2.
k = 2, pois π2 = min { π2, π5, π6, π7, π8 } = min { 4, 12, 13, ∞, 16 }
Permanentes = Permanentes ∪ { 2 } = { 1, 2, 3, 4 }
Temporários = Temporários − { 2 } = { 5, 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 2, com rótulos temporários e atualizar os seus rótulos:
π5 = min { π5, π2 + C25 } = min { 12, 4 + 1 } = 5 ⇒ [ξ5, π5] = [2, 5]
8 O problema do Caminho Mais Curto
Cap. 5 - Grafos e redes
Passo 2.
k = 5, pois π5 = min { π5, π6, π8 } = min { 5, 13, 16 }
Permanentes = Permanentes ∪ { 5 } = { 1, 2, 3, 4, 5 }
Temporários = Temporários − { 5 } = { 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 5, com rótulos temporários e atualizar os seus rótulos:
π7 = min { π7, π5 + C57 } = min { ∞, 5 + 6 } = 11 ⇒ [ξ7, π7] = [5, 11]
π8 = min { π8, π5 + C58 } = min { 16, 5 + 9 } = 14 ⇒ [ξ8, π8] = [5, 14]
Passo 2.
k = 7, pois π7 = min { π6, π7, π8 } = min { 13, 11, 14 }
Permanentes = Permanentes ∪ { 7 } = { 1, 2, 3, 4, 5, 7 }
Temporários = Temporários − { 7 } = { 6, 8 }
Passo 3.
Varrer todos os nós adjacentes a 7, com rótulos temporários e atualizar os seus rótulos:
π8 = min { π8, π7 + C78 } = min { 14, 11 + 7 } = 14 ⇒ [ξ8, π8] = [5, 14] (sem alteração)
O problema do Caminho Mais Curto 9
Cap. 5 - Grafos e redes
Passo 2.
k = 6, pois π6 = min { π6, π8 } = min { 13, 14 }
Permanentes = Permanentes ∪ { 6 } = { 1, 2, 3, 4, 5, 6, 7 }
Temporários = Temporários − { 6 } = { 8 }
Passo 3.
Varrer todos os nós adjacentes a 6, com rótulos temporários e atualizar os seus rótulos:
π8 = min { π8, π6 + C68 } = min { 14, 13 + 8 } = 14 ⇒ [ξ8, π8] = [5, 14] (sem alteração)
Passo 2.
k = 8, pois π8 = min { π8 } = min { 14 }
Permanentes = Permanentes ∪ { 8 } = { 1, 2, 3, 4, 5, 6, 7, 8 }
Temporários = Temporários − { 8 } = ∅
Passo 3.
Não existem nós adjacentes a 8, com rótulos temporários.
Passo 2.
Temporários = ∅ ⇒ Fim do algoritmo.
Resultados após o término do algoritmo:
� caminho mais curto entre os nós 1 e 8 calcula-se da seguinte forma:
p = { 8 }
i = 8
Como i ≠ 1 então { i = ξi = ξ8 = 5; p = p ∪ { i } = { 5, 8 }
Como i ≠ 1 então { i = ξi = ξ5 = 2; p = p ∪ { i } = { 2, 5, 8 }
Como i ≠ 1 então { i = ξi = ξ2 = 1; p = p ∪ { i } = { 1, 2, 5, 8 }
Como i = 1 então termina o processo.
Logo, o caminho mais curto entre 1 e 8 é p = { 1, 2, 5, 8 } e o comprimento é C(p) =
14 (= π8).
10 O problema do Caminho Mais Curto
Cap. 5 - Grafos e redes
� a árvore de caminho mais curto do nó 1 para todos os outros é a seguinte:
e tem um comprimento total de 34 (Σ cij na árvore de caminhos mais curtos).
3.3. Algoritmo de Floyd
Ao pretender-se determinar o caminho mais curto entre todos os pares de nós, pode-
se aplicar o algoritmo de Dijkstra n vezes, utilizando cada nó, sucessivamente, como
origem. No entanto, existem outros algoritmos para resolver este problema, como é o caso
do algoritmo de Floyd, desde que não haja circuitos negativos os arcos podem ter
comprimentos negativos.
Considere-se uma rede G = (N, A, D). Um arco (i, j) designa-se por arco básico, se
constituir o caminho mais curto entre os nós i e j. Um caminho mais curto entre quaisquer
dois nós da rede será totalmente constituído por arcos básicos (embora existam arcos
básicos não pertencentes ao caminho mais curto).
O algoritmo de Floyd utiliza a matriz D, de ordem n, das distâncias diretas mais curtas
entre nós. Os nós que não são adjacentes (não existe arco a ligá-los) têm associado uma
distância direta infinita. Como os nós são (por convenção) adjacentes com eles próprios,
têm associado um arco de comprimento 0. Os ciclos próprios são ignorados.
Entre cada par de nós não ligados por um arco básico é criado um arco, através de um
processo identificado por “tripla ligação“ :
dij ← min { dij , dik + dkj }
Fixando um k, a “tripla ligação“ é efetuada para todos os nós i, j ≠ k.
Após efetuar a “tripla ligação“ para cada k ∈ N com i, j ∈ N − { k }, a rede (na matriz
D alterada ao longo deste processo) é apenas constituída por arcos básicos. Logo, o
comprimento associado a cada arco dirigido do nó i ao nó k, é o caminho mais curto entre
aqueles dois nós.
O problema do Caminho Mais Curto 11
Cap. 5 - Grafos e redes
Para conhecer todos os nós intermédios num dado caminho, mantém-se
paralelamente uma matriz P, de ordem n, onde o elemento Pij representa o primeiro nó
intermédio entre os nós i e j.
Algoritmo:
Passo 1.
D = matriz das distâncias diretas
Pij = j, ∀ i, j ∈ N
k ← 0
Passo 2.
Se k ≥ n Então STOP
k ← k + 1
Passo 3.
Se Dij > Dik + Dkj (i, j ≠ k não se considera a linha e a coluna k)
Então
Dij ← Dik + Dkj
Pij ← Pik
No final, os elementos da matriz D são as distâncias mais curtas entre qualquer par de nós.
Exemplo: Determinar o caminho mais curto entre todos os pares de nós da seguinte rede:
Passo 1.
∞
∞=
02
03
580
D
=
321
321
321
P
k = 0
Passo 2.
0 ≥ 3 (n = 3) Falso
k = k + 1 = 1
12 O problema do Caminho Mais Curto
Cap. 5 - Grafos e redes
Passo 3.
D22 < D21 + D12 (0 < 3 + 8 = 11)
D23 > D21 + D13 (∞ > 3 + 5 = 8) ⇒ D23 = D21 + D13 = 8; P23 = P21 = 1
D32 < D31 + D12 (2 < ∞ + 8)
D33 < D31 + D13 (0 < ∞ + 5)
∞
=
02
803
580
D
=
321
121
321
P
Passo 2.
1 ≥ 3 Falso
k = k + 1 = 2
Passo 3.
D11 < D12 + D21 (0 < 8 + 3 = 11)
D13 < D12 + D23 (5 < 8 + 8 = 16)
D31 > D32 + D21 (∞ > 2 + 3 = 5) ⇒ D31 = D32 + D21 = 5; P31 = P32 = 2
D33 < D32 + D23 (0 < 2 + 8)
=
025
803
580
D
=
322
121
321
P
Passo 2.
2 ≥ 3 Falso
k = k + 1 = 3
Passo 3.
D11 < D13 + D31 (0 < 5 + 5 = 10)
D12 > D13 + D32 (8 > 5 + 2= 7) ⇒ D12 = D13 + D32 = 7; P12 = P13 = 3
D21 < D23 + D31 (3 < 8 + 3 = 11)
D22 < D23 + D32 (0 < 8 + 2)
=
025
803
570
D
=
322
121
331
P
O problema da Árvore Abrangente Mínima 13
Cap. 5 - Grafos e redes
Passo 2.
3 ≥ 3 Verdadeiro
STOP (termina o algoritmo)
Resultados após o final do algoritmo:
− o comprimento do caminho mais curto entre os nós 1 e 2 é 7 (D12 = 7);
− o caminho mais curto entre os nós 1 e 2 é { 1, 3 (P12 = 3), 2 (P32 = 2) }.
4. O problema da Árvore Abrangente Mínima
4.1. Conceitos gerais
A Árvore Abrangente Mínima (“Minimum Spanning Tree”), é a árvore abrangente
com o menor comprimento entre todas as árvores abrangentes. O comprimento de uma
árvore abrangente é o somatório dos comprimentos associados aos respetivos arcos.
Note-se que, em geral, a árvore abrangente mínima é diferente da árvore de caminho
mais curto entre um nó origem e todos os outros nós da rede (calculada pelo algoritmo de
Dijkstra). O algoritmo mais comum usado para resolver este problema, é o de Prim.
4.2. Algoritmo de Prim (1ª versão)
Os passos principais deste algoritmo são os seguintes:
Passo 1.
Toma-se arbitrariamente um nó S e atribui-se-lhe um rótulo permanente nulo: πS = 0.
Aos restantes nós da rede atribuem-se rótulos temporários:
πj = CSj se (S, j) ∈ A
πj = ∞ se (S, j) ∉ A
Permanentes = { S }
Temporários = N − { S }
Passo 2.
k = nó com rótulo temporário que possua menor valor (que é vizinho de um nó i);
Permanentes = Permanentes ∪ { k }
Temporários = Temporários − { k }
O arco com o mínimo valor Cik = πk passa a fazer parte da árvore abrangente mínima
Se Temporários = ∅ Então STOP (foi determinada a árvore abrangente mínima)
14 O problema da Árvore Abrangente Mínima
Cap. 5 - Grafos e redes
Passo 3.
Para todo o j ∈ N tal que (k, j) ∈ A e j ∈ Temporários Fazer
πj = min { πj, Ckj }
Voltar ao Passo 2.
Exemplo: Determinar a árvore abrangente mínima da seguinte rede:
Passo 1.
Colocar rótulo permanente no nó 1 e rótulos temporários nos restantes nós:
π1 = 0
π2 = 4; π3 = 5; π4 = 2; π5 = 12
π6 = π7 = π8 = ∞
Permanentes = { 1 }
Temporários = { 2, 3, 4, 5, 6, 7, 8 }
Passo 2.
k = 4
Permanentes = Permanentes ∪ { 4 } = { 1, 4 }
Temporários = Temporários − { 4 } = { 2, 3, 5, 6, 7, 8 }
O arco (1, 4) passa a fazer parte da árvore abrangente mínima, pois C14 = π4 = 2
Passo 3.
π3 = min { 5, 1 } = 1 π6 = min { ∞, 11 } = 11
Passo 2.
k = 3
Permanentes = Permanentes ∪ { 3 } = { 1, 4, 3 }
Temporários = Temporários − { 3 } = { 2, 5, 6, 7, 8 }
O arco (4, 3) passa a fazer parte da árvore abrangente mínima, pois C43 = π3 = 1
O problema da Árvore Abrangente Mínima 15
Cap. 5 - Grafos e redes
Passo 3.
π2 = min { 4, 3 } = 3
π8 = min { ∞, 13 } = 13
Passo 2.
k = 2
Permanentes = Permanentes ∪ { 2 } = { 1, 4, 3, 2 }
Temporários = Temporários − { 3 } = { 5, 6, 7, 8 }
O arco (3, 2) passa a fazer parte da árvore abrangente mínima, pois C32 = π2 = 3
Passo 3.
π5 = min { 12, 1 } = 1
Passo 2.
k = 5
Permanentes = Permanentes ∪ { 5 } = { 1, 4, 3, 2, 5 }
Temporários = Temporários − { 5 } = { 6, 7, 8 }
O arco (2, 5) passa a fazer parte da árvore abrangente mínima, pois C25 = π5 = 1
Passo 3.
π7 = min { ∞, 6 } = 6
π8 = min { 13, 9 } = 9
Passo 2.
k = 7
Permanentes = Permanentes ∪ { 6 } = { 1, 4, 3, 2, 5, 7 }
Temporários = Temporários − { 7 } = { 6, 8 }
O arco (5, 7) passa a fazer parte da árvore abrangente mínima, pois C57 = π7 = 6
Passo 3.
π8 = min { 9, 7 } = 7
Passo 2.
k = 8
Permanentes = Permanentes ∪ { 8 } = { 1, 4, 3, 2, 5, 7, 8 }
Temporários = Temporários − { 8 } = { 6 }
O arco (7, 8) passa a fazer parte da árvore abrangente mínima, pois C78 = π8 = 7
16 O problema da Árvore Abrangente Mínima
Cap. 5 - Grafos e redes
Passo 3.
π6 = min { 11, 8 } = 8
Passo 2.
k = 6
Permanentes = Permanentes ∪ { 6 } = { 1, 4, 3, 2, 5, 7, 8, 6 }
Temporários = Temporários − { 6 } = ∅
O arco (8, 6) passa a fazer parte da árvore abrangente mínima, pois C86 = π6 = 8
Como Temporários = ∅ STOP (foi determinada a árvore abrangente mínima)
Resultados após o final do algoritmo:
− a árvore abrangente mínima (árvore que visita todos os nós) é a seguinte:
− a árvore abrangente mínima tem um comprimento total igual a 28 (2+1+3+1+6+7+8).
4.3. Algoritmo de Prim (2ª versão)
Existe uma outra versão do algoritmo de PRIM, que opera sobre a matriz das distâncias
(custos) da rede. Os passos principais são os seguintes:
Passo 1.
Riscar a 1ª coluna e marcar a 1ª linha.
Passo 2.
Selecionar o menor elemento das linhas marcadas (não considerar colunas riscadas).
Se estão todas as colunas riscadas, STOP (determinada a árvore abrangente mínima)
Passo 3.
Riscar a coluna j e marcar a linha j.
Voltar ao Passo 2.
Os arcos que constituem a árvore abrangente mínima são os correspondentes aos
selecionados, e o seu valor é o somatório daqueles Cij.
O problema da Árvore Abrangente Mínima 17
Cap. 5 - Grafos e redes
Exemplo: Determinar a árvore abrangente mínima da rede do exemplo anterior.
Passo 1. Riscar a 1ª coluna e marcar a 1ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − −
3 5 3 0 1 − − − −
4 2 − 1 0 − − − 13
5 12 1 − − 0 − 6 9
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado da linha 1 (a única selecionada): C14 = 2
Passo 3. Riscar a 4ª coluna e marcar a 4ª linha
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − −
3 5 3 0 1 − − − −
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado das linhas 1 e 4 (selecionadas): C43 = 1
Passo 3. Riscar a 3ª coluna e marcar a 3ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − −
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado das linhas 1, 3 e 4 (selecionadas): C32 = 3
18 O problema da Árvore Abrangente Mínima
Cap. 5 - Grafos e redes
Passo 3. Riscar a 2ª coluna e marcar a 2ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − − �
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado das linhas 1, 2, 3 e 4 (selecionadas): C25 = 1
Passo 3. Riscar a 5ª coluna e marcar a 5ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − − �
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9 �
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado das linhas 1, 2, 3, 4 e 5 (selecionadas): C57 = 6
Passo 3. Riscar a 7ª coluna e marcar a 7ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − − �
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9 �
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7 �
8 − − 13 − 9 8 7 0
Passo 2. Menor elemento não riscado das linhas 1, 2, 3, 4, 5 e 7 (selecionadas): C78 = 7
O problema da Árvore Abrangente Mínima 19
Cap. 5 - Grafos e redes
Passo 3. Riscar a 8ª coluna e marcar a 8ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − − �
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9 �
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7 �
8 − − 13 − 9 8 7 0 �
Passo 2. Menor elemento não riscado das linhas 1, 2, 3, 4, 5, 7 e 8 (selecionadas): C86 = 8
Passo 3. Riscar a 6ª coluna e marcar a 6ª linha:
1 2 3 4 5 6 7 8
1 0 4 5 2 12 − − − �
2 4 0 3 − 1 − − − �
3 5 3 0 1 − − − − �
4 2 − 1 0 − − − 13 �
5 12 1 − − 0 − 6 9 �
6 − − − 11 − 0 − 8
7 − − − − 6 − 0 7 �
8 − − 13 − 9 8 7 0 �
Passo 2. Como todas as colunas se encontram riscadas, então STOP foi determinada a
árvore abrangente mínima.
Resultados no final do algoritmo:
− A árvore abrangente mínima é constituída pelos seguintes arcos:
(1, 4), (2, 5), (3, 2), (4, 3), (5, 7), (7, 8) e (8, 6)
− O valor da árvore abrangente mínima é:
2 + 1 + 3 + 1 + 6 + 7 + 8 = 28
Como se pode verificar, a árvore é a mesma que foi determinada pela versão anterior.
20 O problema do Fluxo Máximo
Cap. 5 - Grafos e redes
5. O problema do Fluxo Máximo
5.1. Conceitos gerais
Considere uma rede G, em que os valores associados aos arcos desta rede, bij,
representam as respetivas capacidades, isto é, a quantidade máxima de fluxo que pode ser
enviada pelos arcos. Estes valores terão que ser positivos (bij ≥ 0). Portanto, pode-se
definir a rede da seguinte forma: G = (N, A, B), em que B = [bij].
Em problemas de fluxo máximo existem 2 nós especiais: nó origem e nó terminal.
Com a resolução do problema de fluxo máximo pretende-se determinar a quantidade
máxima de unidades de fluxo que podem ser enviados do nó origem S para o nó terminal T.
O fluxo no arco (i, j) é designado por xij. Devido às restrições de capacidade nos
arcos, tem-se o conjunto de restrições:
0 ≤ xij ≤ bij, para todo (i, j) ∈ A [1]
Além disso, em cada nó (exceto em S e T) deve haver conservação de fluxo: a quantidade
de fluxo que chega a um nó é igual à quantidade de fluxo que sai desse nó; ou seja,
∑∑ =k
jki
ij xx para todo j ≠ S, T [2]
Como existe conservação de fluxo em todos os nós, o fluxo que sai do nó S é igual ao fluxo
que chega ao nó T; isto é,
∑∑ ==j
jTi
Si xfx [3]
onde f é o valor de fluxo.
Portanto, com a resolução do problema de fluxo máximo, pretende-se determinar o
valor do fluxo nos arcos xij [1], que maximize o valor do fluxo f, sujeito às restrições de
capacidade [2] e de conservação de fluxo [3].
Matematicamente, este problema pode ser formulado da seguinte forma:
∑=j
SjxfMaximizar
sujeito a
∑∑ =k
jki
ij xx para todo j ≠ S, T [2]
∑∑ =j
jTi
Si xx [3]
0 ≤ xij ≤ bij, para todo (i, j) ∈ A [1]
O problema do Fluxo Máximo 21
Cap. 5 - Grafos e redes
Dado um caminho qualquer de S para T numa rede,
p = [ S = n1, n2, n3, . . . , nk-1, nk = T ],
a quantidade máxima de fluxo que pode ser enviada de S para T, satisfazendo [1], [2] e
[3], por aquele caminho, é a seguinte :
min { bij : (i, j) ∈ p }.
Logo, o arco com a menor capacidade fica “saturado”, não passando mais fluxo por ele.
Um corte (“cut”) é o conjunto de todos os arcos de um subconjunto de nós para o seu
complementar: o corte )X,X( é o conjunto de todos os arcos (i, j), tal que i ∈ X e j ∈ X . A
remoção de todos os arcos do corte, desliga a rede em duas ou mais partes.
A capacidade de um corte é:
XjeXicom,b)X,X(C)j,i(
ij ∈∈= ∑ .
Em geral, )X,X(C)X,X(C ≠ . Um corte separando S de T com uma capacidade mínima
designa-se por corte mínimo.
Teorema do “fluxo máximo corte mínimo” (“max flow min cut”): Para qualquer
rede com capacidades de valor inteiro associadas aos arcos, o fluxo máximo do nó origem
S, para o nó terminal T, é igual à capacidade de um corte mínimo que separa S de T.
Enquanto existir um caminho de aumento de fluxo (c.a.f.) satisfazendo uma das
condições:
− xij < bij � arco “forward” (sentido correto): pode enviar-se fluxo adicional de i para j
− xji > 0 � arco “backward” (sentido inverso): pode enviar-se fluxo adicional de i para
j, diminuindo o fluxo que existe de j para i,
é possível aumentar a quantidade de fluxo a enviar de S para T.
Assumindo que as capacidades dos arcos são valores inteiros, definido um caminho de
aumento de fluxo constituído por arcos “forward” e arcos “backward”, o fluxo a enviar de
S para T pode ser alterado de ε unidades:
ε = min { ε1, ε2 } [inteiro positivo]
com ε1 = min { bij − xij } nos arcos “forward” do c.a.f.
ε2 = min { xji } nos arcos “backward” do c.a.f.
O valor do fluxo é, então, aumentado em ε unidades nos arcos “forward” e diminuído
em ε unidades nos arcos “backward”.
22 O problema do Fluxo Máximo
Cap. 5 - Grafos e redes
Como a capacidade de um corte mínimo é um número finito e em cada caminho de
aumento de fluxo, o fluxo é aumentado de pelo menos 1 unidade, o fluxo máximo obtém-se
após um número finito de iterações.
Um fluxo é máximo, se e só se, não existir um caminho de aumento de fluxo.
5.2. Algoritmo de Ford−Fulkerson
Este algoritmo, é um modo sistemático de pesquisar todos os possíveis c.a.f. de S para
T, atribuindo rótulos aos nós para indicar a direção em que o fluxo pode ser aumentado.
Cada nó pode estar num dos 3 estados:
− rotulado e varrido ⇒ tem um rótulo e todos os seus vizinhos estão rotulados;
− rotulado e não varrido ⇒ tem um rótulo, mas nem todos os seus vizinhos estão
rotulados;
− não rotulado ⇒ não tem rótulo.
O rótulo do nó j tem 2 partes: [i+, ε(j)] (ou [i−, ε(j)]), em que,
− i+ (ou i−) : índice de um nó i, indicando que pode-se enviar fluxo de i para j (ou de j
para i)
− ε(j) : fluxo máximo adicional que se pode enviar de S para j.
Algoritmo:
Passo 1.
S ← [S+, ∞]
S fica rotulado e varrido
Passo 2. (processo de rotulação)
j (rotulado e não varrido) ← [i+, ε(j)] ou [i−, ε(j)]
Para todo o k ∈ N tal que (j, k) ∈ A e xjk < bjk Fazer
k ← [j+, ε(k)] com ε(k) = min { ε(j), bjk − xjk }
Para todo o k ∈ N tal que (k, j) ∈ A e xkj > 0 Fazer
k ← [j−, ε(k)] com ε(k) = min { ε(j), xkj }
j fica rotulado e varrido.
Todos os k ficam rotulados e não varridos.
Se (T está rotulado) ou (não é possível rotular T)
Então (foi determinado um c.a.f.) ou (não existe c.a.f. ⇒ o fluxo atual é máximo)
Senão Regressar ao Passo 2 (início)
O problema do Fluxo Máximo 23
Cap. 5 - Grafos e redes
Passo 3. (mudança de fluxo)
T ← [k+, ε(T)] ⇒ xkT = xkT + ε(T)
Enquanto k ≠ S Fazer
Se k ← [j+, ε(k)] ⇒ xjk = xjk + ε(T)
Se k ← [j−, ε(k)] ⇒ xkj = xkj − ε(T)
k ← j
Apagar os rótulos e regressar ao Passo 1.
Exemplo: Considere a rede seguinte onde os valores correspondem à capacidade e ao fluxo
nos arcos.
Pretende-se determinar o fluxo máximo a enviar do nó 1 para o nó 4, atendendo a que
o fluxo atual enviado entre aqueles 2 nós é de 2 unidades.
Passo 1.
Fluxo atual = 2
1 ← [1+, ∞]
RotuladosVarridos = ∅
RotuladosNãoVarridos = { 1 }
NãoRotulados = { 2, 3, 4 }
Passo 2.
j ← 1 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 1: 2 e 3.
2 não pode ser rotulado, pois b12 = x12
3 ← [1+, min { ε(1), b12 − x12 }] ≡ [1+, min { ∞, 1 }] ≡ [1+, 1]
RotuladosVarridos = { 1 }
RotuladosNãoVarridos = { 3 }
NãoRotulados = { 2, 4 }
24 O problema do Fluxo Máximo
Cap. 5 - Grafos e redes
Passo 2.
j ← 3 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 3: 2 e 4.
2 ← [3−, min { ε(3), x23 }] ≡ [3−, min { 1, 1 }] ≡ [3−, 1]
4 não pode ser rotulado, pois b34 = x34
RotuladosVarridos = { 1, 3 }
RotuladosNãoVarridos = { 2 }
NãoRotulados = { 4 }
Passo 2.
j ← 2 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 2: 4.
4 ← [2+, min { ε(2), b24 − x24 }] ≡ [2+, min { 1, 3 }] ≡ [2+, 1]
RotuladosVarridos = { 1, 3, 2 }
RotuladosNãoVarridos = { 4 }
NãoRotulados = ∅
Como T = 4 foi rotulado, foi determinado um caminho de aumento de fluxo.
Passo 3. (mudança de fluxo: o aumento de fluxo é de ε(4) = 1 unidade)
fluxo = fluxo + ε(4) =2 + 1 = 3
4 ← [2+, 1] ⇒ x24 = x24 + ε(4) = 0 + 1 = 1
2 ← [3−, 1] ⇒ x23 = x23 − ε(4) = 1 − 1 = 0
3 ← [1+, 1] ⇒ x13 = x13 + ε(4) = 1 + 1 = 2
Passo 1.
Fluxo actual = 3
1 ← [1+, ∞]
RotuladosVarridos = ∅
O problema do Fluxo Máximo 25
Cap. 5 - Grafos e redes
RotuladosNãoVarridos = { 1 }
NãoRotulados = { 2, 3, 4 }
Passo 2.
j ← 1 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 1: 2 e 3.
2 não pode ser rotulado, pois b12 = x12
3 não pode ser rotulado, pois b13 = x13
Como não é possível rotular mais nenhum nó, e como o nó T = 4 não foi rotulado,
então não existe caminho de aumento de fluxo; logo, o fluxo atual é máximo.
Resultados a retirar após o final do algoritmo:
Fluxo máximo = 3.
X = { 1 }
X = { 2, 3, 4 }
C(X, X ) = b12 + b13 = 3 = Fluxo máximo