lau

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: O problema do ciclo de Hamiltoniano (HAM-CYCLE) e o problema do caixeiro viajante (TSP) são bastantes conhecidos da teoria de NP-completude. Sabendo que HAM-CYCLE é NP-completo e que TSP é NP, para provar que TSP é NP-completo, basta mostrar que TSP é NP-difícil apresentando uma redução polinomial do HAM-CYCLE para o TSP. Quantas arestas são necessárias adicionar ao grafo abaixo para realizar tal redução? 

 

 

Observação: o grafo acima apresenta HAM-CYCLE.

1. 1
2. 3  
3. 10
4. 12
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto