Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
 
Exercícios: Grafos – Conceitos Básicos e Caminhamentos 
Nomes:		 ___________________________________________________	
	 ___________________________________________________	
	 ___________________________________________________	
01.	Considerando	o	grafo	abaixo,	assinale	as	alternativas	que	contem	características	deste	
grafo.	 (Uma	 ou	 mais	 alternativas	 podem	 ser	 assinaladas.	 Uma	 alternativa	 errada	 anula	 uma	
alternativa	certa)	
	
(						 )		 grafo	valorado	
(							)		 grafo	não	valorado	
(					 )		 grafo	orientado	
(					 )		 grafo	não	orientado		
(						 )		 grafo	não	possui	laços	
(						 )		 grafo	possui	laços	
(					 )		 grafo	conexo	
(						 )		 grafo	não	conexo		
(						 )		 grafo	completo	
(						 )		 grafo	não	completo	
(						 )		 grafo	não	possui	ciclos	
(						 )		 grafo	possui	ciclos	
(						 )		 as	cidades	Rondinha,	Estrela	e	Guaporé	formam	um	clique	
(			 )		 as	cidades	Estrela,	Guaporé,	Caxias	do	Sul	e	Porto	Alegre	formam	um	clique	
02.	 Um	 grafo	 de	 pré-requisitos	 entre	 disciplinas	 de	 um	 curso	 pode	 ser	 modelado	 da	
seguinte	forma:	cada	disciplina	é	um	vértice	do	grafo.	Se	uma	disciplina	é	origem	de	um	
arco,	significa	que	tem	como	pré-requisito	a	disciplina	no	destino	daquele	arco.	Desenhe	o	
grafo	formado	pelas	disciplinas	e	seus	pré-requisitos	da	tabela	abaixo.	(Sugestão:	utilize	o	
código	da	disciplina	para	desenhar	o	grafo).	
Código	 Disciplina	 Pré-requisitos	
INF01202	 Algoritmos	e	Programação	 	
LET02720		 Inglês	Instrumental	 	
INF01107		 Introdução	à	Arquitetura	de	computadores	 	
INF01108		 Arquitetura	e	Organização	de	Computadores	I	 INF01107		
INF01112		 Arquitetura	e	Organização	de	Computadores	II	 INF01108		
INF05008	 Fundamentos	de	Algoritmos	 	
INF01203	 Estruturas	de	Dados	 INF01202,	INF05008	
INF01124	 Classificação	e	Pesquisa	de	Dados	 INF01203	
INF01145		 Fundamentos	de	Bancos	de	Dados		 INF01124	
INF01120		 Técnicas	de	Construção	de	Programas	 INF01124	
	
	
	
	
	
	
	
	
	
	
	
	
b)	Faça	(graficamente)	a	matriz	de	adjacência	que	representa	o	grafo	desenhado	no	item	
(a).		
	
	
	
	
	
	
	
	
	
	
	
	
	
c)	Faça	(graficamente)	a	lista	de	adjacência	que	representa	o	grafo	desenhado	no	item	(a).		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
d)	 Liste	 os	 vértices	 do	 grafo	 em	 uma	 ordem	 que	 represente	 o	 caminhamento	 em	
profundidade	iniciando	no	vértice	INF01203.	
	
	
	
	
	
e)	Liste	os	vértices	do	grafo	em	uma	ordem	que	represente	o	caminhamento	em	largura	
iniciando	no	vértice	INF01203.	
	
	
	
	
	
f)	O	grafo	é	orientado?	Assinale	a	alternativa	correta.	
(				)	Sim			(				)	Não	
	
g)	O	grafo	é	valorado	(ponderado)?	Assinale	a	alternativa	correta.	
(				)	Sim			(				)	Não	
	
h)	O	grafo	possui	um	ou	mais	ciclos?	Assinale	a	alternativa	correta.	
(				)	Sim				(				)	Não	
	
i)	O	grafo	possui	um	ou	mais	laços?	Assinale	a	alternativa	correta.	
(				)	Sim				(				)	Não	
	
j)	O	grafo	é	conexo?	Assinale	a	alternativa	correta.	
(				)	Sim			(				)	Não	
03.	Você	 usaria	 uma	 lista	 de	 adjacência	 ou	 uma	matriz	 de	 adjacência	 em	 cada	 um	 dos	
casos	abaixo?	Justifique	sua	escolha.	
a) O	grafo	tem	10.000	vértices	e	20.000	arestas	e	é	importante	usar	tão	pouco	espaço	
quanto	possível.	
	
	
b) O	grafo	tem	10.000	vértices	e	200.000.000	arestas,	e	é	importante	usar	tão	pouco	
espaço	quanto	possível.	
	
	
c) O	 grafo	 tem	 10.000	 vértices	 90.000.000	 arestas,	 e	 é	 importante	 usar	 tão	 pouco	
espaço	quanto	possível.	
	
	
d) Você	 deve	 ter	 a	 aresta	 adjacente	 tão	 rápido	 quanto	 possível,	 sem	 se	 importar	
quanto	espaço	você	usa.	
	
	
04.	Um	 sistema	de	 computação	 possui	 uma	 senha	 de	 acesso	 para	 cada	 usuário	 que	 dá	
direito	 ao	 uso	 do	 sistema.	Um	usuário	 pode	dar	 a	 outro	 o	 direito	 de	 usar	 sua	 área	 (ou	
conta).	Se x puder usar a área de y e y puder usar a área de z, 
então x poderá usar a área de z. 	Assinale	 a	 alternativa	 que	 contem	 as	
propriedades	corretas	do	grafo	que	modela	o	problema	desta	questão:	
a)		orientado	/	não-valorado	/	pode	conter	ciclos	/	pode	conter	vértices	isolados		
b)		não-orientado	/	valorado	/	pode	conter	ciclos	/	não	pode	conter	vértices	isolados		
c)		orientado	/	valorado	/	não	pode	conter	ciclos	/	pode	conter	vértices	isolados		
d)		não-orientado	/	não-valorado	/	pode	conter	ciclos	/	não	pode	conter	vértices	isolados		
e)		orientado	/	não-valorado	/	não	pode	conter	ciclos	/	não	pode	conter	vértices	isolados		
	
05.	 Complete	 	 o	 texto	 a	 seguir	 usando	 as	 palavras	 que	 estão	 no	 quadro	 abaixo.	 Cada	
palavra	pode	ser	utilizada	uma	ou	mais	vezes,	sendo	que	cada	palavra	deve	ser	utilizada	
pelo	menos	uma	vez.		
adjacentes					aresta	 arestas								grafo	 incide	 	 pontas	 	 vértices	
Um	____________________	é	um	par	(V,A) em	que	V	é	um	conjunto	arbitrário	e	A	é	
um	 subconjunto	 de	V.	 Os	 elementos	 de	V	 são	 chamados	 ____________________	 e	 os	
elementos	de	A	são	chamados	____________________.			
	
Uma	____________________	como	{v,w}	será	denotada	simplesmente	por	vw ou	por	
wv	.	Dizemos	que	a	____________________	vw ____________________	em	v e	em	w	e	
que	 v e	 w	 são	 as	 ____________________	 da	 aresta.	 Se	 vw	 é	 uma	
____________________,	 diremos	 que	 os	 ____________________	 v	 e	 w são	
____________________.	
06.	Qual	é	a	economia	de	memória,	ao	se	substituir	a	matriz	de	adjacência	como	estrutura	
de	dados	de	um	grafo	orientado,	pela	lista	de	adjacência	para	cada	vértice.	
	
	
	
	
	
	
	
	
07.	 A	 mitologia	 grega	 fala	 de	 um	 labirinto	 construído	 para	 abrigar	 o	 monstruoso	
minotauro,	parte	homem	parte	touro.	Este	labirinto	era	tão	complexo	que	nenhum	animal	
ou	homem	podia	escapar	dele.	Até	que	o	herói	grego	Teseu,	com	a	ajuda	da	filha	do	rei,	
Ariadne,	 decidiu	 implementar	 um	 algoritmo.	 A	 lógica	 do	 algoritmo	 é	 a	 seguinte:	 Teseu	
amarrou	um	novelo	de	linha	na	porta	do	labirinto	e	o	desenrolou	à	medida	que	caminhava	
pelas	tortuosas	passagens	à	procura	do	monstro.	Evidentemente,	ele	sabia	sobre	o	bom	
projeto	de	algoritmos,	pois	após	encontrar	e	vencer	o	minotauro	ele	facilmente	seguiu	o	
fio	de	volta	à	porta	e	dos	braços	de	Ariadne.	Responda:	Qual	o	algoritmo	visto	em	aula	
que	resolve	o	problema	apresentado?	Justifique	sua	resposta.		
	
	
	
	
	
	
 
08.	Considere	os	 trecho	de	código	a	 seguir.	As	variáveis	num_ar	 e	num_v	 representam,	
respectivamente,	 o	 número	 de	 arestas	 e	 o	 número	 de	 vértices	 do	 grafo.	 	 Responda	 as	
perguntas	a	seguir.	
	
#define num_ar 7 
#define num_v 6 
 
void hein(int grafoin[num_v+1][num_v+1],int grafoout[num_v+1][num_ar+1]){ 
 int l,a,i,j; 
 a=1; 
 for(i=1;i<=num_v;i++) 
 for (j=1;j<=num_v;j++){ 
 if (grafoin[i][j]==1){ 
 grafoout[i][a]=-1; 
 grafoout[j][a]=1; 
 a++;}}} 
	
a)	O	que	faz	a	função	hein?	
	
	
	
	
	
b)	Qual	é	a	estrutura	de	representação	física	do	grafo	grafoin?	
	
___________________________________________	
	
c)	Qual	é	a	estrutura	de	representação	física	do	grafo	grafoout?	
	
___________________________________________	
	
	
d)	A	função	é	adequada	para	grafos	orientados,	não-orientados	ou	ambos?	
	
___________________________________________	
	
e)	A	função	é	adequada	para	grafos	valorados,	não-valorados	ou	ambos?	
	
___________________________________________	
	
09.	Considere	os	trecho	de	código	a	seguir.	
	
#define max 7 
 
int enigma (int grafo[max+1][max+1]) 
 { 
 int i,j,k; 
 
 for (i=1;i<=max;i++) 
 for (j=1;j<=max;j++) 
 { 
 if ((grafo[i][j]==1) && (grafo[j][i]==1) ) 
 for (k=1;k<=max;k++) 
 if (grafo[k][i]==1 && grafo[i][k]==1 && grafo[k][j]==1 ) 
 { 
 printf("achou enigma %d %d %d\n",i,j,k); 
 return 1; 
 } 
 } 
 return 0; 
 } 
	
	
a)	O	que	faz	a	função	enigma?	
	
	
	
	
b)	Qual	é	a	estrutura	de	representaçãofísica	do	grafo	grafo?	
	
___________________________________________	
	
c)	A	função	é	adequada	para	grafos	orientados,	não-orientados	ou	ambos?	
	
___________________________________________	
	
d)	A	função	é	adequada	para	grafos	valorados,	não-valorados	ou	ambos?	
	
___________________________________________	
	
10.	Considere	o	trecho	de	código	a	seguir.		
#define max 7 
void whatIsGoingOn(int grafo[max+1][max+1], int v) 
{ 
 int i, j, x; 
 for (i=1; i<= max; i++) 
 { 
 x = 0; 
 for (j=1; j<= max; j++) 
 x = x + grafo[i][j]; 
 printf("%d=%d\n", i, x); } } 
	
a)	O	que	faz	a	função	whatIsGoingOn?	
	
	
	
b)	Qual	é	a	estrutura	de	representação	física	do	grafo	grafo?	
	
___________________________________________	
c)	A	função	é	adequada	para	grafos	conexos,	não-conexos	ou	ambos?	
	
___________________________________________	
d)	A	função	é	adequada	para	grafos	valorados,	não-valorados	ou	ambos?	
	
___________________________________________