| Les sujets "zéro" du baccalauréat
|
| Série ES
|
| Exercice 26 (enseignement de spécialité)
|
Enoncé.
On désire transporter sept produits chimiques par chemin de fer.
Pour des problèmes de sécurité, certains de ces produits ne peuvent pas être transportés dans le même wagon, ils sont considérés comme incompatibles. L'objectif de cet exercice consiste à rechercher une répartition des produits qui utilise un nombre optimal de wagons.
|
On donne ci-contre le tableau d'incompatibilité entre ces sept produits, désignés par les lettres A, B, C, D, E, F, et G:
Ce tableau signifie, par exemple, que les produits C et D ne peuvent pas être transportés dans un même wagon. |
1- Parmi les trois graphes proposés ci-dessous, quel est celui qui représente cette situation? Justifier ce choix.
Par la suite ce graphe sera noté ().
2- Donner un sous-graphe complet d'ordre maximal.
3- a) Colorier le graphe () et déterminer son nombre chromatique en justifiant la valeur trouvée.
b) Indiquer une répartition possible de ces produits qui permette d'utiliser un nombre minimal de wagons pour assurer leur transport.
c) Quel est alors le nombre maximum de produits pouvant être transportés dans un même wagon?
Solution
1- Le graphe 2 ne convient pas parce qu'il ne contient pas l'arête AE. Le graphe 1 ne convient pas parce qu'il ne contient pas l'arête CF. Donc le graphe qui représente la situation est le graphe 3 nommé .
2- Le sous graphe de sommets ABFE est complet parce que chaque sommet est lié à tous les autres et il est d'ordre 4 puisqu'il a 4 sommets et cet ordre est le maximum possible.
3- a) On a rangé les sommets du graphe par ordre décroissant de leur degré. On a obtenu le coloriage suivant:
| Sommet |
E |
B |
F |
C |
D |
A |
G |
| Couleur |
Rouge |
Bleu |
Jaune |
Bleu |
Jaune |
Vert |
Rouge |
Graphe colorié:
Le nombre chromatique de ce graphe est le nombre minimum de couleurs nécessaire pour le colorier, donc il est égal à 4.
b) Une répartition possible des produits qui permette d'utiliser un nombre minimal de wagons pour assurer leur transport est la suivante: E et G, B et C, F et D, A.
c) Le nombre maximum de produits pouvant être transportés dans un même wagon est alors égal à 2.
Retour
|
|
|