¿El algoritmo de Kruskal resuelve siempre el problema del vendedor ambulante?

1. El algoritmo de Kruskal resuelve el problema del árbol de expansión mínimo.
2. Puede utilizar el algoritmo de Kruskal en parte para calcular un recorrido TSP cuando las instancias TSP satisfacen la desigualdad del triángulo, pero no se garantiza que sea una solución óptima. Ver algoritmo Christofides – Wikipedia. Es el paso 1, pero de ninguna manera un árbol de expansión equivale a un recorrido TSP, debe hacer más.

¿Cómo puedes demostrar que no siempre resuelve TSP? En pocas palabras, no son el mismo problema (esto debería ser suficiente, pero sigamos). Si produce un árbol de expansión mínimo, de ninguna manera será un recorrido TSP porque se requiere un ciclo hamiltoniano para ser un recorrido TSP. Para atravesar ese árbol, necesitarás visitar dos vértices dos veces muchas veces cuando llegues a una hoja para explorar más vértices. Es por eso que el algoritmo que mencioné anteriormente hace más para obtener un ciclo (y tenga en cuenta que esto solo funciona en casos específicos).