On demande à un architecte de concevoir les plans d’un futur musée. Le musée exposera essentiellement des peintures qui seront suspendues aux murs de couloirs.
Une contrainte : les visiteurs doivent pouvoir circuler dans tous les couloirs où sont exposés les oeuvres sans repasser deux fois par un même couloir. Le directeur du musée, pour des raisons artistiques indiscutables, refuse que des pancartes imposent le parcours . . . L’architecte doit donc proposer un plan de musée tel que toute personne partant de l’entrée du musée et déambulant au hasard, en s’interdisant seulement d’emprunter un couloir déjà visité, puisse admirer toutes les oeuvres et finir à son point de départ (pour pouvoir ressortir).
Pouvez-vous trouver un tel plan ? Pouvez-vous trouver une manière de construire tous les plans possibles ?
A la première question, une réponse évidente est bien sûr de créer un long couloir circulaire... Mais est-ce le seul plan possible ; non, bien sûr. La démonstration jointe montrera qu'un tel musée est construit à partir d'un sommet et d'une forêt, c'est à dire un ensemble d'arbres (graphe connexe sans cycles)
On dessine les arbres, on dessine un sommet Entrée que l'on relie à tous les sommets impairs de l'arbre.
Voir la démonstration complète ; c'est un extrait du livre : Introduction à la théorie des graphes, butinage graphique, Jean-Manuel Meny, CRDP de Lyon.