Baccalauréat 2010 MATHÉMATIQUES Série ES
sujet : Pondichery
Corrigé de l'exercice 2 : candidats ayant suivi l'enseignement de spécialité
On considère un espace de jeu réservé à des enfants. Les enfants peuvent se déplacer sur cinq plates-formes notées A, B, C, D et E.
Ces plates-formes sont reliées entre elles par un certain nombre de rampes, comme indiqué sur le schéma ci-dessous :
On représente cet espace de jeu par le graphe G ci-contre : Une plate-forme est représentée par un sommet et une rampe est représentée par une arête |
partie a
Donner un sous-graphe complet d'ordre 4 du graphe G.
est un sous-graphe complet d'ordre 4 du graphe G.
En déduire un encadrement du nombre chromatique du graphe G. Justifier la réponse.
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. D'où :
Sommets A B C D E Degré des sommets du graphe 4 4 3 4 3 Soit X le nombre chromatique du graphe G. Le plus haut degré des sommets est 4 donc . D'autre part, est un sous-graphe complet d'ordre 4 du graphe G donc
Ainsi, .
Proposer une coloration du graphe G en expliquant la méthode utilisée.
On attribue une couleur distincte à chacun des sommets du sous-graphe complet . Les sommets C et E ne sont pas adjacents, on leur attribue la même couleur.
En déduire la valeur du nombre chromatique du graphe G.
Une coloration avec quatre couleurs est possible, comme donc le nombre chromatique du graphe est 4.
partie b
Ce graphe est-il connexe ? Est-il complet ? Justifier les réponses.
La chaîne A-B-C-D-E contient tous les sommets du graphe.
Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Les sommets C et E ne sont pas adjacents, Par conséquent, le graphe G n'est pas complet.
Ce graphe contient-il une chaîne eulérienne ? Justifier la réponse.
Le graphe G est connexe et contient seulement deux sommets de degré impair :
Il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (C ou E) et finissant par le deuxième sommet de degré impair.
Si on rajoute une arête à ce graphe, quels sommets peut-on alors relier pour que le graphe obtenu contienne un cycle eulérien ? Justifier la réponse.
Les sommets C et E ne sont pas adjacents et sont de degré impair.
Si on relie les sommets C et E par une arête, alors tous les sommets du graphe obtenu seront de degré pair. Ce nouveau graphe admet alors un cycle eulérien.
partie c
On décide de peindre les surfaces des cinq plates-formes en attribuant des couleurs différentes à deux plates-formes reliées par une rampe.
Quel est le nombre minimum de couleurs nécessaire ? Justifier la réponse.Le nombre chromatique du graphe est 4. Donc quatre couleurs suffisent.
On propose aux enfants le jeu suivant : il s'agit de partir de la plateforme C et de rejoindre la plateforme E en utilisant toutes les rampes, et sans passer deux fois par la même rampe. Proposer un chemin remplissant les conditions exposées ci-dessus.
Il existe une chaîne eulérienne commençant par le sommet de degré impair C et finissant par le deuxième sommet de degré impair E.
Par exemple le chemin C-D-B-A-E-B-C-A-D-E.
Pour faciliter le déplacement des enfants dans cet espace de jeu, on décide d'installer une nouvelle rampe. Où peut-on placer cette rampe pour obtenir l'existence d'un chemin qui, partant d'une plate-forme donnée, emprunte une et une seule fois chaque rampe pour revenir à la plate-forme initiale ? Justifier la réponse.
D'après le résultat établi dans question 3 de la partie B :
Il suffit d'installer la nouvelle rampe entre les plates-formes E et C pour obtenir un cycle eulérien.
La construction risque d'être délicate !
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.