Trabalho 03

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARÁ
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO - PPGCC
Teoria da Computação: Grafos
Prof. Francisco Edson Rocha
Problemas de Grafos
Alunos.: 
Emanuel Maués da Costa Tavares
Elton Sarmanho Siqueira
Belém, 2010
Sumário
Sumário ........................................................................................................................................ 2 
Introdução ............................................................................................................................ 3 
Objetivo ................................................................................................................................ 4 
Desenvolvimento .................................................................................................................. 5 
Conclusão ........................................................................................................................... 13 
Referência Bibliográfica ...................................................................................................... 14 
Introdução
Este trabalho tem propósito de mostrar possíveis resoluções de problemas da 
Matéria de Grafos, Lecionada pelo professor Francisco Edson, na disciplina Teoria de 
Grafos, realizada no mestrado da universidade federal do Pará. Vale ressaltar que as 
resoluções destes problemas são baseadas nas aulas do professor e também em suas 
bibliografias citadas pelo mesmo, trazendo um maior embasamento teórico para a 
resolução dos problemas. Tais problemas levam um nível de complexidade na forma 
crescente, onde, ao avançar das questões, percebe-se que ocorre um aumento no nível de 
complexidade das questões.
As questões citadas anteriormente podem ser encontradas em 
http://www.inf.ufsc.br/grafos/problemas/index.htm, criadas pelo professor Antonio 
Carlos Mariane. Tais questões envolvem desde os conceitos básicos, passando por 
caminhos Eulerianos, calculo de distancia, caminhos Hamiltonianos, travessias e outros.
Por fim, este humilde trabalho, tentará mostrar resoluções com embasamento 
matemático, no qual facilite a leitura de alunos interessados na resolução destes 
problemas, para que o mesmo possa ter a possibilidade de melhorar as questões, usando 
outras técnicas, ou até comparando sua resolução com a que se apresenta neste trabalho.
Objetivo
Objetivo deste trabalho é mostrar resoluções dos vinte quatro questões que 
envolvem grafos, no qual a resposta envolverá a identificação dos vértices, arestas, 
descrição da técnica de grafos a ser usada para resolver o problema e dando um pequeno 
de exemplo de aplicação da técnica no problema que estiver sendo considerado.
Desenvolvimento
O trabalho proposto contém 24 a questões a serem apresentadas, as quais serão 
discutidas, segundo o objetivo do trabalho, da seguinte maneira: Nome do problema, 
vértice, aresta, Técnica e Solução. Logo abaixo, será mostrado a resoluções dos 
problemas.
1) Dos Polígonos
a. Vértice: v ϵ V | v são os círculos que possuem rótulos internos
b. Aresta: e ϵ E | e são as linhas que possuem operações matemáticas com os 
pesos.
c. Técnica: Usar lista de adjacência 
d. Solução: Se baseia em guarda no vetor das arestas o operando matemático, o 
vetor de vértice os valores. Em seguida, no vetor de incidência armazenar as 
referências dos vértices adjacentes. Por fim, fazer um algoritmo que consiga 
mapear a estrutura antes e após a remoção de aresta, conseguindo realizar as 
operações conforme o problema.
2) Das pontes de Königsberg
a. Vértice: v ϵ V | v são as ilhas. 
b. Aresta: e ϵ E | e são as pontes que interligam as ilhas.
c. Técnica: Ciclo de Euler
d. Solução: Não. Como os graus de todos os vértices são impares, é fácil 
verificar que este grafo não apresenta um ciclo Euleriano, visto que ele 
não satisfaz o teorema de Euler, nem tampouco é um grafo atravessável. 
Logo, a travessia proposta não é possível.
3) Do Caixeiro Viajante 
a. Vértice: v ϵ V | v são as cidades. 
b. Aresta: e ϵ E | e são os caminhos que interligam as cidades.
c. Técnica: Ciclo de Hamiltoniano.
d. Solução: Sim, é possível. Mas para que isso aconteça, cada cidade deve 
possuir n/2 passagens rodoviárias, onde n é o numero de cidades que será 
percorrido pelo viajante.
4) Do desenho da casa
a. Vértice: v ϵ V | v os pontos vermelhos assinalados pelo desenho. 
b. Aresta: e ϵ E | e são as linhas pretas que interligam os pontos vermelhos.
c. Técnica: Caminho de Euler
d. Solução: Sim, é possível. Como existem dois vértices com grau impar (de 
acordo com o teorema que reproduz o caminho de Euler), ocorre à 
possibilidade de desenhar a casa segundo os critérios que problema 
impõe.
5) Do assassinato do bilionário Count Van Diamond 
a. Vértice: v ϵ V | v os cômodos da casa. 
b. Aresta: e ϵ E | e são as portas que interligam os cômodos.
c. Técnica: Caminho e circuito de Euler
d. Solução: De acordo com o teorema do caminho de Euler (onde no máximo dois 
no vértices possuem grau impar), o jardineiro está falando a verdade, já o 
mordomo, está mentido, pois de acordo com o teorema para ciclo de Euler, não 
ocorre à possibilidade de o jardineiro parar no mesmo ponto inicial, logo 
ele é suspeito.
6) Do passeio do cavalo a Xadrez 
a. Vértice: v ϵ V | v são as casas da mesa. 
b. Aresta: e (vi,vj) ϵ E | e é o movimento do cavalo.
c. Técnica: Ciclo Hamiltoniano.
d. Solução: Não. De acordo com teorema ciclo hamiltoniano, onde cada 
vértice deve ter grau menor que a metade do numero de vértices 
existentes, o movimento do cavalo não poderá retorna na casa inicial 
devido a este motivo descrito anteriormente.
7) Da pavimentação de estradas 
a. Vértice: v ϵ V | v são as cidades. 
b. Aresta: e (vi,vj) ϵ E | e são as estradas que interligam as diversas cidades.
c. Técnica: Ciclo Euler.
d. Solução: Não. Pois como se trata de um circuito de Euler, não obedece ao 
teorema, pois cada vértice deveria ter grau par para poder terminar 
Santana. Já segunda pergunta, também consiste em resposta negativa, 
pois a cidade oito possui grau impar, cujo homem não seria sendo 
sincero.
8) Da coleta de correspondência 
a. Vértice: v ϵ V | v são os postos de coleta. 
b. Aresta: e (vi,vj) ϵ E | e são as rotas entre os postos de coleta.
c. Técnica: Caminho de Euler e Hamiltoniano.
d. Solução: Modelaria através de um grafo, em que a melhor rota seria aquela que 
possibilite passar pelos os postos de coleta e sem repetir o trecho percorrido 
pelos mesmos. Por fim, toda essa analise deve estar voltada para o tamanho da 
distancia que motorista possa percorrer, para que o mesmo não gaste tanta 
gasolina.
9) Do robô-café 
a. Vértice: v ϵ V | v são as salas. 
b. Aresta: e (vi,vj) ϵ E | e são as portas que interligam as salas.
c. Técnica: Matriz de adjacência.
d. Solução: Realizar uma matriz entre assalas e suas portas, assim, 
implementando no robô um processo de mapeamento, onde ele passa 
saber quais as salas já visitadas e quais ainda não foram visitadas. 
Também através da matriz, conseguiria evitar excessivas visitas nas 
salas, na qual contaria com um contador.
10) Problema do caminho do custo mínimo 
a. Vértice: v ϵ V | v são as cidades. 
b. Aresta: e (vi,vj) ϵ E | e são as estradas que interligam as cidades.
c. Técnica: Algoritmo de Dijkstra.
d. Solução: Consiste em usar um grafo valorado e usar o algoritmo de Dijkstra, 
para que consiga encontrar a menor distancia entre dois pontos.
11) Do metrô 
a. Vértice: v ϵ V | v são as Estações. 
b. Aresta: e (vi,vj) ϵ E | e são as rotas entre as estações.
c. Técnica: Árvore.
d. Solução: A solução Consiste em determina a raiz e projetar uma árvore através 
dos possíveis caminhos nos quais, possibilitam chegar ao destino. Depois 
verificar qual o caminho tem menor numero de nodos.
12)RNP 
a. Vértice: v ϵ V | v são os POP. 
b. Aresta: e (vi,vj) ϵ E | e são as rotas entre os POP.
c. Técnica: Algoritmo de custo mínimo.
d. Solução: Considerando a rota apropriada como a menor distância, ou seja, 
então se considera o ponto desejável como raiz e calcular a distância para 
os outros pontos, plotando quais os pontos visitados pela rota calculada, 
assim, verificando através da distância a rota apropriada.
13)Da carga pesada 
a. Vértice: v ϵ V | v são as cidades. 
b. Aresta: e (rodovia, viaduto) ϵ E | e são os viadutos.
c. Técnica: Dígrafo com Lista de adjacência.
d. Solução: Neste caso, realizaria armazenamento o nome da rodovia e o valor da 
altura do viaduto como aresta. Assim, quando determinar ponto inicial e 
destino, realizaria um algoritmo que manipula as informações na aresta, na qual 
visualiza-se o melhor trajeto, levando em conta o sentido e o tamanho do 
viaduto .
14)Da ambulância 
a. Vértice: v ϵ V | v são as Regiões. 
b. Aresta: e (vi,vj) ϵ E | e são os rios.
c. Técnica: Redução transitiva.
d. Solução: podem-se remover as trajetórias equivalentes do ponto inicial e 
destino, deixando somente a trajetória mais favorável tanto na ida como na 
volta.
15) Dos canibais e missionários 
a. Vértice: v ϵ V | v é o par canibal e missionário. 
b. Aresta: e (ei,ej) ϵ E | onde ei (ci,mi) é o estado da margem antes de completar a 
travessia. Já o ej (cj, mj) é o estado da margem oposto, após o barco completar 
a travessia. Sendo que: 
cj ≥ 3 – ci
mj ≥ 3 – mi, logo
1 ≤ | mj – (3-mi) + (cj – (3-mi)) | ≤ 2
c. Técnica: Busca em profundidade
d. Solução: As primeiras duas condições acima afirmam que após a travessia 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. Por sua vez, a terceira 
condição limita o número de pessoas que pode ir ao barco. Motivo pelo qual 
aparece o operador de módulo na terceira restrição é devido à relação ser 
simétrica. Por fim, o algoritmo analisaria as possíveis transições entre estados, 
segundo estas regras definidas.
16) Da fuga dos ladrões 
a. Vértice: v ϵ V | v são o par pessoa(s) e massa corpórea. 
b. Aresta: e (ei, ev) ϵ E | onde ei (piloto+p, xi) significa estado de ida do 
transporte e ev (piloto+p, xv) estado de volta do mesmo. Onde o piloto deve ser 
sempre estar presente no transporte de ida e de volta, os elementos xi e xv são 
as massas carregadas no transporte de ida ou de volta e p são os elementos 
transportados.
c. Técnica: Algoritmo Busca de Profundidade.
d. Solução: Primeiro deve ser definido algumas regras, como:
Piloto + p ≤ 170
p ≤ 110
Onde p, não pode ser maior que 110 kg. Outra regra é que dinheiro não 
pode estar somente com o piloto ou somente com chefe, logo temos 
matematicamente:
(Piloto+ Guarda Costa + Dinheiro, 200) e (Piloto+dinheiro, 100)
Portanto, o algoritmo conseguirá realizar uma combinação através desta 
base regras, onde uma possível combinação é mostrada logo abaixo:
(Piloto+Chefe+Dinheiro, 170)i, (Piloto+Chefe, 130)v, (Piloto+GC, 160)i 
e (Piloto+ Chefe, 130)v. Na ordem de transporte, onde os índices i e v são 
respectivamente ida e volta.
17) Dos três maridos ciumentos 
a. Vértice: (m,o) ϵ V | m e o representam o par marido e a esposa . 
b. Aresta: e (ei,ev) ϵ E | onde ei (mi,oi) é o estado da trajetória de ida e ev (mv,ov) 
é o estado da trajetória de volta.
c. Técnica: Algoritmo Busca de Profundidade.
d. Solução:
Como regra geral, temos:
mi = m ou mi = 0 ou mv = m ou mv = 0
 e
 oi = o ou oi = 0 ou ov = o ou ov = 0
Logo, os índices para situações válidas (onde uma mulher deve estar com 
seu respectivo marido) têm a restrição:
 { i ϵ Z*, j ϵ Z* / i = j}
Então, inferimos a elaboração de um dígrafo, onde ponto inicial é ponto 
final deve ser igual, assim, tornando este grafo um ciclo. Vale ressaltar, 
que duas mulheres podem estar juntas e, valido também para homens. De 
tal forma, que no Corvette pode ter no máximo duas pessoas. Por fim, 
considera-se que nenhuma esposa deve estar com um ou ambos os 
outros maridos a menos que seu marido também esteja presente. Com 
isso, temos a base de regra para que o algoritmo implemente 
satisfatoriamente a situação e obtendo o(s) estado(s) alcançável para 
representar este grafo. Temos uma possível seqüência, onde os i e v, são 
índices de ida e volta respectivamente: (m1, o1)i, (m1, 0)v, (m2, o2)i, 
(m2, 0)v, (m3, o3)i, (o2, o1)v, (m1, o1)i, (0, o1)v, (m2,o2)i, (m1, 0) e 
(m1, o1). 
18) Dos potes de vinho 
a. Vértice: (q1, q2, q3) ϵ V | v representam as quantidades de vinho dos três 
potes, sendo que:
0 ≤ q1 ≤ c1, sendo c1 = 8
0 ≤ q2 ≤ c1, sendo c2 = 5
0 ≤ q2 ≤ c1, sendo c3 = 3
 
b. Aresta: e (e1,e2) ϵ E | onde o estado e2 é alcançado partindo-se do estado e1 
por meio de um único transvaso de um pote para o outro, cujo o transvaso é 
completado quando o pote de origem é esvaziado ou quando o pote de destino é 
enchido.
c. Técnica: Algoritmo Busca de Profundidade
d. Solução: segundo a definição de aresta, 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 é dado pelo mínimo entre o que tem no pote 
de origem (qx) e o que ainda cabe no pote de destino (cy - qy). Sejam px e py 
respectivamente o pote de e destino, então tem-se como resultado de um 
transvaso, a quantidade do pote px é decrescida em t unidades, enquanto a 
quantidade do pote py é acrescida de t unidades. Logo, com o algoritmo de 
busca de profundidade, de acordo com as regras definidas anteriormente, 
podemos obter todos os estados alcançáveis partindo-se do estado inicial (8,0,0) 
para estado de destino. 
19)Um concerto com U2 
a. Vértice: (pessoas, tempo) ϵ V | são o par pessoa(s) e tempo percorrido. 
b. Aresta: e (ei,ev) ϵ E | onde ei é o estado de ida e ev é o estado de volta. 
c. Técnica: Caminho Crítico.
d. Solução: De acordo com o problema, o comprimento do caminho deve ser igual 
e possuindo a seguinte restrição:
{e ϵ E / Σ d(e) ≤ 17}
No qual este somatório com seguinte restrição representa o tempo para 
que não aconteça o atraso. Deve-se resolver este problema em que soma 
dos pesos das arestas não podem passar de 17, no qual é o tempo para 
que não aconteça o atraso, caso contrário, o show atrasará. Da seguinte 
maneira, deve-se realizar um algoritmo, que possa construir um grafo, 
onde par de pessoas deve andar junto no tempo do menos veloz, 
passando no máximo duas pessoas na ponte e não abandonando a 
lanterna.
20) Dos dissidentes políticos 
a. Vértice: v ϵ V | v são os portões nos quais são as interseções das linhas pretas 
que cobrem as paredes. 
b. Aresta: e (vi, vj) ϵ E | e são as linhasque cobrem a área verde.
c. Técnica: Redução de vértices.
d. Solução: neste caso, os portões da região oeste (a8, a7, a6 e a1) teria o portão no 
qual convergem as paredes da mesma, logo, este é o portão alvo para ser 
explodido. Já no lado leste (a10, a4, a3, a5) existe uma porção que abrirá 
brecha para essas áreas. Por fim, explodir o portão entre (a2, a4, a3) e a9 
para que todos possam sair com menor numero de explosões. Um bom 
exemplo de algoritmo que poderia dar essa resposta é Floyd Marshall, o 
qual visita todos os vértices e retorna o caminho mais curto em relação a 
todos eles.
21) Da construção da ferrovia
a. Vértice: v ϵ V | v são as cidades. 
b. Aresta: e (vi, vj) ϵ E | e são as estradas que interligam as cidades.
c. Técnica: Árvore.
d. Solução: matematicamente, a menor distancia entre dois pontos é a reta. Logo, 
a menor malhar rodoviária seria aquela que se se aproxima deste modelo 
matemático, assim, reduziria o tamanho da malha e proporcionalmente 
ao investimento de construção. Um bom exemplo de algoritmo que 
poderia dar essa resposta é Floyd Marshall, o qual visita todos os 
vértices e retorna a malha mais curta, em relação a todas as cidades.
22)Dos conspiradores políticos 
a. Vértice: v ϵ V | v são os agentes. 
b. Aresta: e (vi, vj) ϵ E | e é o fator de risco.
c. Técnica: Caminho Crítico e o comprimento do caminho.
d. Solução: Realizada a construção de um grafo na qual todos os agentes estejam 
se comunicando, após isso, ocorreria a construção de algoritmo que somasse os 
pesos que correspondem ao caminho que se caracteriza a comunicação entre os 
agentes. Por fim, verificaria a menor soma entre os pesos, assim, verificando a 
menor fator de risco entre todos os agentes.
23)Rede ótica entre tabas 
a. Vértice: v ϵ V | v são as tabas. 
b. Aresta: e (vi, vj) ϵ E | e é o ramo entre duas tabas, na qual possui um peso, 
chamado custo ambiental.
c. Técnica: Redução de aresta e lista de adjacência.
d. Solução: pelo método de tentativas, realizaria uma analise do grafo com todas 
as suas ligações e, assim, reduziria as arestas de acordo com condição de que 
todas as tabas estejam interligadas. Assim, o algoritmo, realizaria o calculo do 
menor impacto ambiental (usando a lista de adjacência para guarda os valores) 
e também a comunicação entre tabas.
24)Da instalação da rede elétrica 
a. Vértice: v ϵ V | v são os sítios. 
b. Aresta: e (vi, vj custo) ϵ E | Onde caminhos entre os sítios e o custo com 
instalação elétrica.
c. Técnica: redução de aresta, comprimento do caminho e lista de adjacência.
d. Solução: realizar algoritmo que possibilite por tentativa traçar o melhor 
caminho do vértice a à j, na qual viabilize o menor custo (soma dos pesos), em 
que o usaria a lista para manipular os dados. Neste caso, a solução seria ab, be, 
ei, ij. Já segunda pergunta, seria realizado um algoritmo que inclua as arestas, 
obedecendo ao critério de alcançabilidade e de menor custo. Por fim, caso a 
malha construída (na situação anterior) tiver um custo maior do que em relação 
de uma rede construída desde o inicio (no caso sem a rede de a à j construída), 
então não será um bom negócio, mas caso ao contrario, haverá lucro.
Conclusão
Portanto, observou que o estudo de grafos é algo importante, tanto para os 
alunos da área da computação como engenharia, matemática e áreas afins. Em que para 
diversas questões variadas, mostrou-se útil para resolver ou pelo mostrar como pode ser 
solucionada cada situação. Vale ressaltar, que tais questões podem ser resolvidas por 
outras técnicas que envolvam tanto gráfico ou como outro recurso teórico.
Referência Bibliográfica
MARIANI, A. C. Teoria de Grafos. Disponível em: <http://www.inf.ufsc.br/grafos/>. 
Acessado em: 10/04/2010.
SZWARCFITER, J. L. Grafos e algoritmos computacionais. Rio de Janeiro. 2 Ed. 
Campus, 1988.
	Sumário
	Introdução
	Objetivo
	Desenvolvimento
	Conclusão
	Referência Bibliográfica