ota

MO417- Questão para a prova oral
Numero:

Um dos problemas de Karp, os quais foram provados pertencerem a NP-Completo, é o problema do clique máximo em um grafo não direcionado.
O clique máximo de um grafo G é o maior subgrafo, em número de vértices, os quais todos os vértices estejam conectados, ou seja o subgrafo completo com maior número de vértices de G.

Um uso do clique máximo é achar nas redes sociais, com usuários como vértices e as arestas a relação entre eles, o maior grupo, ou subgrafo, onde todos os usuários estejam conectados entre si, e assim direcionar alguns recursos como notícias e propagandas.

Sobre esse problema:

I.  O problema de se achar o clique máximo em G , no complemento de G,  é mais fácil  do que em G.
II. Seria possível encontrar um k-clique máximo de G=(V,E), ou um clique com k vértices para k <|V| , em tempo polinomial  através de buscas em grafos.
III. Se for possível enumerar todos as componentes fortemente conexas de G em tempo polinomial, o problema do clique também seria resolvido em tempo polinomial para o tamanho da entrada.
IV.  Como se trata de um problema de decisão, é possível propor um algoritmo guloso que pode encontrar pelo menos um i-clique, onde i é menor ou igual ao clique máximo.

São verdadeiras apenas:

a.  I  e II
b.  II e III
c.  III e IV
d.  II e IV
e.  N.D.A

Ideia original de: Otavio Augusto A. Silva