Une grande ville a créé un jardin pédagogique sur le thème de l'écologie, jardin qui doit être visité par la suite par la majorité des classes de cette ville.
Ce jardin comporte six zones distinctes correspondant aux thèmes :
A. Eau | B. Économie d'énergies | C. Plantations et cultures locales |
D. Développement durable | E. Biotechnologies | F. Contes d'ici (et d'ailleurs) |
Ces zones sont reliées par des passages (portes) où sont proposés des questionnaires.
Le jardin et les portes sont représentés par le graphe ci-dessous (chaque porte et donc chaque questionnaire est représenté par une arête).
question préliminaire :
Si un visiteur répond à tous les questionnaires, à combien de questionnaires aura-t-il répondu ?
Donner la matrice G associée à ce graphe.
Le graphe est-il complet ? Est-il connexe ? Justifier.
Peut-on parcourir le jardin en répondant à tous les questionnaires et sans repasser deux fois devant le même questionnaire :
Parcourir le jardin en répondant à tous les questionnaires et sans repasser deux fois devant le même questionnaire revient chercher une chaîne eulérienne.
en commençant la visite par n'importe quelle zone ?
en commençant la visite par la zone C (plantations et cultures) ? Dans ce cas, si la réponse est positive, quelle sera la dernière zone visitée.
(Dans les deux cas, a et b, justifiez votre réponse.)
Si le nombre de sommets de degré impair d'un graphe est 2, les sommets de degré impair sont les extrémités de la chaîne eulérienne.
Pour illustrer chaque zone et présenter légendes et commentaires, les enfants ont décidé d'utiliser des supports de couleurs différentes.
Pour limiter le nombre de couleurs, on utilise des couleurs différentes seulement si les zones sont limitrophes (avec un passage entre les deux).
Donner et justifier un encadrement du nombre chromatique de ce graphe.
Propriété 1:
Soit n le plus haut des degré des sommets d'un graphe G; le nombre chromatique de G est inférieur ou égal à n + 1.
Propriété 2:
Le nombre chromatique d'un graphe complet d'ordre n est égal à n.
Déterminer alors en utilisant un algorithme adapté le nombre chromatique de ce graphe et proposer une répartition des couleurs.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.