Seminario de grafos y algoritmos asociados, basado en el libro "For all practical purposes" de COMAP y organizado por la Olimpíada Matemática Argentina
Problema de distancia más corta y árbol generador mínimo.
Es verdad, ahora que lo analizo mejor no tiene sentido. No tiene sentido el apartado b. Se podría modificar pensando que los vértices son pueblos y las aristas caminos de tierra, y se quieren pavimentar algunos de los caminos de tierra de modo que todos los pueblos queden conectados de alguna forma (directa o no) por un camino pavimentado con el menor costo posible.
Humm, no veo por qué usar un árbol mínimo, ya que no hay costos de construcción. ¿Cómo sería?
ResponderEliminarEs verdad, ahora que lo analizo mejor no tiene sentido. No tiene sentido el apartado b.
EliminarSe podría modificar pensando que los vértices son pueblos y las aristas caminos de tierra, y se quieren pavimentar algunos de los caminos de tierra de modo que todos los pueblos queden conectados de alguna forma (directa o no) por un camino pavimentado con el menor costo posible.