Logo de Tangente Éducation

Le facteur

Jean-Marc Vincent

Un algorithme très utilisé en informatique est le parcours des arêtes d'un graphe. La (re)découverte de ce classique problème du à Euler est aussi l'occasion de s'interroger sur une méthode de résolution automatique.

La tournée du facteur 

Pour économiser ses mollets, le facteur cherche à distribuer le courrier aux habitants d’une ville en ne passant qu’une seule fois par rue. La ville se représente par un graphe dont les sommets sont les carrefours. Pour la manipulation, le graphe est matérialisé par une planche à clous et parcouru à l’aide de ficelles. L’objectif est de construire un chemin passant par toute les arêtes mais une fois seulement.
Il y a deux aspects à ce problème : dans un premier temps on demande de trouver un critère pour être certain qu’un tel chemin existe. En effet, plusieurs « villes » différentes sont proposées et, pour certaines, l’exploration ne donne aucun résultat. Il est fondamental d’établir les conditions de l’existence du parcours pour ne pas rester sur la croyance qu’un temps de recherche plus long permettrait de trouver une solution.
Dans un second temps, lorsqu’on est sûr d’avoir affaire à une ville permettant la tournée du facteur, il reste à construire un algorithme donnant la solution. Une idée clé est de remarquer que le problème peut se décomposer en sous-problèmes de même nature. Dans ce cas on résout récursivement les sous-problèmes et ... Lire la suite


RÉFÉRENCES

Les ressources du site de l'IREM de Grenoble.
Tous les chemins mènent à Königsberg, Benoit Rittaud, Les graphes, Bibliothèque Tangente 54.