UNIVERSIDADE FEDERAL DE MINAS GERAIS 
INSTITUTO DE CIö

ENCIAS EXATAS 

÷

DEPARTAMENTO DE CIENCIA DA COMPUTACöüAO 
ALGORITMOS E ESTRUTURAS DE DADOS III 

Professores: Wagner Meira Jr e Jussara Almeida 
TerceiroTeste: 12.5pontos 

Aluno: 


Avaliador: 


¥ Duraüc÷ao do teste: 50 minutos. 
¥ Prova individual e sem consulta. 
¥ Faz parte da prova a interpretaüc÷ao das quest÷oes. Caso vocöe ache que falta algum detalhe 
nas explicaüc÷oes faüca as suposiüc÷oes que achar necess«arias e documente-as na resoluüc÷ao das 
quest÷oes. 
1a 
Quest÷ao 
(6.0 pontos) 

1. Seja o problema de decis÷ao da Cobertura de V«ertices definido como: Dados um grafo 
G 
=(V, 
E) n÷ao direcionado e um inteiro k, G cont«em um subconjunto de v«ertices V 
0 
(V 
0  V 
)de tamanho no m«aximo k 
talque se(u, 
v)2 E 
ent÷ao u 
2 V 
0 ou v 
2 V 
0 , ou 
ambos? 
ProvequeoproblemadaCoberturadeV«ertices «eNP-Completo,partindodapremissa 

que o Problema da Clique «e NP-Completo. 
O Problema da Clique «e definido como: Dados um grafo G 
=(V, 
E)n÷ao direcionado e 
um inteiro k, existe um subconjunto de v«ertices V 
0 (V 
0  V 
)de tamanho no m«õnimo k 
tal que para quaisquer dois v«ertices u 
e v 
em V 
0 , u 
e v 
s÷ao adjacentes? 


Para provar que um problema «e NP-Completo, «e preciso: 

(1)Provar que ele pertence a NP 
(2)Fazer uma reduüc÷ao polimonial de um outro problema conhecidamente NP-
Completo para o problema em quest÷ao. 
ParaprovarqueCV(CoberturadeV«ertices) «eNP,oalunodeve: 

a) Apresentar um algoritmo polinomial n÷ao determinista que o resolva, ou 
b) Apresentar um algoritmo polinomial determinista que verifica uma dada 
soluüc÷ao. 

A seguir apresentamos poss«õveis soluüc÷oes para a) e b). Na prova, o aluno deve 
escolher uma dentre as duas opüc÷oes. 

a) 
algoritmo 
resolveCV(V,E) 


{ 
S 
= 
conjunto 
vazio; 
// 
inicializa 
conjunto 
solucao 
for 
i=1 
to 
|V| 
do 
{ 


flag 
= 
escolhe(V[i]); 
// 
escolhe 
retorna 
se 
vertice 
V[i] 
// 
fara 
parte 
do 
conjunto 
solucao 
if 
(flag 
== 
TRUE) 
S 
= 
S 
+ 
V[i]; 
} 



if 
|S| 
<= 
k 
return 
sucesso; 
return 
insucesso; 


} 


b) 
algoritmo 
verificaCV(V,E,S) 


{ 
if 
(|S| 
> 
k) 
return 
false; 
//solucao 
tem 
no 
maximo 
k 
elementos. 
for 
i=1 
to 
|E| 
do 
{ 
Seja 
(u,v) 
a 
aresta 
sendo 
processada 
Se 
(u 
nao 
pertence 
a 
S) 
e 
(v 
nao 
pertence 
a 
S) 
return 
false; 
} 
return 
true; 


} 


O algoritmo resolveCV tem ordem de complexidade O(|V 
|), assumindo escolhe 
tem ordem de complexidade O(1). J«a o algoritmo verificaCV tem ordem de 
complexidade O(|E|). Ambos s÷ao polinomiais. 

O pr«oximo passo consiste em reduzir polinomialmente o problema da Clique 
(Cq) para o CV. Isto «e, precisamos provar que Cq 
/ CV 
. 

SejaG(V,E),kumainstöanciadaCq, iremos construir umainstöanciaGÕ(VÕ,EÕ), 

ø

kÕ do CV fazendo G 
0 = G 
(grafo complementar)e k 
0 = |V 
|¥k. 

Agora prove: 
1) Se G 
tem Cq de tamanho  k, ent÷ao G 
0 tem CV de tamanho  k 
0 = |V 
|¥k. 


De fato, seja a soluüc÷ao de Cq dada por V 
0 . Quaisquer dois v«ertices em V 
0 töem 
que ser adjacentes em G. Consequentemente, eles n÷ao podem ser adjacentes 

øø

em G. Assim, para toda e qualquer aresta (u, 
v) em G, ou u 
ou v 
ou ambos 
est÷ao no subconjunto V 
¥V 
0 . Este subconjunto «e portanto soluüc÷ao do CV 
em 
Gø
. Como V 
0 tem no m«õnimo k 
v«ertices, V 
¥V 
0 tem no m«aximo |V 
|¥k 
v«ertices. 

2) Se Gø
tem CV de tamanho  k 
0 = |V 
|¥k, ent÷ao G 
tem Cq de tamanho  k. 

Neste caso, seja a soluüc÷ao do CV dada por V 
0 . Ent÷ao temos que, para toda 
e qualquer aresta (u, 
v) 2 Gø
, ou u 
ou v 
ou ambos est÷ao em V 
0 . Portanto, 
seja quaisquer dois v«ertices p 
e q 
que pertencem ao subconjunto V 
¥V 
0 . Por 

ø

construüc÷ao p 
e q 
n÷ao podem ser adjacentes em G 
e, consequentemente, töem 
que ser adjancementes em G. Logo V 
¥V 
0 «e soluüc÷ao do Cq. Como V 
0 tem no 
m«aximo k 
0 = |V 
|¥k 
v«ertices, V 
¥V 
0 tem no m«õnimo k 
v«ertices. 

Nota Crit«erio S/N 
1.5 Provou que Cobertura de V«ertices pertence a NP 
1.5 Fez a transformaüc÷ao do Cq para CV 
1.5 Provou que soluüc÷ao do Cq leva a soluüc÷ao do CV 
1.5 Provou que soluüc÷ao do CV leva a soluüc÷ao do Cq 

2a 
Quest÷ao 
(2.0 + 2.0 + 1.0 + 1.5 pontos) 

Seja o problema de determinar a cobertura de v«ertices em grafos. Pede-se: 

1. Apresente uma heur«õstica gulosa para o problema da cobertura de v«ertices. Qual a 
complexidade do seu algoritmo? 
Umaestrat«egiagulosaseriaadicionar osv«erticesemordemdecrescentedegrau 


at«e que todas as arestas estejam coberta. A complexidade dele «e O(|V 
|log|V 
|) 
se for preciso ordenar os v«ertices em ordem decrescente de grau. 

Nota Crit«erio S/N 
1.5 Apresentou algoritmo correto 
0.5 Complexidade do algoritmo «e correta 

2. Apresente um algoritmo aproximado com raz÷ao de aproximaüc÷ao n÷ao maior que 2 para 
o problema da cobertura de v«ertices. 
1) Inicie o conjunto soluüc÷ao S 
como um conjunto vazio. 
2) Enquanto houver arestas no grafo G 
faüca: 
a) escolha uma aresta qualquer (i, 
j)do grafo, 
b) inclua i 
e j 
a S, 
c) remova todas as arestas incidentes a i 
ea j 
de G. 
Ao final, retorne S. 


Nota Crit«erio S/N 

2.0 Algoritmo correto 
3. Quala complexidade do seu algoritmo? Justifique. 
O algoritmo tem complexidade O(|E|)onde |E|«e o n«umero de arestas nografo. 

Nota Crit«erio S/N 

1.0 Complexidade correta 
4. Quala raz÷ao de aproximaüc÷ao do seu algoritmo? Justifique. 
Seja C 
o conjunto de arestas selecionadas no passo 2a). Note que nenhuma 
destas arestas compartilha um mesmo v«ertice. Uma cobertura de v««

ertices otima 
S deve conter pelo menos um v«ertice ligado a cada uma das arestas de C, 
sen÷ao n÷ao seria uma cobertura. Ent÷ao |S 
||C|. 
A soluüc÷ao S 
retornada pelo algoritmo cont«em os dois v«ertices de cada aresta 
de C. Logo |S|=2|C|. 

S 
2|C|

Portanto, a raz÷ao de aproximaüc÷ao RA 
=  . Ou seja, RA 
 2.

S C 


Nota Crit«erio S/N 

1.5 Raz÷ao de aproximaüc÷ao correta 

Item Nota Observaüc÷oes 
1.1 
2.1 
2.2 
2.3 
2.4 


