MO640 - Questão para a prova oral

Número: 009

Enunciado:

Dentre afirmações abaixo, qual está correta?

1. Ambos os problemas (a) de encontrar o ciclo hamiltoniano e (b) de encontrar o ciclo euleriano pertencem à classe NP-Completo.
   
2. Não existem grafos que admitem simultaneamente ciclos hamiltonianos e eulerianos.
3. Grafos eulerianos e hamiltonianos são obrigatoriamente grafos conexos.
4. O problema do caixeiro viajante é um caso particular do problema de encontrar o ciclo euleriano.
   
5. NDA

Autor(a): Roberto Hiroshi Higa.