Siguiendo con árbol generador

Hola gente: porfa vayan poniendo en este blog problemas/situaciones aún cuando ya las hayamos visto y discutido en los encuentros.

Les recuerdo que en mi opinión no vale la pena continuar con las reuniones sin antes cerrar el tema de grafos (o a lo sumo encontrarse una última vez para cerrarlo).

Como nos está costando arrancar, acá va una contribución.

Una de los temas que reaparecieron en las reuniones fue el de dar ejemplos de determinados problemas, y recíprocamente, reconocer a qué problema corresponde determinada situación.

Buscando ejemplos del problema del mínimo árbol generador que sugirió Mayra, encontré el siguiente ejemplo en una página de internet:

Para tu viaje a Venecia (!) tenés pensado visitar la mayor cantidad de sitios históricos, pero no tenés demasiado tiempo. Para decidir tu itinerario, decidís usar el algoritmo de Kruskal.

El ejemplo viene acompañado de un mapa con los lugares que uno quiere visitar.

Uno podría dar un problema similar, por ejemplo para visitar distintos museos y muestras cuando visita Buenos Aires (CABA).

Me parece que se podrían hacer varias actividades alrededor, como por ejemplo:

• En un mapa de Bs. As encontrar/estimar las distancias entre puntos determinados.
  

  En la actividad concreta tal vez podría imprimirse un mapa, o usar algo como Google maps.
  

• El problema presentado, ¿es de mínimo árbol generador? Si no, ¿qué tipo de problema es?, ¿es alguno de los que vimos?, ¿cómo se resuelve?
  
• Supongamos que encuentro que para visitar todos los lugares que me interesan necesito más tiempo del que dispongo.
  ¿Cómo puedo hacer para visitar la mayor cantidad de lugares señalados con el tiempo que dispongo?, ¿habría que poner prioridades/preferencias?, ¿cómo se resolvería en ese caso?
  
• En general, uno va a pasar más de un día visitando la ciudad.
  ¿Cómo se podría plantear (= cuál es el modelo) y resolver el problema en ese caso?
  

Sería bueno que rumiaran el problema y plantearan algunas otras preguntas en el blog.