Problema del Viajante (PV)

Estoy pensando en armar una actividad que tenga que ver con el PV.
La idea sería combinar lo que desarrolla el libro (Separta) sobre este problema con algunos ejercicios que hay al final de la sección.
Se podría presentar un grafo (completo) similar al que aparece en la página 35, con los nodos representando ciudades y con pesos en las aristas (podríamos armar una versión "argentina" del grafo, con ciudades de nuestro país, o que los nodos representen otra cosa para que tenga sentido que sea un grafo completo, eso habría que estudiarlo)
Mediante una guía de preguntas se podría ir haciendo analizar a "los alumnos" distintas cuestiones, como por ejemplo, 1) que encuentren un ciclo de hamilton y calculen el peso. 2) que encuentren otro ciclo de hamilton distinto al anterior y su respectivo peso, y que además lo comparen con el anterior. 3) que expliquen cuántos ciclos hay en el grafo completo 4) que intenten calcular el ciclo de peso mínimo. 5) que generalicen la cantidad de ciclos hamiltonianos que hay en un grafo completo 6) ¿Qué sucede a medida que crece en número de vértices en el grafo? ¿Si el grafo tiene 20 ciudades?

Todo esto podría continuar sobre una charla acerca de los problemas NP-completos y tal vez sobre algunas de las estrategias (heurísticas) que desarrolla el libro para resolver el PV.

Si les parece bien voy dándole forma a esta idea, sino no!!! Cuenten qué les parece...

Saludos!
Natalia