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
- 3
- 10
- 12
- NDA.
Ideia original de: Laurindo de Sousa Britto Neto
Nenhum comentário:
Postar um comentário