dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um programador propôs a seguinte rotina para transformar um grafo G em um de seus possíveis ciclos hamiltonianos (CH), ou retornar nulo caso não haja um.

HAM-CICLO(G):
  se VERIFICA-HAM-CICLO(G) == falso
      retorna NULO;

  para cada aresta (u, v) de G
      REMOVE-ELEMENTO(v, G.adj[u]);       // elimina aresta (u, v)

  se VERIFICA-HAM-CICLO(G) == falso   // G deixou de possuir um CH?
  ADICIONA-ELEMENTO(v, G.adj[u]);  // recupera aresta (u, v)

   retorna G;

Admitindo-se que as operações REMOVE-ELEMENTO e ADICIONA-ELEMENTO têm complexidade Θ(1) em relação ao tamanho de G.adj[u], e que a operação VERIFICA-HAM-CICLO(G) decide se o grafo G possui ou não um ciclo hamiltoniano, considere as seguintes afirmações:

I) O problema resolvido pela rotina HAM-CICLO é da classe NP. 

II) O problema resolvido pela rotina VERIFICA-HAM-CICLO é da classe NP.

III) Se comprovado que o problema resolvido pela rotina VERIFICA-HAM-CICLO pertence à classe P de problemas, então HAM-CICLO poderá ser executado em tempo polinomial, com relação ao tamanho do grafo de entrada.
IV) VERIFICA-HAM-CICLO resolve um problema de decisão e, por isto, certamente pertence à classe P. Já HAM-CICLO diz respeito a um problema de otimização, que talvez pertença à classe P, se um dia comprovar-se que P = NP.

Escolha a alternativa verdadeira:

1. Todas as afirmações são verdadeiras.
2. Apenas as afirmações I, II e III são verdadeiras.
3. Apenas as afirmações I e II são verdadeiras.
4. Apenas as afirmações II e III são verdadeiras.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira