EX15-coloracao

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 
Profa. Renata Galante (galante@inf.ufrgs.br ) 
Exercícios sobre Coloração de Grafos 
Nomes:		 ___________________________________________________	
	 ___________________________________________________	
	 ___________________________________________________	
01.	Considere	o	grafo	da	figura	abaixo.	Qual	o	alternativa	representa,	respectivamente,	os	
conjuntos	 de	 vértices	 independentes	 máximo	 (CVIMs)	 e	 os	 conjuntos	 de	 vértices	 que	
formam	os	cliques	do	grafo.		
	
	
	
a)		CVIMs:	{B,C},	{B,Y},	{X,C},	{X,A,Y},	{A,	Z},	{A,Y}	
	 Cliques:	{X,B,Z},	{C,Y,Z},	{A,B},	{A,C}	
b)		CVIMs:	{B,C},	{B,Y},	{X,C},	{X,A},	{A,	Z},	{A,Y}	
	 Cliques:	{X,B,Z},	{C,Y,Z},	{A,B},	{A,C},	{X,Y,Z}	
c)		CVIMs:	{B,C},	{B,Y},	{X,C},	{X,A},	{A,	Z},	{A,Y}	
	 Cliques:	{X,B},	{C,Y,Z},	{A,B},	{A,C},	{X,Y,Z}	
d)		CVIMs:	{B,C},	{B,Y},	{X,C},	{X,A},	{A,	Z},	{A,Y}	
	 Cliques:	{X,B,Z},	{C,Y,Z},	{A,B,C,Z},	{X,Y,Z}	
e)		CVIMs:	{B,C},	{B,Y},	{X,C},	{X,Z},	{A,	Z},	{A,Y}	
	 Cliques:	{X,B,Z},	{C,Y,Z},	{A,B},	{A,C},	{X,Y,Z}	
	
02.	Desenhe	o	grafo	complemento	referente	ao	grafo	do	exercício	01.		
	
03.	Assinale	as	alternativas	que	contem	exemplos	de	problemas	que	podem	ser	resolvidos	
com	Número	Cromático	(Coloração	de	Vértices).	
	
(						 )		Os	professores	do	Instituto	de	Informática	da	UFRGS	estão	se	preparando	para	as	
apresentações	dos	 trabalhos	de	conclusão	da	CIC	e	da	ECP	que	 irão	ocorrer	em	 janeiro.	
Cada	professor	poderá	participar	de	diversas	bancas.	Uma	apresentação	de	 trabalho	de	
conclusão	 deverá	 ocorrer	 em	 um	 turno	 (manhã/tarde).	 Os	 professores	 estão	 tentando	
definir	 o	menor	número	de	 turnos	necessários	para	 realizar	 todas	 as	 apresentações,	 de	
forma	 que	 não	 haja	 conflitos	 entre	 os	 membros	 da	 banca	 (ou	 seja,	 de	 forma	 que	 um	
professor	 não	 seja	 colocado	 em	duas	 bancas	 acontecendo	 ao	mesmo	 tempo).	Qual	 é	 a	
alternativa	que	contém	o	algoritmo	correto	para	resolver	este	problema?	
	
(							 )	Caso	 o	 projeto	 para	 construção	 da	malha	 ferroviária	 da	 questão	 anterior	 tivesse	
sido	 aprovado	 há	 dois	 anos	 atrás	 em	 sua	 forma	 original,	 o	 orçamento	 previsto	 seria	
consideravelmente	maior.	O	 projeto	 ainda	previa	 conectar	 os	mesmos	 10	municípios,	 e	
para	cada	par	de	municípios,	poderia	 ser	possível	ou	não	uma	 ligação	direta	entre	eles.	
Porém	 o	 objetivo	 seria	 o	 de	 reduzir	 a	 distancia	 total	 percorrida	 partindo	 de	 qualquer	
município	para	Porto	Alegre.		
	
(							 )	Digamos	 que	 um	 grafo	G	 representa	 a	 planta	 de	 uma	 cidade:	 os	 vértices	 são	 as	
esquinas	 e	 as	 arestas	 são	 os	 trechos	 de	 ruas	 que	 ligam	 as	 esquinas.	 Um	 empresário	
decidiu	instalar	uma	rede	de	postos	de	gasolina	na	cidade.	Entretanto,	a	legislação	exige	
que	 cada	 posto	 fique	 em	 uma	 esquina	 e	 impede	 que	 dois	 postos	 fiquem	 em	 esquinas	
adjacentes.	O	empresário	deseja	saber	quantos	postos,	no	máximo,	será	possível	instalar	
na	cidade.		
	
(							 )	O	 problema	 de	 atribuição	 de	 frequência	 de	 rádio	 ocorre	 quando	 diferentes	
transmissores	de	rádio	que	operam	na	mesma	área	geográfica	interferem	entre	si	quando	
atribuídos	 a	 canais	 de	 frequência	 próximos.	 O	 objetivo	 é	 impedir	 que	 rádios	 que	 irão	
causar	interferência	sejam	atribuídas	frequências	próximas.		
	
(					 )	Um	 químico	 deseja	 embarcar	 os	 produtos	 A,	 B,	 C,	 D,	 E,	 F,	 X	 usando	 o	 menor	
número	de	containers.	Alguns	produtos	não	podem	ser	colocados	num	mesmo	container	
porque	reagem.	Quaisquer	dos	dois	produtos	entre	A,	B,	C,	X	reagem	e	A	reage	com	F,	D	e,	
E	 também	reage	com	F,	D.	Descreva	o	grafo	que	modela	essa	situação	e	use	esse	grafo	
para	 descobrir	 o	 menor	 número	 de	 containers	 necessários	 para	 embarcar	 os	 produtos	
com	segurança.	Assinale	a	alternativa	que	contem	o	algoritmo	que	resolve	este	problema	
descrito.		
04.	 Considere	 os	 trecho	 de	 código	 a	 seguir.	 	 Assinale	 a	 alternativa	 que	 explica	
corretamente	o	funcionamento	e	as	características	das	duas	funções.		
	
void colore (int grafo[max+1][max+1], int Vcor[max+1], int v) 
{ 
 int i,cor,usada; 
 
 cor=1; 
 do { 
 usada = 0; 
 for (i=1; i<max; i++) 
 if ((grafo[v][i]==1) && (Vcor[i]==cor)) 
 usada = 1; 
 if (usada == 1) 
 cor++; 
 }while (usada == 1); 
 Vcor[v]=cor; 
 printf (" vertice %d - cor %d\n", v, Vcor[v]); 
} 
 
void caminhamento (int grafo[max+1][max+1], int v, int Vcor[max+1]) 
{ 
 int w; 
 colore(grafo,Vcor,v); 
 for(w = 1; w<=max ; w++) 
 if ((grafo[v][w]== 1) && (Vcor[w]==0)) 
 caminhamento(grafo, w, Vcor); 
} 
 
	
a) O	 algoritmo	 caminhamento	 executa	 uma	 busca	 em	 profundidade	 para	 fazer	 a	
coloração	dos	vértices	de	um	grafo	representado	por	uma	matriz	de	adjacência.		
 
b) O	 algoritmo	 caminhamento	 executa	 uma	 busca	 em	 abrangência	 para	 fazer	 a	
coloração	dos	vértices	de	um	grafo	representado	por	uma	matriz	de	adjacência.	
	
	
c) O	 algoritmo	 caminhamento	 executa	 uma	 busca	 em	 abrangência	 para	 fazer	 a	
coloração	dos	vértices	de	um	grafo	representado	por	uma	lista	de	adjacência.	
	
d) O	 algoritmo	 caminhamento	 executa	 uma	 busca	 em	 profundidade	 para	 fazer	 a	
coloração	dos	vértices	de	um	grafo	representado	por	uma	lista	de	adjacência.	
	
	
e) O	 algoritmo	 caminhamento	 executa	 uma	 busca	 em	 profundidade	 para	 fazer	 a	
coloração	dos	vértices	de	um	grafo	representado	por	uma	matriz	de	incidência.