Apostila Grafos POII

Prévia do material em texto

Universidade Federal Fluminense 
 
 
 
 
 
 
 
 
 
 
 
 
Apostila de Pesquisa Operacional II 
 
 
Teoria dos Grafos 
 
 
Lidia Angulo Meza 
Renato Teixeira da Silva 
Talita Pereira dos Santos (revisão) 
 
 
 
 
 
 
 
 
 
 
 
 
Volta Redonda, 11 de março de 2008 (atualizado em 14 de março de 2011)
 
I 
 
Sumário 
 
1. Teoria dos Grafos.................................................................................................... 1�
1.1 Histórico ................................................................................................................ 1�
1.2 Conceitos Básicos .................................................................................................. 2�
1.2.1 Grafo ................................................................................................................................ 2�
1.2.2 Adjacência e Incidência ................................................................................................... 3�
1.2.3 Grau de um grafo.............................................................................................................. 3�
1.2.4 Representação de um Grafo ............................................................................................. 4�
1.2.5 Alguns Tipos de Grafos mais Utilizados.......................................................................... 6�
1.2.6 Percursos em Grafos......................................................................................................... 9�
1.3 O Problema do Caminho Mínimo ........................................................................ 9�
1.3.1 Algoritmo de Dijkstra....................................................................................................... 9�
1.3.2 Algoritmo de Floyd ........................................................................................................ 12�
1.3.3 Formulação Matemática do Problema de Caminho Mínimo ......................................... 15�
1.4 O Problema da Árvore Geradora Mínima......................................................... 17�
1.4.1 Conexidade de um grafo ................................................................................................ 17�
1.4.2 Árvore e Árvore Geradora.............................................................................................. 17�
1.4.3 Algoritmo de Prim.......................................................................................................... 18�
1.4.4 Algoritmo de Kruskal..................................................................................................... 18�
1.5 O Problema de Fluxo Máximo............................................................................ 19�
1.5.1 Modelo de Otimização Linear........................................................................................ 19�
1.5.2 Algoritmo de Ford-Fulkerson......................................................................................... 21�
1.6 Bibliografia.......................................................................................................... 26�
 
 
 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
Profª Lidia 1 
 
 
 
1. Teoria dos Grafos 
 
 
 
 
"A inteligência é o farol que nos guia, mas é a vontade que nos faz caminhar." 
Anônimo 
 
 
1.1 Histórico 
 
 Podemos dizer que o estudo sobre grafos iniciou no século XVIII com os 
estudos de Euler. Ele formulou no ano de 1736 o primeiro problema do que seria 
chamada posteriormente Teoria dos Grafos a partir de uma questão relevante para 
arquitetura, mais especificamente ao planejamento urbano. O problema das pontes de 
Königsberg (atualmente Kaliningrado) na Prússia questionava se existia um caminho 
em que se pudesse cruzar apenas uma vez cada uma das sete pontes que passam sobre o 
rio Nagel e ligam duas ilhas centrais, passando pelas quatro áreas e retornando ao ponto 
de partida. 
 
Figura 1.1: Pontes de Königsberg e a representação em grafos 
 
 Euler construiu um diagrama simplificado onde as ilhas e as margens são 
representadas por pontos e as pontes pelas linhas que unem esses pontos. Para chegar a 
conclusão da não existência de solução para esse problema, Euler analisou que para 
cada ponto da cidade deveria haver uma chegada e uma partida e que elas deveriam ser 
distintas, pois se deve cruzar uma ponte uma única vez, só havendo rota possível caso o 
número de ligações recaindo em cada um dos pontos seja constante, fato que não ocorre 
neste problema. 
 Outro problema que faz parte da história da Teoria dos Grafos é o Problema das 
Quatro Cores, que buscava determinar o número mínimo de cores necessárias para 
colorir um mapa de forma que os países com fronteiras comuns tivessem cores 
diferentes. Francis Guthrie, em 1852, conjecturou que esse número mínimo seria 4. A 
prova dessa conjectura surgiu somente em 1976 por Appel e Haken. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 2 
 Em 1856, William R. Hamilton formula um novo problema, o Problema do 
Ciclo Hamiltoniano. Ele consiste em buscar um caminho que comece e termine num 
mesmo vértice e passe exatamente uma vez por todos os outros vértices. Esse problema 
foi precursor do Problema do Caixeiro Viajante, muito abordado atualmente. 
 No século XX houve um maior interesse sobre o estudo da Teoria dos Grafos 
desencadeando no patamar em que estamos hoje. 
1.2 Conceitos Básicos 
1.2.1 Grafo 
 
 Um grafo é uma noção simples e abstrata utilizada para representar a idéia de 
relação entre "objetos". Graficamente, é representado por uma figura composta de 
vértices, representando os objetos, que estão unidos por um traço denominado aresta, 
representando a relação imaginada. Matematicamente, um grafo é representado por: 
 
 G = (V, A) (1.1) 
 
onde V é o conjunto de vértices e A é o conjunto de ligações entre vértices. 
 
Grafo Não Orientado 
 
 Um grafo é dito não orientado quando os pares de vértices não possuem uma 
ordem, ou seja, quando o par (i, j) é semanticamente igual ao par (j, i), podendo ser 
expresso como [i, j] onde i, j � V. 
 
 
 
Figura 1.2: Exemplo de Grafo não orientado 
 
 Na Figura 1.2, tem-se um exemplo de um grafo não orientado que representa 
uma rede de computadores em um escritório. A transmissão de dados se dá tanto do 
computador 1 para o 5 quanto do 5 para o 1. 
 
Grafo Orientado (ou Dígrafo) 
 
 Um grafo é dito orientado quando o sentido das ligações entre os vértices é 
considerado. Neste caso denomina-se arco o par ordenado (i, j), sendo i o vértice inicial 
e j o vértice final, onde i, j � V. Quando estes arcos possuem um valor associado, ele é 
então chamado de rede orientada. 
 A Figura 1.3 mostra um exemplo de rede orientada representando um sistema de 
transporte, sendo cada vértice uma cidade, cada arco uma estrada ligando uma cidade a 
outra e o valor associado a cada arco a distância entre cada cidade. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 3 
 
 
Figura 1.3: Exemplo de Rede Orientada 
1.2.2 Adjacência e IncidênciaSejam x e y vértices de um grafo G orientado ou não. Se x e y estão unidos por 
uma aresta a, então x e y são adjacentes. Além disso, x e y são incidentes em a e a é 
incidente em x e y. 
 Quando duas arestas compartilham um mesmo vértice, pode-se dizer também 
que elas são adjacentes. 
 Sejam v e w vértices de um grafo G orientado. Se v e w estão unidos por um arco 
e, então v e w são adjacentes. Se o arco e começa em v e termina em w então o arco e é 
incidente de v e incidente a w. 
 
Figura 1.4: Adjacência e Incidência num grafo orientado 
1.2.3 Grau de um grafo 
 
Para grafos não orientados 
 
 O grau de um vértice x de um grafo F é o número de arestas com incidência em 
x e representado por d(x). 
 
 
Figura 1.5: Grafo não orientado 
 
d(u) = 2, d(v) = 5, d(w) = 4, d(z) = 5 
 
Teorema 1.1. Em qualquer grafo, a soma de todos os graus dos vértices é igual a duas 
vezes o número de arestas. 
 
 No exemplo: d(u) + d(v) + d(w) + d(z) = 2 + 5 + 4 + 5 = 16, então o grafo tem 8 
arestas. 
 
Para grafos orientados 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 4 
 Seja G um grafo orientado, o grau exterior de um vértice x ou d+(x) é o número 
de todos os arcos incidentes de x. O grau interior de um vértice x ou d−(x) é o número de 
todos os arcos incidentes a x. 
 
 
 
 
 
Figura 1.6: Grafo orientado 
d+(v) = 3, d−(v) = 1, d+(u) = 1, d−(u) = 1, d+(w) = 2, d−(w) = 2, d+(z) = 0, d−(z) = 2 
 
Teorema 1.2. Em um grafo orientado, a soma de todos os graus exteriores e a soma de 
todos os graus interiores é igual ao número de arcos. 
 
 No exemplo: d+(v) + d+(u) + d+(w) + d+(z) = 3 + 1 + 2 + 0 = 6 = 1 + 1 + 2 + 2 = 
d−(v) + d−(u) + d−(w) + d−(z) 
1.2.4 Representação de um Grafo 
 
 A representação gráfica dos vértices e ligações pode ser de fácil visualização, 
mas não são computacionalmente viáveis. Desta forma, os grafos devem ser 
representados de forma matemática. 
 Existem várias formas de representar um grafo. Dentre as quais temos: 
 
Lista de Adjacências 
 
 Uma lista de adjacências armazena o relacionamento entre os vértices de um 
grafo em uma estrutura de listas. Esse tipo de representação é tida como econômica do 
ponto de vista computacional. 
 
Figura 1.7: Exemplo de grafo orientado 
 Vértices Vértices 
Origem Destino Destino Origem 
1 2,3,4 1 - 
2 4 2 1 
3 - 3 1,4 
4 3 4 1,2 
Tabela 1.1: Lista de Adjacências 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 5 
 A Tabela 1.1 apresenta a lista de adjacências do grafo da Figura 1.7. Por se 
tratar de um grafo orientado, é necessário duas listas de adjacências: uma de origem-
destino e outra de destino-origem. Caso se tratasse de um grafo não orientado seria 
necessário somente a lista de origem-destino. 
 
Matriz de Adjacências 
 
A matriz de adjacências mostra o relacionamento entre os vértices de um grafo. 
Ela é uma matriz quadrada de tamanho n, onde n é o número total de vértices. A matriz 
de adjacências é construída da seguinte forma: 
 
 
ij
ij
a 1 (i, j) A.
M
a 0 (i, j) A.
= ⇔ ∈��
= �
= ⇔ ∉��
 (1.2) 
 
A partir do grafo utilizado no exemplo anterior (Figura 1.7) foi construída a 
matriz de adjacências a seguir: 
 
 1 2 3 4 
1 0 1 1 1
2 0 0 0 1
M
3 0 0 0 0
4 0 0 1 0
� �
� �
� �
=
� �
� �� �
	 
 (1.3) 
 
onde as linhas representam o vértice de origem e as colunas representam o vértice de 
destino. 
Caso i = j e aij = 1, temos o chamado loop, representado pela Figura 1.8. 
 
 
Figura 1.8: Loop 
 
Para um grafo não orientado, o procedimento de construção da matriz de 
adjacências é o mesmo e podemos notar que a matriz gerada é simétrica. 
 
 
Figura 1.9: Exemplo de grafo não orientado 
 
 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 6 
 1 2 3 4 
1 0 1 1 0
2 1 0 1 1
M
3 1 1 0 0
4 0 1 0 0
� �
� �
� �
=
� �
� �� �
	 
 (1.4) 
 
Quando os grafos precisam incluir valores de distâncias, de custos ou outros, 
estes são representados de forma um pouco diferente. Tem-se uma matriz de 
adjacências valorada, que é chamada de matriz de distâncias ou custos. A construção 
dessa matriz se dá da seguinte forma: 
 
 
ij
ij ij
ij
d 0 i j
D d c (i, j) A
d (i, j) A
� = ⇔ =
�
= = ⇔ ∈�
�
= ∞ ⇔ ∉�
 (1.5) 
 
Esse tipo de representação será muito utilizado em todas as próximas seções. A 
Figura 1.10 mostra um exemplo de uma rede orientada e a seguir sua matriz de 
distâncias ou custos. 
 
 
 
Figura 1.10: Exemplo de rede orientada 
 
 1 2 3 4 
1 0 5 6 2
2 0 3
M
3 0
4 5 0
� �
� �
∞ ∞� �
=
� �∞ ∞ ∞
� �� �
∞ ∞	 
 (1.6) 
 
1.2.5 Alguns Tipos de Grafos mais Utilizados 
 
Os exemplos aqui citados foram extraídos de BOAVENTURA NETTO (2003). 
 
Grafo simétrico 
 
Um grafo G = (N,A) será simétrico se (i, j) ∈ A e somente se (j, i) ∈ A, ∀ i, j∈ 
N. Assim, a matriz de adjacência de G será uma matriz simétrica. Exemplos: 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 7 
 
Figura 1.11: Grafos simétricos 
 
Grafo anti-simétrico 
 
Se (i, j) ∈ A, um grafo G = (N,A) será anti-simétrico se e somente se (j, i) ∉ A, 
i, j ∈ N. 
Claramente, este tipo de relacionamento é utilizado para grafos orientados e não 
pode possuir laços. Este tipo de grafo pode expressar relações de ordem total ou parcial 
(paternidade, idade, hierarquia, e outros). Por exemplo, o organograma é um grafo anti-
simétrico. 
 
Figura 1.12: Grafos anti-simétricos 
 
Grafo completo 
 
Um grafo G = (N,A) será completo se existir ao menos uma ligação associada a 
cada par de vértices. No caso orientado, isso significa exatamente uma ligação e, 
portanto, o grafo possuirá todas as arestas possíveis. São conhecidas como cliques, Kn 
onde n é o número de vértices do grafo. 
 
Figura 1.13: Grafos completos 
 
Para o caso orientado, se (i, j) ∉ A então (j, i) ∈ A, isto é, a ausência de um arco 
em um sentido implicará na presença do arco no sentido oposto. 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 8 
Grafo Bipartido 
 
Aqueles nos quais o conjunto de vértices N pode ser particionado em dois 
subconjuntos de tal forma que vértices pertencentes a um mesmo subconjunto não são 
adjacentes. 
 
Figura 1.14: Grafo Bipartido 
Cliques Bipartidas 
 
São grafos bipartidos não orientados com o maior número possível de arestas. 
Denota-se por Kp,q. 
 
Figura 1.15: Cliques Bipartidas 
 
Grafo Complementar 
 
É um grafo G que possui o mesmo conjunto de vértices e as ligações não 
existentes em umgrafo G = (N,A), sendo que o universo de arcos corresponde às arestas 
de um clique. 
 
Figura 1.16: Grafos Complementares 
 
Subgrafo 
 
É um grafo que possui o subconjunto de vértices e o subconjunto de ligações de 
um grafo incidentes aos vértices retirados. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 9 
 
Figura 1.17: Exemplo de subgrafo 
 
Grafo Parcial 
 
É um grafo obtido pela supressão de ligações do grafo original. 
 
 
Figura 1.18: Grafo Parcial 
1.2.6 Percursos em Grafos 
 
Um percurso ou itinerário ou ainda cadeia é uma família de ligações sucessivas 
adjacentes. 
Um percurso euleriano em um grafo é o percurso que usa cada ligação 
exatamente uma vez. Um conhecido problema que se encaixa nesse perfil é o Problema 
do Carteiro Chinês. Nele, o carteiro deseja percorrer todas as ruas da sua rota um 
número mínimo de vezes e voltar ao correio. 
Um percurso hamiltoniano em um grafo é o percurso que visita cada vértice 
uma só vez. No Problema do Caixeiro Viajante, um exemplo que utiliza percurso 
hamiltoniano, o caixeiro deseja visitar uma variedade de cidades e depois voltar ao 
ponto de partida. Associando-se o tempo de viagem entre as cidades, o caixeiro planeja 
um itinerário de tal forma que visite todas as cidades num menor tempo possível. Este é 
talvez um dos problemas mais estudados na Teoria dos Grafos e de mais difícil solução. 
 
Nas seguintes seções estudaremos alguns dos principais problemas em grafos. 
1.3 O Problema do Caminho Mínimo 
 
O problema do caminho mínimo consiste na minimização do custo de percurso 
de um grafo entre dois vértices, custo este dado pela soma dos custos de cada aresta 
percorrida. Para a sua resolução existem vários algoritmos, mas esta disciplina abordará 
somente dois deles: o Algoritmo de Dijkstra e o Algoritmo de Floyd. 
1.3.1 Algoritmo de Dijkstra 
 
O Algoritmo de Dijkstra tem por objetivo determinar o caminho mínimo entre 
uma origem e um destino dados. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 10 
Ele será aplicado diretamente sobre o grafo e utilizará a seguinte notação sobre 
cada vértice: 
 [c, j]X (1.7) 
onde c representa o custo até o vértice, j representa o vértice precedente e X a 
classificação do vértice, que pode assumir valores T (temporário) ou P (permanente). 
Esse algoritmo parte sempre de um vértice T, aquele de menor custo acumulado 
buscando chegar ao destino. 
 
Exemplo: Determine o caminho mínimo entre 1 e 5 da Fig 1.19. 
 
Figura 1.19: Rede Orientada do Exemplo 
Solução: 
Primeiramente vamos identificar o vértice de origem como um vértice de custo 
0, sem precedente e permanente. 
A seguir vamos identificar os vértices que tem como precedente a origem. Eles 
serão classificados como temporários. 
Agora escolheremos o vértice temporário de menor custo c (vértice 3), que será 
classificado como permanente e repetimos o mesmo processo de identificação dos 
vértices que o tem como precedente. Esse processo continuará até termos o destino 
permanente. 
 
 
 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 11 
 
 
 
 
 
 
 
 
Figura 1.20: Solução do Exemplo 
 
O caminho mínimo entre os vértices 1 e 5 é {1 − 3 − 5} ou {1 − 3 − 4 − 5} e tem 
custo de 90un. Ele pode ser visto na Figura 1.20. 
 
Exercícios de Fixação - Algoritmo de Dijkstra 
 
1) São obtidas tiras de alumínio de 2cm a partir de outras de 12cm (espessura através de 
um processo de redução. A Tabela 1.2 descreve o custo de redução para cada 100m de 
alumínio. Determine a forma mais econômica de se obter tiras de 2cm. 
 
2) Uma empresa está planejando a substituição da sua frota de carros para o período 
2006-2011. No início de cada ano toma-se a decisão de se manter a frota operando ou se 
ela deve ser substituída. Essa substituição pode ocorrer no máximo após três anos de 
compra da frota. A Tabela 1.3 nos mostra o custo de substituição da frota como função 
do ano em que ela foi adquirida e o número de anos em operação. Determine o 
planejamento ótimo para a substituição da frota. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 12 
Redução (em cm) Espessura 
(cm) 2 4 6 
12 6,2 7,2 8,5 
10 6,8 7,4 9,2 
08 7,1 12,8 15,2 
06 8,2 14,6 - 
04 10,5 - - 
Tabela 1.2: Custo de Redução 
Custo de substituição por anos 
de operação 
Ano em que 
a frota foi 
adquirida 1 2 3 
2006 3800 4100 6800 
2007 4000 4800 7000 
2008 4200 5100 7200 
2009 4800 5700 - 
2010 5300 - - 
Tabela 1.3: Custo de substituição da frota 
1.3.2 Algoritmo de Floyd 
 
 Esse algoritmo serve para determinar o caminho mínimo entre todos os pares de 
vértices. 
 Inicialmente, cria-se uma matriz de distâncias e uma matriz de rotas do grafo 
seguindo as indicações a seguir: 
 
0
0� = ⇔
�
= = ∞ ⇔ ∉�
�
= ⇔ ∈�
ij
ij
ij ij
d i=j
D d (i, j) A
d c (i, j) A
 (1.8) 
 
0
0
0
� = � ∞�
= �
=��
ij ij
ij
r j d < 
R
r caso contrário. 
 (1.9) 
 
onde a matriz D é chamada de matriz de distâncias e R de matriz de rotas realizadas. 
 Em seguida, verifica-se a existência de um caminho de menor custo entre cada 
par de vértices, ao passar por um vértice intermediário, como na Figura 1.21. Caso 
exista, altera-se a matriz de distâncias, com esse menor valor e também a matriz de rotas 
para o vértice intermediário. Num grafo com n vértices, após montar a matriz de 
distâncias, serão feitas n iterações: 
 
• 1ª Iteração: descobrir se há caminhos que ficam menores ao passar pelo 
vértice 1 
• 2ª Iteração: descobrir se há caminhos que ficam menores ao passar pelo 
vértice 2 
• ... 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 13 
• nª Iteração: descobrir se há caminhos que ficam menores ao passar pelo 
vértice n. 
Os passos do Algoritmo de Floyd são apresentados a seguir: 
 
Figura 1.21: Idéia principal do Algoritmo de Floyd 
 
Algorithm 1 Algoritmo de Floyd 
 for k = 1, n do 
 if dik + dkj < dij then 
 dij � dik + dkj 
 rij � rik 
 end if 
 end for 
 
Ao executar esse algoritmo deve se atentar para as seguintes observações: 
 
• Não é necessário testar nenhum valor da diagonal principal da matriz, pois eles 
não irão variar; 
• Na k-ésima iteração, não haverá variação na linha pivô (linha k) e na coluna pivô 
(coluna k); 
• Na k-ésima iteração, caso exista na linha pivô (linha k) algum elemento onde dkj 
= �, então a coluna j não irá variar nessa iteração; 
• Na k-ésima iteração, caso exista na coluna pivô (coluna k) algum elemento onde 
dik = �, então a linha i não irá variar nessa iteração. 
 
Exemplo: Determine o caminho mínimo entre v5 e v2, v3 e v1 e v4 e v3 da Figura 1.22. 
 
 
Figura 1.22: Rede Orientada do Exemplo 
 
Solução: 
 Primeiramente vamos gerar as matrizes de distâncias e de rotas do grafo. 
Pesquisa Operacional II – Teoria dos GrafosProfª Lidia 14 
 1 2 3 4 5 1 2 3 4 5 
0
1 0 5 3
2 0 3
D 3 0 5
4 1 1 0 1
5 1 1 0
∞ ∞� �
� �
∞ ∞ ∞� �
� �= ∞ ∞ ∞
� �
∞� �
� �
∞ ∞	 
 
0
1 1 2 0 4 0
2 0 2 3 0 0
R 3 0 0 3 0 5
4 1 2 0 4 5
5 0 2 0 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
 
 
 Por esse ser um grafo com 5 vértices, realizaremos 5 iterações. Iniciaremos 
agora as iterações, não se esquecendo das observações. 
 
k = 1 (para esta iteração, tem-se a linha 1 e a coluna 1 como pivôs) 
Termo(s) que deve(m) ser analisado(s) nessa iteração: d42 
 
 1 2 3 4 5 1 2 3 4 5 
1
1 0 5 3
2 0 3
D 3 0 5
4 1 0 1
5 1 1 0
∞ ∞� �
� �
∞ ∞ ∞� �
� �= ∞ ∞ ∞
� �
∞� �
� �
∞ ∞	 
 
1
1 1 2 0 4 0
2 0 2 3 0 0
R 3 0 0 3 0 5
4 1 0 4 5
5 0 2 0 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
 
 
• d41 + d12 < d42? 
 1 + 5 < 1 ? Não 
 
 1 2 3 4 5 1 2 3 4 5 
1
1 0 5 3
2 0 3
D 3 0 5
4 1 0 1
5 1 1 0
∞ ∞� �
� �
∞ ∞ ∞� �
� �= ∞ ∞ ∞
� �
∞� �
� �
∞ ∞	 
1
 
1
1 1 2 0 4 0
2 0 2 3 0 0
R 3 0 0 3 0 5
4 1 0 4 5
5 0 2 0 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
2
 
 
k = 2 (para esta iteração, tem-se a linha 2 e a coluna 2 como pivôs) 
Termo(s) que deve(m) ser analisado(s) nessa iteração: d13, d43, d53. 
 1 2 3 4 5 1 2 3 4 5 
2
1 0 5 3
2 0 3
D 3 0 5
4 1 1 0 1
5 1 1 0
∞� �
� �
∞ ∞ ∞� �
� �= ∞ ∞ ∞
� �
� �
� �
∞	 
 
2
1 1 2 4 0
2 0 2 3 0 0
R 3 0 0 3 0 5
4 1 2 4 5
5 0 2 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 15 
• d12 + d23 < d13? 
 5 + 3 < �? Sim, então 
 d13 = d12 + d23 = 5 + 3 = 8 
 r13 = r12 = 2 
 
• d42 + d23 < d43? 
 1 + 3 < �? Sim, então 
 d43 = d42 + d23 = 1 + 3 = 4 
 r43 = r42 = 2 
 
• d52 + d23 < d53? 
 1 + 3 < �? Sim, então 
 d53 = d52 + d23 = 1 + 3 = 4 
 r53 = r52 = 2 
 1 2 3 4 5 1 2 3 4 5 
2
1 0 5 3
2 0 3
D 3 0 5
4 1 1 0 1
5 1 1 0
∞� �
� �
∞ ∞ ∞� �
� �= ∞ ∞ ∞
� �
� �
� �
∞	 
8
4
4
 
2
1 1 2 4 0
2 0 2 3 0 0
R 3 0 0 3 0 5
4 1 2 4 5
5 0 2 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
2
2
2
 
 
 Repetiremos esse mesmo processo para k = 3, k = 4 e k = 5, chegando a essas 
matrizes de distâncias e rotas: 
 
 1 2 3 4 5 1 2 3 4 5 
5
1 0 4 7 3 4
2 10 0 3 9 8
D 3 7 6 0 6 5
4 1 1 4 0 1
5 2 1 4 1 0
� �
� �
� �
� �=
� �
� �
� �
	 
 
5
1 1 4 4 4 4
2 3 2 3 3 3
R 3 5 5 3 5 5
4 1 2 2 4 5
5 4 2 2 4 5
� �
� �
� �
� �=
� �
� �
� �
	 
 
 
• de v5 para v2: 5 − 2, custo = 1 
• de v3 para v1: 3 − 5 − 4 − 1, custo = 7 
• de v4 para v3: 4 − 2 − 3 custo = 4 
 
1.3.3 Formulação Matemática do Problema de Caminho Mínimo 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 16 
 Sendo 1 e m os vértices de origem e destino, respectivamente, e cij o custo da ligação 
(i,j): 
1 1
1 1
1 1
. 0 1
1
m m
ij ij
i= j=
m m
ij ki
j k
Min c x
, se i
S.A x x , se i ou m
, se i=m= =
=�
�
− = ≠�
�
−�
� �
� �
 
0
1ij
, se (i, j) A
x
, caso contrário
∉�
= �
�
 
i, j = 1, 2, 3, ..., m 
 A modelagem do problema terá, portanto variáveis binárias, xij, as quais, ao 
assumirem o valor 1 indicam que o arco em questão faz parte da rota, e 0, caso 
contrário. 
Exemplo: Formular matematicamente o problema de caminho mais curto do grafo da 
Figura 1.23. 
 
 
 
 
 
 
Figura 1.23: Grafo do Exemplo 
 
Solução: 
{ }
2 7 2 5 4 1 4 3 4 5 1 7
1
1
0,1
OA AD AB OB OC CB CE BE BD DT ED ET
OA OB OC
DT ET
OA AB AD
OB AB CB BD BE
OC CB CE
AD BD ED DT
EB CE ED ET
ij
Min x x x x x x x x x x x x
S.A.
x x x
x x
x x x
x x x x x
x x x
x x x x
x x x x
x i,j
+ + + + + + + + + + +
+ + =
+ =
= +
+ + = +
= +
+ + =
+ = +
∈ ∀
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 17 
1.4 O Problema da Árvore Geradora Mínima 
 
 O problema da árvore geradora mínima objetiva encontrar o caminho mais curto de tal 
maneira que os arcos forneçam um caminho entre todos os pares de vértices. Esse modelo de 
problema pode ser aplicado a: 
 
• Projeto de redes de telecomunicação; 
• Projeto de redes de transporte (rodovias, ferrovias, etc.); 
• Projeto de redes de transmissão de energia. 
 
 Esse tipo de problema é resolvido por vários algoritmos, dentre eles o Algoritmo de 
Prim e o Algoritmo de Kruskal. 
 Para um melhor entendimento, dois novos conceitos serão apresentados. 
1.4.1 Conexidade de um grafo 
 
 Um grafo é dito conexo se existir pelo menos um percurso entre todos os pares 
de vértices. 
 Caso contrário, trata-se de um grafo não conexo. 
 
Figura 1.24: Conexidade 
 
 
 
Figura 1.25: Árvore Geradora 
1.4.2 Árvore e Árvore Geradora 
 
 Uma árvore é um grafo conexo e sem ciclos. Uma árvore geradora de um grafo 
G é um subgrafo de G que inclui cada vértice de G e é uma árvore. 
 Uma árvore possui as seguintes particularidades: 
 
• Se a árvore tem n vértices, então ela terá n − 1 arestas; 
• Caso seja eliminada uma aresta da árvore, teremos um grafo não-conexo; 
• Caso acrescente uma aresta entre qualquer par de vértices será formado 
somente um ciclo. 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 18 
1.4.3 Algoritmo de Prim 
 
1. Selecionar um nó arbitrariamente e ligá-lo ao nó mais próximo; 
2. Identificar o nó ainda isolado que esteja mais próximo de um nó já ligado e ligar 
estes dois nós. Repetir esse passo até que todos os nós estejam ligados entre si. 
 
Exemplo: Determine a árvore geradora mínima do grafo da Figura 1.26. 
 
 
Figura 1.26: Grafo do Exemplo 
 
Solução: 
 
 
Figura 1.27: Resolução utilizando o Algoritmo de Prim 
 
1.4.4 Algoritmo de Kruskal 
 
1. Ordenar as arestas por ordem crescente de custo, sendo os desempates feitos 
arbitrariamente, formando uma lista; 
2. Selecionar a primeira aresta da lista. Caso gere um ciclo, retirá-la da lista e voltar 
ao início de 2. Caso contrário, adicioná-la à árvore de suporte e retirá-la da lista. 
Repetir esse passo até que a árvore de suporte esteja formada. 
 
Exemplo: Determine a árvore geradora mínima do grafo do exemplo anterior (Figura 
1.26) utilizando o Algoritmo de Kruskal. 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 19 
Solução: 
(B,C) – 1ª aresta adicionada a árvore 
(D,E) – 2ª aresta adicionada à árvore 
(O,A) – 3ª aresta adicionada à árvore 
(A,B) – 4ª aresta adicionada à árvore 
(B,E) – 5ª aresta adicionada à árvore 
(O,C) – forma ciclo 
(B,D)– forma ciclo 
(C,E) – forma ciclo 
(O,B) – forma ciclo 
(D,W) – 6ª aresta adicionada à árvore - Fim 
(A,D) 
(E,W) 
 
 
Figura 1.28: Solução do Exemplo 
1.5 O Problema de Fluxo Máximo 
 
 O Problema de Fluxo Máximo objetiva maximizar o fluxo de um ponto de 
origem (ou fonte) até um ponto de destino (ou sorvedouro) tendo que respeitar as 
restrições de fluxo de cada arco da rede. Este tipo de problema pode aparecer 
envolvendo o fluxo de materiais como água, óleo, vapor através de uma rede de tubos; o 
fluxo máximo de veículos em um sistema de transporte; ou ainda quando se deseja 
determinar a capacidade máxima de uma linha de produção de um produto que pode ser 
fabricado utilizando vários roteiros diferentes, passando por vários centros de 
fabricação, cada um deles com uma certa capacidade instalada. 
 De uma forma geral, seja G(N, A) uma rede orientada onde uij representa a 
capacidade do arco que liga o vértice i ao vértice j tal que i, j � A. Deseja-se saber qual 
o número máximo de unidades que podem circular do vértice 1 ao vértice n por unidade 
de tempo. 
 
1.5.1 Modelo de Otimização Linear 
 
 Para a formulação desse modelo considera-se existente um arco virtual ligando o 
nó n ao nó 1 que terá capacidade infinita. Neste arco teremos o fluxo total da rede. 
 
Figura 1.29: Exemplo de Arco Virtual 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 20 
 O modelo matemático será formulado conforme as instruções abaixo: 
 1Função Objetivo n Max x (1) 
Restrições 0 1
∈ ∈
− =� �ij ki
(i,j) A (k,i) A
 SA x x i= , ..., n (2) 
 0 ≤ ≤ ∀ ∈ij ij x u (i,j) A (3) 
 
onde: (1) mostra que se quer maximizar o fluxo entre a fonte e o sorvedouro; (2) faz 
com que o fluxo que chega em cada nó seja igual ao fluxo que sai do mesmo; e (3) 
limita o fluxo do arco no intervalo [0, uij], onde uij representa o fluxo máximo do arco 
que liga os nós i e j. 
 
Exemplo: A Companhia Estadual de Gás do Rio de Janeiro (CEG-RJ) deseja 
determinar a quantidade máxima de metros cúbicos por segundo de gás que pode 
bombear da estação de Campos para a cidade de Volta Redonda, através de uma rede de 
gasodutos já existentes. A Figura 1.30 apresenta a atual rede de distribuição de gás da 
CEG-RJ. Formule um problema de programação linear para este caso. 
 
 
Figura 1.30: Rede de distribuição de gás da CEG-RJ 
Solução: 
Primeiramente cria-se o arco virtual. No exemplo em estudo, ele terá fluxo x61. 
 Max x61 
 SA x61 − (x12 + x13 + x14) = 0 (nó 1) 
 x12 − (x23 + x25 + x26) = 0 (nó 2) 
 x13 + x23 + x43 − (x35) = 0 (nó 3) 
 x14 − (x43 + x45) = 0 (nó 4) 
 x25 + x35 + x45 − (x56) = 0 (nó 5) 
 x26 + x56 − (x61) = 0 (nó 6) 
 0 � x12 � 15 
 0 � x13 � 5 
 0 � x14 � 10 
 0 � x23 � 8 
 0 � x25 � 10 
 0 � x26 � 10 
 0 � x35 � 10 
 0 � x43 � 7 
 0 � x45 � 9 
 0 � x56 � 15 
 0 � x61 � 1 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 21 
1.5.2 Algoritmo de Ford-Fulkerson 
 
Algoritmo de Ford-Fulkerson simplificado 
 
 É uma heurística (não garante solução ótima) que funciona pela definição de um 
caminho de aumento de fluxo num grafo. Caminho de aumento de fluxo é aquele que 
parte da fonte até o sorvedouro e que apresenta o fluxo de pelo menos um de seus arcos 
saturado, isto é, utiliza todo o fluxo disponível de pelo menos um arco. Ao 
acrescentarmos o caminho de aumento ao fluxo já existente no grafo, o fluxo máximo é 
atingido quando não for possível descobrir mais caminhos de aumento. Para aplicar o 
Algoritmo de Ford-Fulkerson substituímos o fluxo de cada arco pelo par ordenado (a, 
b), onde a representa o fluxo disponível no arco e b o fluxo enviado pelo arco. 
 
Exemplo: Aplique o Algoritmo de Ford-Fulkerson (heurística) à rede de distribuição de 
gás da CEG-RJ da Figura 1.30 do exemplo anterior. 
 
Solução: 
 
 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 22 
 
 
Figura 1.31: Resolução utilizando o Algoritmo de Ford-Fulkerson (heurística) 
 
 Como não existe mais nenhum caminho de aumento de fluxo, então o fluxo 
máximo é igual a 25. 
 
Algoritmo de caminhos aumentados 
 
 Este algoritmo se baseia nos conceitos de rede residual e caminho aumentado. 
A rede residual mostra as capacidades dos arcos remanescentes, chamadas 
capacidades residuais, para designar fluxos adicionais. A capacidade residual para o 
fluxo que vai de um nó a outro é indicada por um número colocado próximo ao nó de 
origem. Na Figura 1.32, o arco O � B possui capacidade de arco igual a 7, havendo 
uma capacidade residual de 2 para qualquer designação de fluxo de O para B, e uma 
capacidade residual de 5 para o fluxo de B para O. 
 
 
 
Figura 1.32: Capacidade residual de fluxo 
 
Quando alguma quantidade de fluxo é designada a um arco, essa quantidade deve 
ser subtraída da capacidade residual na direção em questão e adicionada à capacidade 
residual na direção oposta. 
Um caminho aumentado é um caminho direcionado da origem para o destino de 
modo que todo arco nesse caminho tenha fluxo residual estritamente positivo. 
O algoritmo de caminhos aumentados identifica um caminho aumentado na rede, 
acrescentando a esta um fluxo igual à capacidade residual do caminho selecionado. São 
realizadas sucessivas iterações até que não exista mais nenhum caminho com fluxo 
residual positivo, o que indica que a solução atual é ótima (como os caminhos 
aumentados podem cancelar parte dos fluxos previamente designados na rede original, 
selecionar os caminhos indiscriminadamente não impede o emprego de uma 
combinação melhor de designações de fluxo, garantindo que a solução obtida seja 
ótima). 
 
Exemplo: Aplique o Algoritmo de Caminhos Aumentados à rede da Figura 1.33. 
 
 
 
 
�� ��
�� ��
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 23 
O
A
C
B
D
E
T
3
5
4
1
2
4
4
9
6
5
7 1
 
 
Figura 1.33: Rede do exemplo 
 
Solução: 
 
• 1º Caminho: O – B – E – T 
Capacidade: 5 
Fluxo Máximo: 5 
O
A
C
B
D
E
T
0
0
4
1
2
4
4
9
5
5
5
1
5
2
0
0
0
0
0
0
3
0
0
1
 
 
Figura 1.34: 1º Caminho 
 
• 2º Caminho: O – A – D – T 
Capacidade: 3 
Fluxo Máximo: 5 + 3 = 8 
O
A
C
B
D
E
T
3
3
4
1
2
4
4
6
5
5
5
1
2
2
0
0
0
0
0
0
0
0
3
1
 
 
Figura 1.35: 2º Caminho 
 
• 3º Caminho: O – A – B – D – T 
 Capacidade: 1 
 Fluxo Máximo: 8 + 1 = 9 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 24 
O
A
C
B
D
E
T
3
4
4
0
2
4
3
5
5
5
5
1
1
2
0
0
0
0
1
10
0
4
1
 
 
Figura 1.36: 3º Caminho 
 
• 4º Caminho: O – B – C – E – T 
 Capacidade: 1 
 Fluxo Máximo: 9 + 1 = 10 
 
O
A
C
B
D
E
T
3
4
4
0
1
3
3
5
6
5
6
1
1
1
0
1
1
0
1
1
0
0
4
0
 
 
Figura 1.37: 4º Caminho 
 
• 5º Caminho: O – C – E – D – T 
 Capacidade: 1 
 Fluxo Máximo: 10 + 1 = 11 
O
A
C
B
D
E
T
3
4
3
0
1
2
3
4
6
5
6
0
1
1
1
1
2
0
1
1
0
1
5
0
 
 
Figura 1.38: 5º Caminho 
 
• 6º Caminho: O – B – D – T 
 Capacidade: 1 
 Fluxo Máximo: 11 + 1 = 12 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 25 
O
A
C
B
D
E
T
3
4
3
0
1
2
2
3
6
5
7
0
1
0
1
1
2
0
2
1
0
1
6
0
 
 
Figura 1.39: 6º Caminho 
 
• 7º Caminho: O – C – B – D – T 
 Capacidade: 1 
 Fluxo Máximo: 12 + 1 = 13 
O
A
C
B
D
E
T
3
4
2
0
2
2
1
2
6
5
7
0
1
0
2
0
2
0
3
1
0
1
7
0
 
 
Figura 1.40: 7º Caminho 
 
• 8º Caminho: O – C – E – B – D – T 
 Capacidade: 1 
 Fluxo Máximo: 13 + 1 = 14 
O
A
C
B
D
E
T
3
4
1
0
2
1
0
1
6
4
7
0
1
0
3
0
3
1
4
1
0
1
8
0
 
 
Figura 1.41: 8º Caminho 
 
Exercício de Fixação – Algoritmo dos caminhos aumentados 
1) Aplique o Algoritmo de Ford-Fulkerson de caminhos aumentados à rede de 
distribuição de gás da CEG-RJ (Figura 1.30). 
Pesquisa Operacional II – Teoria dos Grafos 
 Profª Lidia 26 
1.6 Bibliografia 
 
1. ALOISE, J.D.; CRUZ, J.S. Teoria dos Grafos e Aplicações. Disponível em: 
<http://www.dimap.ufrn.br/dario/disciplinas.htm>. Acesso em: 20 jul. 2007. 
2. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa 
Operacional. 1.ed. Rio de janeiro: Editora Campus, 2007. 
3. BAAZARA, M.S.; JAVIS, J.J.; SHERALI, H.D. Linear Programming and 
Network Flows. 2.ed. Nova York: Wiley, 1990. 
4. BOAVENTURA NETTO, P.O. Grafos - Teoria, Modelos e Algoritmos. 3.ed., São 
Paulo: Edgard Blücher Ltda, 2003. 
5. FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma Introdução 
Sucinta à Teoria dos Grafos. Disponível em: <http://www.ime.usp.br/˜pf 
/teoriadosgrafos/ texto/TeoriaDosGrafos.pdf>. Acesso em: 19 ago. 2007. 
6. FERREIRA, J.A.S.; SIMARIA, A.S.A. Algoritmos para a Resolução de Problemas 
em Redes. Disponível em: 
<http://www2.egi.ua.pt/cursos/files/SAD/Algoritmos_Redes.pdf>. Acesso em: 14 nov. 
2007. 
7. GUIMARÃES, J.O. Teoria dos Grafos. Disponível em: <http://www.dc.ufscar.br/ 
jose/courses/tg.htm>. Acesso em: 20 jul. 2007. 
8. LACHTERMACHER,G. Pesquisa Operacional na Tomada de Decisões. 3.ed. Rio 
de janeiro: Editora Campus, 2007. 
9. MARTINS, F.M. Paradigmas da Programação III - Notas de Aula. Disponível 
em: <http://sim.di.uminho.pt/ ensino2.php3?seccao=geral&id=45>. Acesso em: 20 jul. 
2007. 
10. MEZA, L.A. Pesquisa Operacional II - Teoria dos Grafos. 2007. 22 f. Notas de 
Aula. 
11. NOGUEIRA, F. Pesquisa Operacional - Notas de Aula. Disponível em: 
<http://www.engprod.ufjf.br/fernando/epd015/>. Acesso em: 24 nov. 2007. 
12. PATRÍCIO, P. Breve introdução à teoria dos grafos. Disponível na internet. 
Acesso em: 20 jul. 2007. 
13. RAGGI, L.A. Teoria e Modelos de Grafos. Disponível em: 
<http://www.dpi.ufv.br/disciplinas/inf330/index.php?pk=167>. Acesso em: 16 jul. 
2007. 
14. RIBEIRO, C.C.; ROCHA, C.T. Algoritmos em Grafos. Disponível em: 
<http://wwwdi.inf.puc-rio.br/ celso/disciplinas.htm>. Acesso em: 21 nov. 2007. 
15. SILVA JÚNIOR, E. P. Análise Combinatória e Teoria dos Grafos. Disponível 
em: <http://www.inf.ufrgs.br/ prestes/disciplinas.html>. Acesso em: 20 jul. 2007. 
16. SILVA,M. Grafos - Definições e Conceitos Fundamentais. Disponível em: 
<http://www.moraissilva.com/grafos_cap1.pdf>. Acesso em: 20 jul. 2007. 
17. SOUZA, L. O Teorema das Quatro Cores. Millenium - Revista do ISPV , n.24, p. 
125-51, out. 2001. Disponível em: <http://www.ipv.pt/millenium/Millenium24/12.pdf>.