var

MO417 - Questão para a prova oral

Número:

Enunciado: Conhecemos que o problema de decisão do CLIQUE é NP-Completo. Analise as sentenças a seguir e identifique a alternativa correta.

I) O problema de decisão do CLIQUE em grafos bipartidos é NP-Completo
II) O problema de decisão do CLIQUE em grafos planares é de classe P
III) O problema de decisão do CLIQUE em grafos densos não é NP-Completo

a) Apenas I está correta
b) Apenas II está correta
c) Apenas III está correta
d) Todas estão corretas
e) NDA


Ideia original de: John Edgar Vargas Muñoz