La Réunion – juin 2003
Une grande surface est conçue de telle façon que six secteurs (alimentation, hi-fi, etc.) notés A, B, C, D, E, F sont reliés par des allées selon le graphe G ci-dessous.
Degré
F
E
D
C
B
A
Secteur
Recopier et compléter le tableau suivant :
Le graphe G est-il connexe ? Pourquoi ?
Un visiteur désire parcourir l’ensemble des allées en ne passant par celles-ci qu’une seule fois.
Démontrer que son souhait est réalisable.
Donner un exemple d’un tel parcours.
Le directeur désire associer chaque secteur à une couleur de sorte que deux secteurs (sommets) ne portent pas la même couleur.
Démontrer que le nombre chromatique n du graphe vérifie .
Expliquer pourquoi .
Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.
Une famille se trouve dans le secteur E et doit se rendre dans le secteur F. Cela étant, les parents connaissent suffisamment les allées pour savoir que, pour chacune d’elles, les enfants ne résistant pas, il leur faudra débourser une somme (en euros) précisée dans le graphe ci-dessous.
Indiquer une chaîne qui minimise la dépense de cette famille