Antilles Guyane – juin 2003
Partie A
Un musée est constitué de 9 salles, notées A, B, C, D, E, F, G, H et S. Le plan du musée est représenté ci-contre : Ainsi, un visiteur qui se trouve dans la salle S peut atteindre directement les salles A, D ou G. S’il se trouve dans la salle C, il peut se rendre directement dans la salle B, mais pas dans la salle F. On s’intéresse au parcours d’un visiteur dans ce musée. On ne se préoccupe pas de la manière dont le visiteur accède au musée ni comment il en sort.
Cette situation peut être modélisée par un graphe, les sommets étant les noms des salles, les arêtes représentant les portes de communication.
Dessiner un graphe représentant la situation décrite.
Est-il possible de visiter le musée en empruntant chaque porte une fois et une seule ? Justifier en utilisant un théorème du cours sur les graphes.
Pour rompre une éventuelle monotonie, le conservateur du musée souhaite différencier chaque salle de sa ou de ses salles voisines (c’est-à-dire accessibles par une porte) par la moquette posée au sol.
Quel est le nombre minimum de types de moquettes nécessaires pour répondre à ce souhait ? Justifier.