GRAFOS EM SITUAÇÕES DESCRITAS

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARÁ 
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS – ICEN 
PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
 
 
 
IDENTIFICAÇÃO DE VÉRTICES E ARESTAS EM PROBLEMAS 
DESCRIÇÃO DE TÉCNICAS PARA SOLUÇÃO 
 
 
 
 
 
 
 
 
 
VERÔNICA SOUZA LEAL SALIBA GOMES 
MÁRIO AUGUSTO FONSECA GOMES 
 
 
 
 
 
Terceiro trabalho elaborado como parte da 
disciplina de Teoria da Computação: Grafos do 
Programa de Pós-Graduação em Ciência da 
Computação da UFPA. 
 
 
 
 
 
 
 
UFPA / ICEN / PPGCC 
Campus Universitário do Guamá 
Belém – Pará - Brasil 
Abril/2010 
 
OBJETIVO: Apresentação de solução para 24 problemas do site: 
http://www.inf.ufsc.br/grafos/problemas/index.htm, com identificação dos vértices e arestas em cada caso, 
pesquisa e descrição da técnica de grafos a ser usada para resolver o problema, com um pequeno de exemplo de 
aplicação da técnica no problema considerado; 
 
OBSERVAÇÃO: Para todos os problemas descritos, um grafo será representado por G (V, E), onde V é o conjunto 
de vértices e E é o conjunto de arestas do grafo. 
 
 
PROBLEMA 1: Polígono 
 
 Descrição do problema: Polígono é um jogo individual que começa com N vértices, como no 
exemplo da Figura 1, onde N = 4. Cada vértice é rotulado com um número inteiro e cada aresta 
é rotulada ou com o símbolo + (adição) ou com o símbolo * (produto). As arestas são 
numeradas de 1 a N. 
 
 
 
 
Figura 1. Polígono 
 
Na primeira jogada, uma das arestas é removida. Jogadas seguintes envolvem os seguintes 
passos: 
• escolha uma aresta E e dois vértices v1 e v2 que são ligados por E, e 
• substitua E, v1 e v2 por um novo vértice, rotulado com o valor resultante da operação 
indicada por E sobre os valores v1 e v2. 
O jogo termina quando não há mais arestas, e a sua pontuação é o rótulo do vértice 
remanescente. 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do 
problema é definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um valor numérico inteiro} 
o E = {(vi,vj, o)} | existe um operando o (+, -, *, / ) entre os vértices vi e vj} 
 Descrição da técnica para resolução: 
A solução pode consistir em utilizar a representação computacional de grafos por lista 
de adjacências, por exemplo. O vetor das arestas contém o operando matemático e o 
vetor de vértices os valores numéricos, com a representação de seus respectivos vértices 
adjacentes. A implementação deve consistir em um algoritmo para a remoção de arestas 
e execução das operações que garantam o maior valor final. 
 
PROBLEMA 2: das Pontes de Königsberg 
 
 Descrição do problema: No século XVIII havia na cidade de Königsberg um conjunto de sete 
pontes (identificadas pelas letras de a até f na figura abaixo) que cruzavam o rio Pregel. Elas 
conectavam duas ilhas entre si e as ilhas com as margens. Por muito tempo os habitantes daquela 
cidade se perguntavam se era possível cruzar as sete pontes em uma caminhada contínua sem passar 
duas vezes por qualquer uma delas. 
 
 
 
 
 
 
 
Figura 2. Pontes da cidade de Königsberg 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma ilha ou uma margem} 
o E = {(vi,vj, p)} | existe uma ponte p unindo as margens ou ilhas vi e vj} 
Desta forma, extraindo os elementos do problema para cada conjunto definido, temos: 
 
o G = (V, E), sendo: 
o V = {A, B, C, D} 
o E = {(A,C,c), (A,C,d), (A,B,a), (A,B,b), (A,D,e), (B,D,f), (C,D,g)} 
 
O Grafo, construído a partir dessas definições pode apresentar-se como: 
 
 
 
 
 
 
 
 
Figura 3. Grafo G - Pontes de Königsberg 
 
Conforme definido por [Euler, 1736], para a modelagem do problema, as distâncias envolvidas 
ou o formato das ilhas são irrelevantes. O que importa é como as várias porções de terra estão 
interligadas entre si. Desta forma, a representação através do grafo G, permite utilizar o teorema de 
Euler para solução do problema, conforme técnica descrita no tópico a seguir. 
 
 Descrição da técnica para resolução: 
 
A solução para o problema consiste em, partindo de qualquer vértice do grafo, tentar atravessar 
todas as arestas uma única vez. Trata-se, portanto, de verificar se, no grafo modelado, existe um 
caminho de Euler. 
 
Teorema: Existe um caminho de Euler (que não é um circuito) em um grafo se e somente se o 
grafo é conexo (isto é, existe um caminho ligando qualquer par de vértices) e tem exatamente dois 
vértices de grau ímpar (ou seja, o número de arestas que nele incidem é ímpar). 
 
Portanto, pela análise do grafo G, observa-se que: para todo v є V, grau(v) é ímpar. Logo, o 
grafo G não possui um caminho e nem um circuito de Euler, o que significa que o problema não 
possui solução. 
 
 
 
PROBLEMA 3: do caixeiro viajante 
 
 Descrição do problema: Suponha que a área de venda de um caixeiro viajante inclua várias 
cidades, muitas das quais, aos pares, estão conectadas por rodovias. O trabalho do caixeiro requer 
que ele visite cada cidade pessoalmente. Sob que condições seria possível estabelecer uma viagem 
circular (que o leve ao ponto de partida) de forma a que ele visite cada cidade exatamente uma vez? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cidade} 
o E = {(vi,vj)} | há uma estrada que conecta diretamente as cidades vi e vj} 
 Descrição da técnica para resolução: 
 
A partir da modelagem apresentada anteriormente, a solução do problema consiste em verificar 
se o grafo G é Hamiltoniano, ou seja, se contém um ciclo ou circuito Hamiltoniano. 
Um grafo G é dito Hamiltoniano se existe um ciclo em G (caminho ou seqüência de arestas 
começando e terminando em um mesmo vértice) que contenha todos os seus vértices, de tal forma 
que cada vértice só aparece uma vez no ciclo. 
 
o Exemplo: Considerando-se o mapa abaixo, contendo as cidades a serem visitadas por um 
caixeiro viajante, pode-se representá-las através do grafo a seguir. Como exemplo, temos o ciclo 
Hamiltoniano passando por: Badajoz – Évora – Faro – Córdoba – Madrid – Aveiro - Badaroz. 
 
Figura 4. Mapa exemplo Figura 5. Grafo G (Ciclo: Badajoz – Évora – Faro – 
 Córdoba – Madrid – Aveiro - Badajoz) 
 
 
 
 
 
 
 
 
 
 
Atualmente, os conceitos do problema do caixeiro viajante são aplicados, principalmente, para 
encontrar o circuito (ou ciclo) de menor custo (mínimo) para grafos Hamiltonianos com arestas 
“valoradas”. No exemplo anterior, o objetivo seria encontrar o circuito a ser percorrido com a menor 
distância total. 
 
PROBLEMA 4: do desenho da casa 
 
 Descrição do problema: No desenho abaixo, uma criança diz ter posto a ponta do lápis numa 
das bolinhas e com movimentos contínuos (sem levantar e sem retroceder o lápis) traçou as 
linhas que formam o desenho da casa, traçando cada linha uma única vez. 
 
 
Figura 6. O desenho da casa 
 
A mãe da criança acha que ela trapaceou, pois não foi capaz de achar nenhuma seqüência que 
pudesse produzir tal resultado. Você concorda com esta mãe? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma bolinha vermelha do desenho da casa} 
o E = {(v1,v2)} | há uma linha que conecta diretamente as bolinhas v1 e v2} 
 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
 
 
 
 
 
 
 
Figura 7. Grafo representativo e graude seus vértices 
 
 Descrição da técnica para resolução: 
 
A solução para o problema consiste em, partindo de qualquer vértice do grafo, tentar atravessar 
todas as arestas uma única vez. Ou seja, encontrar um caminho de Euler. Pelo teorema descrito a 
seguir, é possível verificar que existe um caminho de Euler, uma vez que só dois vértices possuem 
grau ímpar. Conclui-se, então, que a mãe estava errada, já que é possível a criança ter desenhado a 
casa da forma como descreveu. 
 
Teorema: Se um grafo for conexo e possuir apenas dois vértices de grau ímpar então tem pelo 
menos um caminho de Euler. 
 
 
o Exemplo: A figura abaixo representa uma das maneiras como a criança poderia ter 
procedido: 
 
Figura 8. Exemplo de solução 
 
PROBLEMA 5: do Assassinato do Bilionário Count Van Diamond 
 
 Descrição do problema: O cenário abaixo é a residência do bilionário Count Van Diamond, que 
acaba de ser assassinado. Sherlock Gomes (um conhecido detetive que nas horas vagas é um 
estudioso da teoria dos grafos) foi chamado para investigar o caso. O mordomo alega ter visto o 
jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar 
aquela sala pela mesma porta que havia entrado. O jardineiro, contudo, afirma que ele não 
poderia ser a pessoa vista pelo mordomo, pois ele havia entrado na casa, passado por todas as 
portas uma única vez e, em seguida, deixado a casa. Sherlock Gomes avaliou a planta da 
residência (conforme figura abaixo) e em poucos minutos declarou solucionado o caso. Quem 
poderia ser o suspeito indicado por Sherlock Gomes? Qual o raciocínio utilizado pelo detetive 
para apontar o suspeito? 
 
 
Figura 9. Planta da residência 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um cômodo da casa} 
o E = {(vi,vj)} | vi esta ligado a vj por uma porta} 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
 
Figura 10. Grafo representativo e grau de seus vértices 
 
 Descrição da técnica para resolução: 
 
Para descobrir se o jardineiro fala a verdade, é preciso encontrar um circuito de Euler no grafo 
representado anteriormente. Ou seja, um caminho que percorra cada aresta uma única vez e retorne 
ao vértice inicial. 
 
Teorema: Um grafo conexo tem um circuito de Euler se e somente se todos os seus vértices 
possuem grau par. 
 
Nota-se que existem, no grafo, exatamente dois vértices de grau ímpar (P e D). Assim, o único 
percurso que permite atravessar todas as arestas uma única vez, terá de se iniciar em P e terminar 
em D (ou vice-versa), formando um caminho de Euler e não um circuito. 
Portanto, não é possível entrar na casa pela sala da piscina, passar por todas as portas (percorrer 
todas as arestas) uma única vez e em seguida deixar a casa. Conclui-se, então, que o jardineiro está 
mentindo, tornando-se o suspeito indicado por Sherlock Gomes. 
 
PROBLEMA 6: do passeio do cavalo (xadrez) 
 
 Descrição do problema: O Cavalo é a única peça do xadrez que pode saltar sobre outras peças. 
Ele tem um movimento bem peculiar em formato de "L": duas casas no sentido vertical ou 
horizontal e uma casa no outro sentido. No esquema que se segue estão apresentadas todas as 
possibilidades de jogada do cavalo (indicado pelos pontos em azul) a partir da posição onde ele 
está. 
 
 
 
Uma seqüência de movimentos do cavalo é apresentada na figura que se segue: 
 
 
 
Seguindo as regras de movimento do cavalo, é possível que um cavalo parta de uma casa 
qualquer, percorra todo o tabuleiro visitando cada casa uma e somente uma única vez e retorne 
à casa inicial? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma casa do tabuleiro de xadrez} 
o E = {(vi,vj)} | a casa vj pode ser atingida a partir da casa vi por um único movimento de 
cavalo} 
 Descrição da técnica para resolução: 
 
Conforme definido por [MARIANI, 2010], a solução para este problema consiste em verificar 
se o grafo G é Hamiltoniano, ou seja, se G possui um ciclo ou circuito (“seqüência” de arestas que 
começa e termina no mesmo vértice) que contenha todos os seus vértices, sendo que cada vértice só 
aparece uma vez no ciclo. O grafo modelado a partir das definições apresentadas anteriormente 
possui 64 vértices e 168 arestas. A seguir, como exemplo, está representado um dos circuitos 
hamiltonianos encontrado, o que mostra que é possível que um cavalo parta de uma casa qualquer, 
percorra todo o tabuleiro, visitando cada casa uma e somente uma única vez, e retorne à casa inicial. 
o Exemplo: 
 
Figura 11. Exemplo de Solução 
 
PROBLEMA 7: da pavimentação de estradas 
 
 Descrição do problema: Tertuliano Gonçalves havia prometido casamento a Josefina das 
Graças. O evento deveria ser realizado, segundo ele, assim que acabasse o contrato de trabalho 
recém assinado com uma empresa encarregada de pavimentar toda a rede de estradas que ligava 
Santana do Caixa Prego (cidade onde morava Josefina) às cidades da região. O trabalho iria 
começar em Santana e prosseguir em continuidade, estada após estrada, terminando, segundo 
explicou Tertuliano, na própria Santana. A rede de estradas poderia ser representada pela matriz 
de adjacência que se segue, na qual a cidade de Santana é representada pelo número 1. 
 
 
 
1 - Você que leu esta estória acha que Tertuliano estava sendo sincero com Josefina? Por quê? 
2 - E se o itinerário 1-5-9-10 estivesse a cargo de outra empresa, estaria ele sendo sincero? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cidade da região} 
o E = {(vi,vj)} | a cidade vi está ligada diretamente à cidade vj por uma estrada a ser 
pavimentada, conforme matriz de adjacência} 
O Grafo, construído a partir dessas definições pode apresentar-se como: 
 
 
 
Figura 12. Grafo representativo e grau de seus vértices 
 
 
 Descrição da técnica para resolução: 
 
Para responder ao primeiro questionamento é preciso verificar se existe um circuito de Euler, 
começando e terminando no vértice 1, que representa a cidade de Santana. Conforme descreve o 
teorema de Euler, um grafo conexo G tem um circuito de Euler, se e somente se, todo vértice de G 
possuir grau par. Tal situação não ocorre no grafo representado anteriormente, logo, não é possível 
pavimentar toda a rede de estradas começando e acabando em Santana. 
Para o segundo questionamento, a resposta também é não, já que, ao retirarmos do grafo as 
arestas {1;5}, {5;9}e {9;10}, continuaríamos a ter vértices de grau ímpar, o que pelo teorema 
caracteriza a não existência de um circuito de Euler. Portanto, não é possível pavimentar a rede de 
estradas começando e acabando em Santana, mesmo que o itinerário 1-5-9-10 esteja a cargo de 
outra empresa. 
 
PROBLEMA 8: da Coleta de Correspondências 
 
 Descrição do problema: A Empresa Brasileira de Correios e Telégrafos mantém vários postos 
de coleta de correspondência espalhados pela cidade, inclusive em bairros mais afastados. A 
localização e a quantidade destes postos são por vezes modificados de forma que diariamente o 
motorista responsável por recolher a correspondência recebe um esquema que mostra o melhor 
percurso para passar em todos os postos de coleta. Este esquema é montado manualmente por 
um funcionário da E.C.T.. Este funcionário não agüenta mais as reclamações dos motoristas de 
que as rotas que ele traça nunca são as melhores e pede demissão. O chefe, sem saber como 
tratar o problema, resolve contratarum especialista (você), para resolvê-lo. Como você 
modelaria o problema? Como encontrar a melhor rota? Que particularidades devem ser 
tratadas? 
 
 Identificação dos vértices e arestas: A escolha do grafo direcionado (dígrafo) utilizado na 
modelagem do problema é definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um posto de coleta} 
o E = {(vi,vj)} | o posto vi está ligado diretamente ao posto vj por uma rua, sendo esta 
aresta direcionada, conforme o sentido da rua} 
 Descrição da técnica para resolução: 
A solução para o problema da coleta de correspondências está em encontrar um ciclo 
hamiltoniano, ou seja, um caminho que comece em um vértice, passe por todos os outros uma 
única vez, e retorne ao vértice inicial. A principal particularidade a ser tratada neste problema, é 
em relação ao sentido das ruas, ou seja, deve-se utilizar um grafo direcionado (dígrafo) na 
representação do problema. Outra questão é considerar a menor distância a ser percorrida pelo 
motorista. 
 
PROBLEMA 9: do Robô-Café 
 
 Descrição do problema: Na empresa RoboCamp, fabricante de robôs industriais, os engenheiros 
desenvolveram um robô que distribui cafezinhos no escritório da empresa. Para o robô poder 
realizar esta tarefa, os engenheiros da empresa lhe acoplaram uma máquina de café e rodas para 
ele se locomover. Eles também o dotaram de vários sensores que lhe permite desviar de mesas, 
cadeiras, pessoas e outros obstáculos. Ou seja, ele é capaz de locomover-se numa sala qualquer 
sem risco de choque com as pessoas, móveis e etc. Os engenheiros programaram o robô para 
fazer um caminho circular passando por todas as salas do escritório, de sorte que ele está 
constantemente passando nas diversas salas e servindo cafezinhos. 
 
O diretor de comercialização da empresa gostou tanto do resultado que resolver comercializar 
este tipo de robô. Mas para facilitar a implantação do robô-café, o diretor sugeriu aos 
engenheiros que pensassem numa forma do robô se adaptar a diferentes configurações de 
escritórios, ou seja, que o robô "escolhesse" o melhor roteiro de oferta de cafezinhos. Escadas e 
elevadores ficariam de fora desta primeira versão; ele só precisaria operara adequadamente em 
um mesmo piso. 
Critérios para escolha do roteiro: 
• o robô deveria ficar constantemente passando em todas as salas onde houvesse um 
emissor de sinal de local de parada; 
• o robô deveria minimizar o número de passagens em cada sala para não perturbar 
demais a atividade do pessoal da sala; 
• ao passar novamente por uma sala, o robô só deveria parar nela se ele já houvesse 
completado a volta completa em todas as outras salas (para evitar a ciúmes); 
Particularidades: 
• entre duas salas poderia haver mais de uma porta; 
• algumas salas poderiam ter várias portas para outras salas (em particular os 
corredores); 
• nem todas as salas teriam necessariamente pontos de parada (os corredores, por 
exemplo). 
Um dos engenheiros é seu amigo e lhe conta, desanimado, seu drama. Ele lhe pergunta se você 
tem alguma sugestão. Com bom amigo, você não quer desanimá-lo mais, e diz que não tem de 
pronto algo palpável, mas fica de pensar no caso. E agora, como sair desta? 
 
 Identificação dos vértices e arestas: O primeiro grafo, proposto por [LELLIS, 2008], utilizado 
para a solução, representa a disposição das salas do escritório: 
o G = (V,E) 
o V = {v | v é uma sala} 
o E = {(v1, v2) | há uma porta ligando v1 e v2} 
 
O segundo grafo é um modelo utilizado pelo robô, todas as salas que não devem ser visitadas 
são excluídas, ligando diretamente as que precisam de seus serviços. 
o G = (V,E) 
o V = {v | v é uma sala que deve ser visitada} 
o E = {(v1, v2) | é possível ir de v1 a v2 passando por portas e/ou corredores} 
 
 Descrição da técnica para resolução: 
Com base na representação anterior, é possível identificar que a solução consiste em: 
• Encontrar um circuito que percorra todos os vértices do grafo; 
• Este circuito deve repetir o mínimo de vezes os vértices; 
Se o grafo analisado fosse completo, o problema recairia em achar um ciclo Hamiltoniano de 
custo mínimo. No entanto, não há garantia de que o grafo seja completo. O mais provável é que 
os vértices tenham que se repetir para poder percorrer a todos para que todos sejam percorridos. 
A solução descrita por [LELLIS, 2008], propões tornar o grafo completo, colocando como 
pesos das arestas o caminho de custo mínimo entre elas, e então resolver o problema como se 
fosse o do caixeiro viajante. Trata-se de uma aproximação da solução ótima, com a utilização 
do algoritmo do vizinho mais próximo, que possui os seguintes passos: 
• Escolha um vértice inicial; 
• Encontre a aresta de menor peso que conecte o vértice atual a um vértice não visitado 
v; 
• Defina v como o vértice atual; 
• Marque v como visitado; 
• Se todos os vértices no domínio foram visitados, termine; 
• Vá para o passo 2. 
 
o Exemplo: O exemplo abaixo foi elaborado e implementado por [LELLIS, 2008]. 
Primeiramente, as figuras abaixo representam a planta de um escritório e o primeiro 
grafo gerado. Os corredores também são representados por vértices (4, 5, 9, 12): 
 
 
 
 
Figura 13. Representação de um exemplo – Planta e grafo representativo 
A versão do grafo para o robô ficaria como a seguir, os pesos foram inventados pelo autor como 
exemplo. Ao lado o resultado do algoritmo de custo mínimo, com o melhor circuito a ser 
percorrido. 
 Figura 14. Representação do segundo grafo e resultado 
 
PROBLEMA 10: do caminho de custo mínimo 
 
 Descrição do problema: 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 caminho de menor custo entre quaisquer duas cidades por ela servidas. Como 
realizar esta tarefa? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cidade} 
o E = {(vi,vj,d)} | há uma conexão por estrada entre as cidades vi e vj, sendo d a distância 
que as separa} 
 
 Descrição da técnica para resolução: 
 
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. 
 
PROBLEMA 11: do metrô 
 
 Descrição do problema: Considere a rede de metrô de uma cidade como Barcelona, na 
Espanha. Esta rede cobre boa parte da cidade, sendo composta por várias linhas que se cruzam 
em estações específicas. Nestes pontos de cruzamento um usuário pode livremente sair de uma 
composição e passar para uma composição de outra linha. Sendo assim, em geral o usuário tem 
mais de uma opção de rota quando deseja deslocar-se de uma parte a outra da cidade. Escolher a 
melhor rota passa, então, a ser fundamental para que o deslocamento seja o mais rápido 
possível. 
 
As distâncias entre estações vizinhas do metrô não são iguais e, conseqüentemente, o tempo de 
deslocamento entre estações vizinhas não é constante. Estas diferenças de tempo não são, 
contudo, significativas quando comparadas com os tempos de parada das composições nas 
estações e de troca de composição (de linha). 
 
Em redes de metrô de várias cidades do mundo há sistemas computacionais que auxiliam os 
usuários a escolher a melhor rota para um deslocamento particular. Mais do que simplesmente 
indicar uma rota possível, estes sistemas procuram identificar aquela rota que conduz o usuário 
o mais rapidamente ao seu destino. Dois critérios básicos para esta escolha são (em ordem de 
importância): procurar minimizar o número de trocas de composição (de linhas);procurar 
minimizar o número de paradas em estações. 
 
 
Mapa do Metrô da cidade de Barcelona (Espanha) 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma estação de metrô} 
o E = {(vi,vj,p)} | há uma linha ligando as estações vi e vj, sendo p um peso atribuído para 
o deslocamento} 
 Descrição da técnica para resolução: 
Tendo-se como base a representação anterior, podemos criar um grafo onde cada linha (aresta) 
ligando duas estações (vértices) terá um peso. O peso será maior quando for necessária a troca 
de composição, o que busca atender ao critério de minimização das trocas de composição. 
Desta forma, este problema pode ser resolvido aplicando os algoritmos de caminhos mais curtos 
em grafos (por exemplo, o algoritmo de Dijkstra) 
 
o Exemplo: Considerando a representação simplificada, abaixo, de uma linha de metrô, 
podemos produzir o grafo ao lado e então aplicar o algoritmo para encontrar os 
caminhos de menor peso entre as estações. 
 
 
 
 
 
 
Figura 15. Exemplo de representação 
 
PROBLEMA 12: da RNP 
 
 Descrição do problema: A RNP (Rede Nacional de Pesquisa) é uma rede de computadores que 
interliga um grande número de instituições de ensino/pesquisa do sistema público de educação. 
Em algumas cidades há um POP (Ponto de Presença da RNP). Considerando que em algumas 
situações há mais de uma possível rota de comunicação entre dois POP's, como fazer para 
determinar qual a rota mais apropriada? 
 
 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um POP} 
o E = {(vi,vj,c)} | há uma comunicação direta (link) entre os POPs vi e vj, sendo c a 
velocidade de conexão} 
 
 Descrição da técnica para resolução: 
A solução consiste em encontrar um caminho de custo mínimo entre dois pontos (vértices) – 
algoritmo de custo mínimo. Considerando que, quanto maior a velocidade do link e quanto 
menos congestionado estiver, menor o custo (da aresta). 
 
PROBLEMA 13: da Carga Pesada 
 
 Descrição do problema: Um dos maiores problemas no transporte de cargas pesadas por 
rodovias é a altura dos viadutos, pois muitas vezes a carga é mais alta do que o vão do viaduto 
sob o qual o caminhão deve passar. Considere o mapa abaixo. É possível transportar uma 
turbina de hidroelétrica, que em cima do caminhão mede 7 metros de altura, da cidade Xis da 
Serra para a cidade Ypsilon Bonito? 
 
 
 
 
 
 
 
Neste caso é fácil perceber que a resposta é sim, pois o menor vão encontrado no caminho, se 
utilizarmos as estradas BR-1001 e BR-1024, é de 9 metros. No caso geral, com dezenas de 
cidades e estradas, a resposta pode não ser tão evidente. 
 
Conhecendo todas as estradas da região e a altura de todos os túneis e viadutos dessas estradas, 
e dado que temos uma carga de uma determinada altura, como se poderia determinar qual o 
melhor trajeto para levar a carga de um lugar para outro qualquer desta região? 
 
 Identificação dos vértices e arestas: A escolha do dígrafo utilizado na modelagem do problema 
é definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cidade} 
o E = {(vi,vj,h)} | há uma estrada entre as cidades vi e vj, sendo h a altura máxima 
permitida – aresta direcionada} 
 
Abaixo o dígrafo criado a partir desta definição: 
 Figura 16. Dígrafo representativo 
 
 Descrição da técnica para resolução: 
Trata-se de um dígrafo com arestas valoradas. A solução consiste em verificar se existe e 
encontrar o melhor trajeto (caminho) entre o ponto inicial e final, levando-se em conta a altura 
máxima permitida. 
 
PROBLEMA 14: da Ambulância 
 
 Descrição do problema: O município de Águas Molhadas é formado por várias vilas 
interligadas por igarapés. Os igarapés funcionam como sistema viário, já que a maioria dos 
habitantes usa barcos como meio de transporte. Os igarapés têm uma forte corrente, o que 
obriga os barcos a transitarem todos no mesmo sentido em cada igarapé (na verdade, é proibido 
o trânsito de barcos na contramão). A prefeitura do município mantém um único Posto de Saúde 
e um barco-ambulância (que em geral se encontra na vila onde está o Posto de Saúde) utilizado 
para transporte de doentes. 
 
O timoneiro do barco-ambulância está sempre com pressa, e tem medo de confundir-se no 
emaranhado de igarapés quando atende um chamado para buscar um doente em alguma vila. 
Por isso, ele deseja um esquema que lhe permita escolher a melhor alternativa para ir e voltar o 
mais rápido possível, ou seja, que passe pelo menor número de igarapés. 
 
Na região há sete vilas interligadas por onze igarapés, conforme figura que se segue. Como 
poderíamos auxiliar o timoneiro? 
 
 
 
 
 
 
 Identificação dos vértices e arestas: A escolha do dígrafo utilizado na modelagem do problema 
é definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma vila} 
o E = {(vi,vj) | há um igarapé interligando diretamente vi e vj, sendo a aresta direcionada} 
O Grafo, construído a partir dessas definições pode apresentar-se como: 
 
 Figura 17. Grafo representativo 
 
 Descrição da técnica para resolução: 
O problema consiste em encontrar um caminho de comprimento mínimo, dentre todos os 
caminhos que tem dois vértices como extremo, ou seja, na minimização do custo de travessia de 
um grafo entre dois vértices, dado pela soma dos valores de cada aresta percorrida. Neste caso, 
cada aresta terá o valor 1, e o objetivo é percorrer o menor número de arestas (igarapés) 
possível, considerando a direção de cada uma. 
 
o Exemplo: Uma solução interessante para minimizar o trajeto do timoneiro, de maneira 
geral, é encontrar a melhor vila para posicionar o Posto de saúde. A tabela abaixo 
contém os custos totais de ida e volta entre as vilas. 
 Tabela 1. Custos totais dos trajetos 
Verifica-se que um posto de saúde posicionado na vila 7, garantirá um menor custo de ida e 
volta total para os trajetos do timoneiro. 
 
PROBLEMA 15: dos canibais e dos missionários 
 
 Descrição do problema: Três canibais e três missionários estão viajando juntos e chegam a um 
rio. Eles desejam atravessar o rio, sendo que o único meio de transporte disponível é um barco 
que comporta no máximo duas pessoas. Há outra dificuldade: em nenhum momento o número 
de canibais pode ser superior ao número de missionários, pois desta forma os missionários 
estariam em grande perigo de vida. Como administrar a travessia do rio? 
 
 
 
 
 
 
 
 
 Identificação dos vértices e arestas: 
 
o A solução a seguir descrita foi adaptada de [MARIANI, 2010], que define que: 
o O primeiro passo para resolução do problema está na identificação de todos os estados 
que podem ocorrer em uma das margens, em relação ao número de canibais e número 
de missionários. Cada estado será representado por um par ordenado (c, m), onde c e m 
representam o número de canibais e missionários, respectivamente. Sendo 0 =< c <= 3 e 
0 =< m <= 3, tem-se 16 estados possíveis, de (0,0) à (3,3). 
 
o Porém, em função da restrição imposta pelo problema (em nenhum momento o número 
de canibais pode ser superior ao número de missionários), alguns destes estados não são 
viáveis. São eles: pares ordenados: (2,1), (3,1) e (3,2), assim como dos pares (1,2), (0,2) 
e (0,1), sendo que nestes últimos casos, a restrição se verifica na margem oposta, já que 
os canibais e missionários restantes (complemento em relação a (3,3)) estão lá. A tabela 
a seguir representa todos os estados, com X nos que não são viáveis. 
Tabela 2. Estados prováveis e viáveis 
 
o Desta forma, com o objetivo de permitir a representaçãode todos os estados viáveis, a 
escolha do grafo que pode ser utilizado na modelagem do problema é definida 
conforme abaixo: 
 
� G = (V, E), sendo: 
� V = {(c,m) | c e m representam o número de canibais e de missionários, 
respectivamente, numa das margens do rio, sendo que: 
• 0 =< c <= 3, 
• 0 =< m <= 3, 
• (m = c) ou (m = 0) ou (m = 3)} 
� E = {(e1,e2) | e1 = (c1,m1) é o estado da margem onde o barco está antes da 
travessia ser iniciada, e e2 = (c2,m2) é o estado da margem oposta após o barco 
completar a travessia, sendo que: 
• c2 >= 3-c1, 
• m2 >= 3-m1, (os números de canibais e de missionários da margem oposta não 
podem ser menor do que os números que haviam antes da travessia.) 
• 1<= | (m2 - (3-m1)) + (c2 - (3-c1)) | <= 2} (restringe o número de pessoas que 
podem ir no barco); 
 
 Descrição da técnica para resolução: A representação do grafo abaixo possui todas as possíveis 
transições entre os estados. Buscar uma solução neste grafo implica em procurar uma cadeia 
(uma seqüência qualquer de arestas adjacentes que ligam dois vértices) de tamanho impar que 
parta do vértice (3,3) (todos os canibais e os missionários estão numa margem) e que chegue 
novamente ao vértice (3,3) (todos os canibais e os missionários estão na outra margem). 
 
 Figura 18. Grafo representativo 
 
 
o Exemplo: Uma das possíveis soluções está representada nas figuras a seguir. 
 Figura 19. Possível 
Solução 
PROBLEMA 16: da fuga dos ladrões 
 
 Descrição do problema: Uma quadrilha de 3 ladrões assalta um banco e foge com uma mala de 
dinheiro para um aeroporto onde um avião pronto para decolar está à espera. O esconderijo é 
seguro, mas a fuga é difícil porque o avião só comporta 170kg. Só um dos ladrões sabe pilotar e 
ele pesa 60 kg. O segundo, que é o guarda-costas do chefe, pesa 100 kg e o chefe pesa 70 kg. O 
chefe teme que o piloto fuja com o dinheiro (que pesa 40 kg) se tiver uma oportunidade. O 
piloto tem a mesma preocupação em relação ao chefe. Apenas o guarda-costas merece a 
confiança de ambos. A quadrilha, no entanto, já elaborou um plano de fuga capaz de satisfazer a 
todos. Qual é esse plano? 
 
 Identificação dos vértices e arestas: 
 
o O primeiro passo para resolução do problema está na identificação de todos os estados 
que podem ocorrer em um dos locais (aeroporto ou esconderijo), em relação aos 
membros da quadrilha e o dinheiro. Cada estado será representado por: (P,G,C,D), 
onde P representa o piloto, G o guarda-costas, C o chefe e D o dinheiro. 
 
o Em função das restrições impostas, teríamos um número limitado de estados viáveis, 
dentre todos os possíveis, e estes serão representados no grafo da figura 20. 
 
o A escolha do grafo que pode ser utilizado na modelagem do problema é definida 
conforme abaixo: 
 
� G = (V, E), sendo: 
� V = {(P,G,C,D) | P, G, C e D representam os elementos (piloto, guarda-costas, 
chefe e dinheiro) em um dos locais em determinado momento, 1 se estão 
presentes e 0 se não estão sendo que: 
• (P = C) ou (G = 1) ou (D = 0)} 
� E = {(e1,e2) | e1 = (P1,G1,C1,D1) é o estado do local antes da travessia do avião, e 
e2 = (P2,G2,C2,D2) é o estado do local oposto, após o avião completar a 
travessia, sendo que: 
• |P| = 60 
• |G| = 100 
• |C| = 70 
• |D| = 40 
• 60 <= { |P|*(P2 - (1-P1)) + |G|*(G2 - (1-G1)) + |C|*(C2 - (1-C1)) + 
|D|*(D2 - (1-D1)) } <= 170 } - (restringe o peso total no avião, sendo que o peso mínimo é 
igual ao peso do piloto); 
 
 Descrição da técnica para resolução: Com base nas definições apresentadas, é possível criar o 
grafo abaixo, com as possibilidades viáveis e uma solução para o problema. 
o Exemplo: 
 
 
 
Figura 20. Grafo representativo e solução para o problema 
 
PROBLEMA 17: dos três maridos ciumentos 
 
 Descrição do problema: Três esposas e seus respectivos maridos desejam ir ao centro da cidade 
em um Corvette, o qual comporta apenas duas pessoas. Como eles poderiam deslocar-se até o 
centro considerando que nenhuma esposa deveria estar com um ou ambos os outros maridos a 
menos que seu marido também esteja presente? 
 
 Identificação dos vértices e arestas: 
 
o O primeiro passo para resolução do problema está na identificação de todos os estados 
que podem ocorrer em um dos lados da cidade, em relação ao número de maridos e 
esposas. Cada estado será representado por um par ordenado (h, m), onde h e m 
representam o número de homens e mulheres, respectivamente. Sendo 0 =< h <= 3 e 0 
=< m <= 3, tem-se 16 estados possíveis, de (0,0) à (3,3). 
 
o Porém, em função da restrição imposta pelo problema (nenhuma esposa deveria estar 
com um ou ambos os outros maridos a menos que seu marido também esteja presente), 
alguns destes estados não são viáveis. São eles: pares ordenados: (2,3), (1,3) e (1,2), 
assim como dos pares (2,1), (2,0) e (1,0), sendo que nestes últimos casos, a restrição se 
verifica no lado oposto, já que os homens e mulheres restantes (complemento em 
relação a (3,3)) estão lá. A tabela a seguir representa todos os estados, com um X nos 
que não são viáveis. 
 
 Tabela 3. Estados prováveis e viáveis 
o Desta forma, com o objetivo de permitir a representação de todos os estados viáveis, a 
escolha do grafo que pode ser utilizado na modelagem do problema é definida 
conforme abaixo: 
 
� G = (V, E), sendo: 
� V = {(h,m) | h e m representam o número de homens e de mulheres, 
respectivamente, em um dos lados da cidade, sendo que: 
• 0 =< h <= 3, 
• 0 =< m <= 3, 
• (m = h) ou (h = 0) ou (h = 3)} 
� E = {(e1,e2) | e1 = (h1,m1) é o estado do lado onde o carro está antes da travessia 
ser iniciada, e e2 = (h2,m2) é o estado do lado oposto após o carro completar a 
travessia, sendo que: 
• h2 >= 3-h1, 
• m2 >= 3-m1, (os números de homens e de mulheres no lado oposto não podem ser 
menor do que os números que haviam antes da travessia.) 
• 1<= | (m2 - (3-m1)) + (h2 - (3-h1)) | <= 2} (restringe o número de pessoas que 
podem ir no carro); 
 
 Descrição da técnica para resolução: A representação do grafo abaixo possui todas as possíveis 
transições entre os estados. Buscar uma solução neste grafo implica em procurar uma cadeia 
(uma seqüência qualquer de arestas adjacentes que ligam dois vértices) de tamanho ímpar que 
parta do vértice (3,3) (todos os maridos e esposas estão em um lado) e que chegue novamente 
ao vértice (3,3) (todos os maridos e esposas estão no centro). 
 
 Figura 21. Grafo representativo 
 
o Exemplo: Uma das possíveis soluções está representada nas figuras abaixo. 
 
 
Figura 22. Possível solução 
 
PROBLEMA 18: dos potes de vinho 
 
 Descrição do problema: Considere que temos três potes com capacidades de 8, 5 e 3 litros, 
respectivamente, os quais não possuem qualquer marcação. O maior deles está completamente 
cheio enquanto que os outros dois estão vazios. Estamos interessados em dividir o vinho em 
duas porções iguais de 4 litros, tarefa esta que pode ser realizada por transvasos sucessivos de 
um vaso no outro. Qual o menor número de transvasos necessários para completar a divisão? 
 
 Identificação dos vértices e arestas: A solução a seguir descrita foi adaptada de [MARIANI, 
2010], que define que: sejam c1 = 8, c2 = 5 e c3 = 3 respectivamente as capacidades dos três 
potes p1, p2 e p3. Então, um possível modelo para este problema é definir o grafo G (V,E) como: 
 
o V = {(q1, q2, q3) | q1, q2 e q3 representam as quantidades de vinho dos três potes, sendo 
que: 
� 0 =< q1 <= c1, 
� 0 =< q2 <= c2, 
� 0 =< q3 <= c3, 
� q1 + q2 + q3 = 8} 
 
o E = {(e1,e2) | o estado e2 é alcançado partindo-se do estado e1 por meio de um único 
transvaso de um pote para outro. O transvaso é completado quando o pote de origem é 
esvaziado ou quando o pote de destino é enchido} 
 
 Descriçãoda técnica para resolução: 
o Sejam px e py respectivamente os pote de origem e de destino do transvaso. Segundo o 
descrito na definição das arestas acima, um transvaso é possível se o pote de origem não 
estiver vazio (qx > 0) e o pote de destino não estiver cheio (qy < cy). A quantidade a ser 
transvasada é dada pelo mínimo entre o que tem no pote de origem (qx) e o que ainda 
cabe no pote de destino (cy-qy). Como resultado de um transvaso, a quantidade do pote 
px é decrescida em t unidades, enquanto que a quantidade do pote py é acrescida de t 
unidades. Abaixo um grafo com todos os estados viáveis: 
 Figura 23. Grafo representativo 
 
o Exemplo: A partir da representação anterior, verifica-se que o caminho de menor custo 
(menos transvasos) entre (8,0,0) e (4,4,0) é o apresentado na figura abaixo. 
 Figura 24. Solução de menor custo 
 
 
PROBLEMA 19: Um concerto com U2 
 
 Descrição do problema: A banda U2 tem um concerto que começa daqui a 17 minutos e todos 
precisam cruzar a ponte para chegar lá. Todos os 4 participantes estão do mesmo lado da ponte. 
Você deve ajudá-los a passar de um lado para o outro. É noite. Na ponte só pode passar no 
máximo duas pessoas de cada vez. Só há uma lanterna. Qualquer pessoa que passe, uma ou 
duas, deve passar com a lanterna na mão. A lanterna deve ser levada de um lado para o outro, e 
não pode ser jogada, etc. Cada membro da banda tem um tempo diferente para passar de um 
lado para o outro. O par deve andar junto no tempo do menos veloz: 
o Bono:- 1 minuto para passar 
o Edge:- 2 minutos para passar 
o Adam:- 5 minutos para passar 
o Larry:-10 minutos para passar 
 
Por exemplo: se o Bono e o Larry passarem juntos, vai demorar 10 minutos para eles chegarem 
do outro lado. Se o Larry retornar com a lanterna, 20 minutos terão passados e o show sofrerá 
um atraso. Como organizar a travessia? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {(a1,b1) | representam as duas pessoas que irão atravessar} 
o E = {(e1,e2,t) | e1 = (a1,b1) são as pessoas que realizaram a travessia, e e2 = (a2,b2) 
pessoas que podem realizar a próxima travessia, dependente da anterior. A aresta será 
valorada pelo tempo da travessia t} 
 Descrição da técnica para resolução: 
Para este problema é criado um grafo acíclico, representando uma seqüência de atividades 
possíveis, com suas respectivas durações. As arestas representam uma relação de precedência 
(uma aresta de e1 para e2 significa que a atividade em e1 só pode ser iniciada após a conclusão 
da em e2). 
Desta forma, a solução consiste em encontrar o menor tempo de conclusão da seqüência de 
atividades. Uma possível solução seria: 
o Primeiro passa o Bono e o Edge - 2 minutos; 
o Volta o Bono - 1 minuto; 
o Passa o Adam e o Larry – 10 minutos; 
o Volta o Edge - 2 minutos; 
o Por fim passam Bono e Edge novamente - 2 minutos (Total: 17 minutos) 
 
PROBLEMA 20: dos dissidentes políticos 
 
 Descrição do problema: A figura abaixo apresenta o diagrama de uma prisão para dissidentes 
políticos. Os prisioneiros estão divididos em várias celas como mostrado. Um espião planeja 
ajudá-los a escapar explodindo os portões das paredes da prisão. Dado o risco do plano, ele 
deseja destruir o menor número possível de portões e ainda assim garantir que todos os 
prisioneiros escapem. Quantos portões devem ser explodidos? Como poderia um problema mais 
geral ser resolvido? 
 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cela ou área exterior (R)} 
o E = {(vi,vj)} | vi esta ligado a vj por um portão} 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
 Figura 25. Grafo representativo 
 
 Descrição da técnica para resolução: 
 
Para encontrar a solução para o problema, é preciso entender, primeiramente o conceito de 
árvore geradora. Chama-se árvore todo o grafo que é conexo e que é minimal com essa 
propriedade, ou seja, se retirarmos uma aresta qualquer, destruímos a conexão. Uma árvore 
também pode ser conceituada como um grafo G conexo e sem ciclos. Uma árvore T diz-se 
árvore geradora de um grafo G se T é um subgrafo abrangente de G (e contém todos os vértices 
de G). 
Para encontrarmos uma árvore geradora em um grafo, executamos os seguintes passos: 
o Se G não contém nenhum circuito ele já é a sua própria árvore geradora; 
o Suponhamos agora que ele contém um circuito, tirando uma aresta desse circuito resulta 
um grafo ainda conexo; 
o Continuando assim até que não tenha nenhum circuito, o grafo obtido é um grafo 
conexo, que é uma árvore. 
Será encontrada a árvore geradora do grafo representado anteriormente, que é a solução para o 
problema, já que encontraremos um caminho minimal entre todos os vértices, ou seja, 
destruindo o menor número de portões. 
o Exemplo: Abaixo uma representação da solução 
 
 Figura 26. Solução 
 
PROBLEMA 21: da construção da ferrovia 
 
 Descrição do problema: Considere que a RFFSA deseje construir uma malha férrea que conecte 
um conjunto das cidades de nosso Estado. Assuma que a RFFSA efetuou um levantamento 
prévio sobre os custos de construção de cada segmento da malha entre duas cidades. Dada a 
situação econômica do Estado, ela deseja construir a malha de forma tão barata quanto possível, 
independentemente de quão inconveniente ela possa ser. A questão é: que malha deveria ser 
construída? 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma cidade} 
o E = {(vi,vj, c)} | vi e vj є V | vi e vj possuem um segmento da malha férrea entre si, que 
pode ser construído com um custo c} 
 Descrição da técnica para resolução: 
Tendo em vista o que o custo de construção de cada malha está representado pelo valor das 
arestas, a solução consiste em encontrar uma árvore geradora do grafo de custo mínimo, que 
ligue todos os vértices do grafo. 
o Exemplo: A mesma solução utilizada para o problema dos conspiradores políticos, a 
seguir, e para a instalação da rede elétrica do problema 24 pode ser aplicada para este 
caso. 
 
PROBLEMA 22: dos conspiradores políticos 
 
 Descrição do problema: Os agentes A, B, C, D, E, F, G e H são conspiradores políticos. De 
forma a coordenar seus esforços, é vital que cada agente seja capaz de comunicar-se direta ou 
indiretamente com todos os outros conspiradores. Esta comunicação, contudo, envolve um certo 
risco para cada um. Os fatores de risco associados à comunicação direta entre cada par de 
conspiradores é dado por: 
 
A A A A A B B C C C C D D E 
B C E F G C F D F G H E H H 
9 3 8 3 4 10 6 6 4 5 7 6 3 5 
Todas as outras comunicações diretas são impraticáveis, pois exporiam todos os esquemas de 
disfarce. Qual é o menor risco total envolvido neste sistema de conexão, ou seja, o menor risco 
para que uma mensagem seja repassada para todos os conspiradores? 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um agente conspirador político} 
o E = {(vi,vj, r)} | vi é capaz de comunicar-se diretamente com vj, com um risco r} 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 Figura 27. Grafo representativo 
 Descrição da técnica para resolução: 
o Para se obter o menor risco total neste sistema, devemos encontrar um grafo de custo 
global mínimo, que será uma árvore geradora de custo mínimo, onde todos podem se 
comunicar com todos. 
o Um algoritmo para realizar a tarefa acima,pode ser elaborado como: Suponha que o 
grafo G possua n vértices. A etapa inicial é formada por uma floresta com n árvores 
triviais (um só vértice cada), o que significa ET = [ ] (conjunto de arestas da árvore 
geradora está vazio). A cada etapa, a aresta de menor peso que une duas árvores, sem 
formar ciclos, é inserida em ET. O processo termina quando todas as árvores forem 
fundidas em uma só com n-1 arestas. 
 
o Exemplo: Abaixo cada um dos passos do algoritmo acima descrito: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 28. Solução – Passo a passo 
 
o Abaixo a solução final de menor custo, com risco total igual a 30. 
 Figura 29. Solução – árvore Geradora de custo mínimo 
 
PROBLEMA 23: Rede ótica entre tabas 
 
 Descrição do problema: Os caciques da região de Tutuaçu pretendem integrar suas tribos à 
chamada “aldeia global”. A primeira providência foi a distribuição de telefones celulares a 
todos os pajés. Agora, planejam montar uma rede de fibra ótica interligando todas as tabas. Esta 
empreitada requer que sejam abertas novas picadas na mata, passando por reservas de flora e 
fauna. Conscientes da necessidade de preservar o máximo possível o meio ambiente, os 
caciques encomendaram um estudo do impacto ambiental do projeto. Será que você consegue 
ajudá-los a projetar a rede de fibra ótica? 
 
Vamos denominar uma ligação de fibra ótica entre duas tabas de um ramo de rede. Para 
possibilitar a comunicação entre todas as tabas é necessário que todas elas estejam interligadas, 
direta (utilizando um ramo de rede) ou indiretamente (utilizando mais de um ramo). Os caciques 
conseguiram a informação do impacto ambiental que causará a construção dos ramos. Alguns 
ramos, no entanto, nem foram considerados no estudo ambiental, pois sua construção é 
impossível. Como determinar quais ramos devem ser construídos, de forma a possibilitar a 
comunicação entre todas as tabas, causando o menor impacto ambiental possível. 
A figura que se segue apresenta os ramos possíveis da rede, juntamente com o menor custo 
ambiental associado às interligações das tabas. 
 
 
 
Como se poderia determinar quais ramos devem ser construídos, de forma a possibilitar a 
comunicação entre todas as tabas, causando o menor impacto ambiental possível. 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é uma taba} 
o E = {(vi,vj, i)} | vi é capaz de comunicar-se, por um ramo de rede, diretamente com vj, 
com um impacto ambiental i} 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
 Figura 30. Grafo representativo 
 Descrição da técnica para resolução: 
A solução consiste em encontrar uma árvore geradora de custo mínimo no grafo. Abaixo uma 
representação da solução. 
 
 Figura 31. Solução 
 
 
PROBLEMA 24: da instalação de rede elétrica 
 
 Descrição do problema: A tabela abaixo mostra as possibilidades de instalação de seções de 
rede elétrica em um loteamento de sítios (o custo é dado em unidades de R$1000). A rede 
principal, a partir da qual o loteamento será abastecido, passa em frente ao sítio a. 
 
um sítio a a a b b c c d d d e e f g g h i 
outro sítio b c d d e d f f g h g i h h i j j 
custo 7 5 5,5 7,5 8 6 6,5 5,5 3,5 6,5 4 5 5 5 5 7,5 5,5 
Agora, examine a seguinte situação: a empresa responsável pelo loteamento não se obriga, por 
contrato, a instalar a rede elétrica enquanto pelo menos 80% dos sítios não forem vendidos; até 
o momento, apenas a e j encontraram comprador e o proprietário deste último, pessoa influente, 
pressiona a empresa para que esta leve, imediatamente, energia até o seu sítio. Esta, por seu 
lado, não julga conveniente aproveitar a ocasião para estender a instalação aos demais sítios. 
a) Você é consultado pela empresa, que deseja saber como atender ao proprietário influente da 
forma mais econômica, ou seja, determinar que seções da rede devem ser construídas de modo a 
levar energia ao sítio j, sem se preocupar com os sítios pelos quais o itinerário escolhido não 
passar; 
b) A empresa lhe pede, ainda, que planeje uma rede geral que abasteça todos os sítios, a qual 
tenha o custo mais baixo possível, levando-se em conta que a linha de a para j já foi instalada; 
c) Enfim, a empresa deseja saber se teve prejuízo ao atender à exigência, de modo a poder, 
eventualmente, compensá-lo ao vender os sítios restantes. 
 
 Identificação dos vértices e arestas: A escolha do grafo utilizado na modelagem do problema é 
definida conforme abaixo: 
 
o G = (V, E), sendo: 
o V = {v | v é um sítio} 
o E = {(vi,vj, c)} | vi e vj є V | vi e vj possuem seções de rede elétrica entre si, que podem 
ser instaladas com um custo c} 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
Figura 32. Grafo representativo 
 
 Descrição da técnica para resolução: 
Questão a) Para atender ao proprietário influente da forma mais econômica é necessário criar 
um caminho de custo mínimo que ligue o sítio a ao j. Por exemplo: ADHJ e ADGIJ = 19,5 são 
boas opções. O caminho pode ser encontrado aplicando-se, por exemplo, o algoritmo de 
Dijkstra. Abaixo um grafo com um destes caminhos. 
 Figura 33. Solução questão a. 
Questão b) Para criar uma rede geral, levando-se em conta a linha já instalada de a até j, é 
preciso criar uma árvore de custo mínimo, a partir da linha já instalada no item (a). Ou seja, 
acaba sendo mais interessante no item anterior escolher o caminho ADGIJ, pois passa por mais 
sítios e acaba deixando mais opções de escolha na formação da árvore. Abaixo uma solução 
com custo total de R$ 45.500,00 
 
 Figura 34. Solução questão b – Rede Geral. 
 
Questão c) Para a empresa saber se teve, e qual o prejuízo, é necessário fazer a diferença entre: 
a árvore de custo mínimo criada independente da exigência do proprietário influente e a árvore 
criada no item (b) com a exigência. 
 Criando-se a árvore independente da exigência do usuário, o custo fica o mesmo da 
anterior, não acarretando prejuízo para empresa. É importante destacar, porém, que se a escolha 
do item a fosse pelo caminho ADHJ, a empresa teria prejuízo ao instalar a rede geral. 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
MARIANI, Antônio Carlos. Teoria dos Grafos. Disponível em: <http://www.inf.ufsc.br/ 
grafos/livro.html>. Acessado em: 11/04/2010. 
 
LELLIS, Filipe Hoss & HEBEDA, Stephan. Implementação de uma Solução para o 
problema do Robô-Café. 22 de novembro de 2008. Disponível em: 
<http://www.inf.ufsc.br/~filipehl/>. Acessado em: 13/04/2010.