GRAFOS 1 (1)

Prévia do material em texto

Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
1 
 
GRAFOS 
ANÁLISE DE REDES 
Conceitos Básicos em Teoria dos Grafos 
Diversos problemas de programação linear, inclusive os problemas de transporte, 
podem ser modelados como problema de fluxo de redes. Algoritmos específicos para 
determinados tipos de problemas podem ser mais convenientes para a sua solução do que 
algoritmos mais genéricos. Antes de continuar, serão apresentadas algumas definições da teoria 
dos grafos. 
 
Definição 1 
Um grafo linear consiste em diversos nós, ou pontos, sendo que cada nó deve estar conectado 
a um ou mais nós por arcos. 
 
Um exemplo de um grafo linear é apresentado na Figura 1. 
 
Figura 1 - Exemplo de um grafo linear. 
 
Definição 2 
Um grafo direto (ou rede direta) é um grafo em que o fluxo ao longo de um arco pode ser 
efetuado apenas em um sentido. 
 
Entretanto, pode-se substituir um arco com fluxo nos dois sentidos por dois arcos em 
sentidos opostos. Desta forma, podemos utilizar redes diretas sem que o modelo esteja 
perdendo a sua generalidade. 
 
Definição 3 
Um grafo bipartido é um grafo direto onde os nós são divididos em dois subconjuntos, onde 
todos os arcos do grafo ligam um nó de um subconjunto a um nó do outro. 
 
O grafo G6 é uma K3,3, ou seja, um grafo 
bipartido completo que contém duas partições 
de 3 vértices cada. 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
2 
 
Um grafo representando um problema de transporte é um exemplo de grafo bipartido, já 
que todos os arcos ligam nós das origens a nós dos destinos. 
Definição 4 
Um caminho ou canal é um conjunto ordenado de arcos que conectam dois nós através de nós 
intermediários, cada um dos quais estando exatamente em dois arcos do canal. 
 
Um exemplo de canal no grafo da Figura 1 é o conjunto dos arcos 1, 5 e 7, que 
conectam os nós a e c através dos nós b e e. 
 
Definição 5 
Um grafo conectado é um grafo no qual existe caminho entre qualquer par de nós. 
 
O grafo da Figura 1 é um grafo conectado. 
 
Definição 6 
Um laço é um canal que conecta um nó a ele mesmo. 
 
 Os arcos 1, 5, 7, 8, 9 e 2 formam um laço conectando o nó a (ou qualquer outro nó do 
canal) a ele mesmo (figura 1). 
 
Definição 7 
Uma árvore é um grafo conectado que não contém laços. 
 
Exemplos de árvores no grafo da Figura 1 incluem os arcos 1, 3, 4, 6, 8 ou os arcos 2, 3, 
4, 5, 8. O conjunto de arcos 1, 2, 3, 4, 7, 8 contém um laço (1, 2, 3), portanto não é uma árvore; 
o conjunto de arcos 1, 3, 7, 8, apesar de não conter laços, não forma uma árvore por não ser um 
grafo conectado. Pode ser provado que uma árvore com n nós possui (n - 1) arcos e há pelo 
menos dois extremos (nós em apenas um arco) em uma árvore. 
 
Problema de Fluxo Máximo 
 O tipo de problema de fluxo máximo é utilizado quando queremos maximizar a 
quantidade de fluxo de um ponto origem para o outro ponto destino e estamos sujeitos a 
restrições de capacidade de fluxo nos arcos. Estes problemas geralmente envolvem o fluxo de 
matérias como água, óleo, gás, energia por uma rede de tubos o cabos, mas também podem 
representar o fluxo máximo de carros em uma malha rodoviária, de produtos em linhas de 
produção, e assim por diante. 
Um problema de rede usual é a determinação do fluxo máximo entre dois pontos em 
uma rede. Considere o seguinte exemplo, adaptado de ZIONTS (1974). 
Em G3 há três ocorrências de laços para 
um grafo não orientado. 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
3 
 
Exemplos: "Um produtor de gás natural tem uma rede de tubulações conforme 
apresentado na Figura 2. As capacidades de cada parte da rede estão representadas em bilhões 
de litros por dia. Um problema ocorreu no ponto t, de modo que se deseja fornecer a maior 
quantidade de gás possível da produção ao ponto t. Portanto, o problema é encontrar a máxima 
capacidade da rede entre s e t de modo que a máxima quantidade seja fornecida de s para t." 
 
 
Mais formalmente, o problema a ser considerado é a maximização do escoamento de 
um nó s (chamado de origem) a um nó t (chamado de destino), sujeito às limitações das 
capacidades dos arcos. 
 
Neste problema, podemos considerar que a quantidade de gás que chega no ponto t é 
igual à quantidade de gás que sai do ponto s. Isso pode ser representado por um arco ligando o 
ponto t ao ponto s. Desta forma, o problema pode ser representado como um problema de 
programação linear onde deseja-se maximizar o fluxo do nó t ao nó s (que é igual ao fluxo que 
sai do nó s, ou ao fluxo que chega no nó t). As restrições deste problema, além da capacidade 
de cada arco da rede, é o fato de que a quantidade de gás que chega em qualquer nó é igual à 
quantidade de gás que sai deste mesmo nó. 
 
As variáveis de decisão para este problema são: 
 : fluxo do nó t ao nó s; 
 : fluxo do nó s ao nó a; 
 : fluxo do nó s ao nó b; 
 : fluxo do nó a ao nó t; 
 : fluxo do nó b ao nó a; 
 : fluxo do nó b ao nó t. 
 
A função objetivo, a ser maximizada, é o fluxo que chega no nó t, representado neste 
problema por . 
 
Para cada nó, o fluxo de gás que chega é igual ao fluxo de gás que sai. Convencionando 
sinal negativo ao fluxo de gás que chega e positivo ao fluxo de gás que sai, temos as seguintes 
restrições: 
 nó t: - - = 0 
 nó s: - + + = 0 
 nó a: - + - = 0 
 nó b: - + + = 0 
Figura 2 - Rede de tubulação de 
gás. 
 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
4 
 
 
As restrições de capacidade são 10, 18, 15, 4 e 10. 
O problema pode ser formulado então como apresentado a seguir. 
 
 
 
Exercício 
Caso LCL GasoBras Ltda. 
A empresa distribuidora de gás LCL GasoBras Ltda. deseja determinar a quantidade 
máxima de metros cúbicos por segundo de gás que pode bombear de estação de 
Campos para o centro consumidor do Rio de Janeiro pela rede de gasodutos 
existentes. A figura 1 ilustra a estrutura da rede de distribuição e apresenta a 
capacidade de fluxo máximo nos trechos (em metros cúbicos por segundo). Pede-se: 
a) determine as variáveis de decisão; 
b) função objetivo; 
c) restrições de capacidade; 
d) restrições de fluxo. 
 
 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
5 
 
Problema do caminho de custo mínimo 
 De forma a reduzir seus custos operacionais, uma empresa de transporte de cargas 
deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor 
caminho (o de menor distância) entre quaisquer duas cidades por ela servidas, de forma a que 
sejam minimizados os custos de transporte. 
 
 
 
Um possível modelo para este problema poderia ser: 
G (V,A) 
 V = {x | x é cidade} 
 A = {(xi, xj, d) | há uma conexão por estrada entre as cidades xi e xj, sendo d a 
distância que as separa} 
O problema de encontrar o caminho de custo mínimo entre dois vértices de um grafo é o 
mais importante relacionado com a busca de caminhos em grafos em vista de sua aplicação à 
várias situações de realidade. 
Há um grande número de situações possível quando da obtenção deste caminho, a 
exemplo de: existência ou não de ciclos; determinação do caminho ou apenas do custo mínimo; 
etc. Dada esta diversidade de situações, há um número razoável de algoritmos que foram 
propostos ao longo do tempo, dentre os quais os algoritmos de Dijkstra e de Floyd. 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
6Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo 
O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de 
custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este 
algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é 
bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da 
solução caso haja a presença de arcos com valores negativos. 
Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai 
sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando 
já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. 
Caso contrário ele dito estar aberto. 
Algoritmo: Seja G(V, A) um grafo orientado e s um vértice de G: 
1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito 
às demais estimativas; 
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice 
que precede t no caminho de custo mínimo de s para t); 
3. Enquanto houver vértice aberto: 
o seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os 
vértices abertos; 
o feche o vértice k 
o Para todo vértice j ainda aberto que seja sucessor de k faça: 
 some a estimativa do vértice k com o custo do arco que une k a j; 
 caso esta soma seja melhor que a estimativa anterior para o vértice j, 
substitua-a e anote k como precedente de j. 
A seqüência de diagramas
*
 ilustra o funcionamento do Algoritmo de Dijkstra. 
 Inicialmente todos os nodos tem um custo infinito, 
exceto s (a raiz da busca) que tem valor 0: 
vértices s u v x y 
estimativas 0 
precedentes - - - - - 
 
 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
7 
 
 selecione s (vértice aberto de estimativa mínima) 
 feche s 
 recalcule as estimativas de u e x 
vértices s u v x y 
estimativas 0 10 5 
precedentes s s - s - 
 
 
 selecione x (vértice aberto de estimativa mínima) 
 feche x 
 recalcule as estimativas de u,v e y 
vértices s u v x y 
estimativas 0 8 14 5 7 
precedentes s x x s x 
 
 
 selecione y (vértice aberto de estimativa mínima) 
 feche y 
 recalcule a estimativa de v 
vértices s u v x y 
estimativas 0 8 13 5 7 
precedentes s x y s x 
 
 
 selecione u (vértice aberto de estimativa mínima) 
 feche u 
 recalcule a estimativa de v 
vértices s u v x y 
estimativas 0 8 9 5 7 
precedentes s x u s x 
 
 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
8 
 
 selecione v (vértice aberto de estimativa mínima) 
 feche v 
vértices s u v x y 
estimativas 0 8 9 5 7 
precedentes s x u s x 
 
 
Quando todos os vértices tiverem sido fechados, os valores obtidos serão os custos 
mínimos dos caminhos que partem do vértice tomado como raiz da busca até os demais vértices 
do grafo. O caminho propriamente dito é obtido a partir dos vértices chamados acima de 
precedentes. 
Para exemplificar, considere o caminho de custo mínimo que vai de s até v, cujo custo 
mínimo é 9. O vértice precendente de v na última das tabelas acima é u. Sendo assim, o 
caminho é: 
s u v 
Por sua vez, o precedente de u é x. Portanto, o caminho é: 
s x u v 
Por último, o precedente de x é o próprio vértice s. Logo, o caminho de custo mínimo é: 
s x u v 
Como apresentado o algoritmo de Dijkstra computa apenas um único caminho de custo 
mínimo entre um dado par de vértices. Para se obter todos os caminhos de custo mínimo entre 
dois vértices é necessário modificar a forma de anotação dos precedentes. A modificação no 
passo 3 indicada a seguir é suficiente para permitir o cômputo de todos os caminhos por um 
processo similar ao descrito acima. 
... 
Para todo vértice j ainda aberto que seja sucessor de k faça: 
 some a estimativa do vértice k com o custo do arco que une k a j; 
 caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote 
k como precedente único de j; 
 caso esta soma seja igual à estimativa anterior para o vértice j, adicione k ao conjunto 
dos precedentes de j; 
Supondo que o peso do arco (y,v) no grafo acima fosse 2, haveriam dois caminhos de custo 
mínimo do vértice s para v. Esta duplicidade resulta em dois precedentes para o vértice v: 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
9 
 
vértices s u v x y 
estimativas 0 8 9 5 7 
precedentes s x u, y s x 
Sendo assim, os dois caminhos são dados por: (s u v) e (s y v). 
Seguindo as precedências para u e y nestes dois casos obtemos os dois caminhos: (s x u 
v) e (s x y v). 
 
Algoritmo de Dijkstra 
O algoritmo de Dijkstra é o mais famoso dos algoritmos para cálculo de caminho de 
custo mínimo entre vértices de um grafo e, na prática, o mais empregado. 
Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste 
vértice para todos os demais vértices do grafo. O algoritmo pode ser usado sobre grafos 
orientados (dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo 
é possível). Esta restrição é perfeitamente possível no contexto de redes de transportes, onde as 
arestas representam normalmente distâncias ou tempos médios de percurso; poderão existir, no 
entanto, aplicações onde as arestas apresentam pesos negativos, nestes casos o algoritmo não 
funcionará corretamente. 
Funcionamento do algoritmo 
Assumiremos um conjunto, chama-lo-emos PERM, que contém inicialmente apenas o 
vértice fonte (raiz da busca) s. A qualquer momento PERM contém todos os vértices para os 
quais já foram determinados os menores caminhos usando apenas vértices em PERM a partir de 
s. Para cada vértice z fora de PERM matemos a menor distância dist[z] de s a z usando 
caminhos onde o único vértice que não está em PERM seja z. É necesssário também armazenar 
o vértice adjacente (precedente) a z neste caminho em path[z]. 
Como fazer com que PERM cresça, ou seja, qual vértice deve ser incluído em PERM a 
seguir? Tomamos o vértice, entre todos os que ainda não pertencem a PERM, com menor 
distância dist. Acrescentamos então este vértice, chamemo-lo de current, a PERM, e 
recalculamos as distâncias (dist) para todos os vértices adjacentes a ele que não estejam em 
PERM, pois pode haver um caminho menor a partir de s, passando por current, do que aquele 
que havia antes de current ser agregado a PERM. Se houver um caminho mais curto 
precisamos também atualizar path[z] de forma a indicar que current é o vértice adjacente a z 
pelo novo caminho mínimo. 
Vejamos o funcionamento do algoritmo sob outra representação: 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
10 
 
1) Defini-se inicialmente o nó de origem (raiz), neste caso s, e inclui-se este nó em PERM. 
Atribui-se zero a sua distância (dist[s]) porque o custo de ir de s a s é obviamente 0. Todos os 
outros nós i tem suas distâncias (dist[i]) inicializadas com um valor bastante grande 
("infinito"). 
 
 
 
2) A partir de s consulta-se os vértices adjacentes a ele, que no grafo G são u e x. Para todos os 
vértices adjacentes, que chamaremos z, calcula-se: 
 Se dist[z] > dist[s] + peso(s, z) 
 dist[z] = dist[s] + peso(s, z) 
 path[z] = s 
 Fim Se 
 
 
 
 
3) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância. 
Neste caso é o vértice x, pois dist[x] = 5. 
Profa.Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
11 
 
 
 
 
4) Então, inclui-se x em PERM e a partir de x consulta-se os vértices adjacentes a ele que não 
estão em PERM, que no grafo G são u, v e y. Para todos os vértices adjacentes, que 
chamaremos z, calcula-se: 
 Se dist[z] > dist[x] + peso(x, z) 
 dist[z] = dist[x] + peso(x, z) 
 path[z] = x 
 Fim Se 
 
 
5) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância. 
Neste caso é o vértice y, pois dist[y] = 7. 
 
 
 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
12 
 
6) Inclui-se então y em PERM e a partir de y consulta-se os vértices adjacentes a ele que não 
estão em PERM, que no grafo G é apenas o vértice v. 
 Se dist[v] > dist[y] + peso(y, v) 
 dist[v] = dist[y] + peso(y, v) 
 path[v] = y 
 Fim Se 
 
 
 
7) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância. 
Neste caso é o vértice u, pois dist[u] = 8. 
 
 
 
8) Inclui-se então u em PERM e a partir de u consulta-se os vértices adjacentes a ele que não 
estão em PERM, que no grafo G é apenas o vértice v. 
 
Se dist[v] > dist[u] + peso(u, v) 
 dist[v] = dist[u] + peso(u, v) 
 path[v] = u 
 Fim Se 
Profa. Msc Claudineia H. Recco 
Pesquisa Operacional – Grafos - UNINOVE 
13 
 
 
 
 
9) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância. 
Neste caso é o único vértice restante v e dist[v] = 9. 
 
 
10) Por fim faz-se v pertencer a PERM. Neste ponto, todos os vértices já estão em PERM e a 
busca é finalizada.