Propagation d’épidémie - Collège Henri Wallon (Saint-Martin d’Hères)

Une épidémie se déclenche dans une ville. À chaque tour, l'épidémie va contaminer toutes les villes qui sont reliées par une route à ville déjà contaminée. Heureusement, pour protéger la région, on pourra vacciner une ville à chaque tour. L'épidémie ne pourra jamais infecter les villes vaccinées. Peut-on déterminer quelles sont les villes à vacciner pour que l'épidémie infecte le moins de villes possible au final ?