Arbre couvrant - Lycée Marguerite de Navarre (Bourges)

Dans la ville « Gadoue », il est très difficile de circuler après de fortes pluies car le sol devient boueux faute de rues pavées. Le maire décide donc de paver certaines rues, mais en respectant deux conditions :
- Paver suffisamment de rues pour que n’importe quel habitant puisse se rendre de sa maison à n’importe quelle autre maison en empruntant les rues pavées.
- Dépenser le moins d’argent possible pour paver ces rues.
On cherche donc à trouver le meilleur chemin pour relier toutes les maisons d'une ville mais en utilisant le moins de pavés possibles.