Desafio 47 | Construção de mercearias

O Adolfo foi convidado para trabalhar num projeto com o arquiteto e urbanista do seu concelho. Têm como missão instalar mercearias para servir todas as aldeias. Decidiram que uma aldeia tem de ter uma mercearia perto. Isto significa que os habitantes dessa aldeia não terão de passar por outra para aceder a uma mercearia. Na imagem abaixo, os círculos representam as aldeias, os quadrados representam os locais onde poderão ser construídas as mercearias e as linhas representam as estradas que ligam as aldeias.

Questão:

Sabendo que se pretende construir o menor número possível de mercearias, quantas deverão ser construídas de forma a servir todas as aldeias do concelho?