MO640 - Questão para a prova oral

Número: 016

Enunciado:
Escolha a alternativa correta é:

1. Numa string palíndrome s o sufixo(s,k) = prefixo(s,k) para 1 < k < |s|/2.
2. Toda árvore é um grafo completo.
3. Encontrar um ciclo Hamiltoniano de mínimo custo num grafo é conhecido como o problema do caixeiro viajante.
4. Se um problema A pode ser reduzido a um problema que pertença à classe NP-completo então o problema A também é NP-completo.
5. NDA

Autor(a): Danilo Benzatti