Vamos a calcular la solución del Problema del Viajante, en un grafo ponderado, calculando TODOS los ciclos de Hamilton y eligiendo el menor. La manera de introducir los pesos de las aristas es de forma ordenada (j,k), 1 ≤ j ≤ v-1, j < k ≤v, siendo v el número de vértices.
La función w(j,k), nos da el peso que une los vértices j < k de la lista del grafo. Extendemos el peso para valores k < j, de manera simétrica, con la función peso:
Fijamos el vértice 1 y calculamos las permutaciones de los v-1 restantes:
Finalmente definimos la función que calcula el peso del ciclo mínimo, y un ciclo solución:
Consideramos el triángulo de manera que w(1,2)=1, w(1,3)=2 y w(2,3)=3:
Tomamos ahora los grafos completos con v=3,4,...,10 puntos, con sucesión de pesos dada por {1,2,...,v(v-1)/2}. Observamos cómo los tiempos van creciendo factorialmente, y para v=10 se necesitan 4 minutos:
Este ejemplo corresponde a las distancias entre 1=Londres, 2= México DF, 3=Nueva York, 4=París, 5=Pekín y 6=Tokio:
Created by Mathematica (May 1, 2006) | ![]() |