El problema del vendedor ambulante (TSP) es cualquier problema en el que debes visitar cada vértice de una gráfica ponderada una vez y solo una vez, y luego terminar de nuevo en el vértice inicial. Ej...El problema del vendedor ambulante (TSP) es cualquier problema en el que debes visitar cada vértice de una gráfica ponderada una vez y solo una vez, y luego terminar de nuevo en el vértice inicial. Ejemplos de situaciones de TSP son entregas de paquetes, fabricación de placas de circuitos, programación de trabajos en una máquina y hacer recados por la ciudad.
Queremos saber si esta gráfica tiene un ciclo, o camino, que usa cada vértice exactamente una vez. (Recordemos que un ciclo en una gráfica es un subgrafo que es un ciclo, y un camino es un subgrafo qu...Queremos saber si esta gráfica tiene un ciclo, o camino, que usa cada vértice exactamente una vez. (Recordemos que un ciclo en una gráfica es un subgrafo que es un ciclo, y un camino es un subgrafo que es un camino.) No hay beneficio ni inconveniente en los bucles y múltiples aristas en este contexto: los bucles nunca se pueden usar en un ciclo o trayectoria de Hamilton (excepto en el caso trivial de una gráfica con un solo vértice), y como máximo se puede usar uno de los bordes entre dos vérti…
