Transports de fromages - Lycée Léonard de Vinci (Calais)

Le réseau de transport de la Région est représenté par un graphe : l'une des villes est Calais. Dans chaque ville se trouve un entrepôt de fromages de Maroilles. Et sur chaque route est embusqué un renard par l'odeur alléché.
On transporte des fromages le long des routes, d'une ville à l'autre. Sur chaque route, on ne peut transporter qu'un nombre pair de fromages. Lors de ce transport, le renard embusqué en prélève la moitié.
But : livrer au moins un fromage à Calais.
Question : combien de fromages faut-il avoir au minimum pour que, quelle que soit leur distribution initiale, il soit toujours possible d'amener un fromage à Calais ?
Par exemple, pour le graphe Calais---Gravelines---Dunkerque, il suffit d'avoir 4 fromages. Quelle que soit la localisation de ces 4 fromages au départ, un fromage parvient toujours à Calais. Par contre, avec seulement 3 fromages placés à Dunkerque, c'est impossible. Le nombre minimal est donc 4.
La réponse dépend de la complexité des graphes et du nombre de villes. Tester tout d'abord les graphes ligne, puis des arbres, etc... Bon appétit !