Prueba de que el problema del viajante de comercio es NP Difícil

Prerrequisito: Problema del viajante de comercio , NP Difícil

Dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema del vendedor ambulante encuentra el camino entre estas ciudades de modo que sea el camino más corto y atraviese cada ciudad una vez, regresando al punto de partida.

Problema: dada una gráfica G(V, E) , el problema es determinar si la gráfica tiene un TSP que consiste en un costo como máximo K.
Explicación:
para demostrar que el problema del viajante de comercio es NP-Difícil, tendremos que reducir un problema NP-Difícil conocido a este problema. Realizaremos una reducción del problema del ciclo hamiltoniano al problema del viajante de comercio.
Cada instancia del problema del ciclo hamiltoniano consta de un gráfico G = (V, E), ya que la entrada se puede convertir en un problema del viajante de comercio que consta del gráfico G’ = (V’, E’) y el costo máximo, K. construirá el grafo G’ de la siguiente manera:
Para todas las aristas e pertenecientes a E, sume el costo de la arista c(e)=1. Conecta las aristas restantes, e’ pertenecientes a E’, que no están presentes en el grafo original G , cada una con un costo c(e’)= 2.
Y, establece .
El nuevo gráfico G’ se puede construir en tiempo polinomial simplemente convirtiendo G en un gráfico completo G’ y agregando los costos correspondientes. Esta reducción puede probarse mediante las dos afirmaciones siguientes:

• Supongamos que el grafo G contiene un Ciclo Hamiltoniano, atravesando todos los vértices V del grafo. Ahora, estos vértices forman un TSP con Dado que utiliza todas las aristas del gráfico original que tiene un costo c(e)=1. Y, como es un ciclo, por lo tanto, vuelve al vértice original.
• Suponemos que el grafo G’ contiene un TSP con costo, . El TSP atraviesa todos los vértices del gráfico volviendo al vértice original. Ahora bien, dado que ninguno de los vértices está excluido del gráfico y el costo suma n, por lo tanto, necesariamente utiliza todas las aristas del gráfico presentes en E , con costo 1, formando así un ciclo hamiltoniano con el gráfico G .

Así podemos decir que el grafo G’ contiene un TSP si el grafo G contiene un Ciclo Hamiltoniano. Por lo tanto, cualquier instancia del problema del viajante de comercio puede reducirse a una instancia del problema del ciclo hamiltoniano. Por lo tanto, el TSP es NP-Hard.