ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
 
Graphe et nombre chromatique
Extrait sujet baccalauréat ES - juin 2003 |
» Ce sujet de baccalauréat est un bon exemple de l'usage de la coloration d'un graphe dans un problème combinatoire de planning (organisation de transports, emploi du temps, travaux soumis à des contraintes, etc.).
Un concert de solidarité est organisé dans une grande salle de spectacle.
A ce concert sont conviés sept artistes de renommée internationale : Luther Allunison (A), John Biaise (B), Phil Colline (C), Bob Ditlane (D), Jimi Endisque (E), Robert Fripe (F) et Rory Garaguerre (G).
Les différents musiciens invités refusant de jouer avec certains autres, l'organisateur du concert doit prévoir plusieurs parties de spectacle. Les arêtes du graphe ci-dessous indiquent quels sont les musiciens qui refusent de jouer entre eux.
1°/ Déterminer la matrice associée au graphe Γ.
» les sommets de Γ
seront classés
dans l’ordre alphabétique.
2°/ Quelle est la nature du sous-graphe
constitué des sommets A, E, F et G ?
Que peut-on en déduire pour le nombre chromatique n du graphe
Γ ?
3°/ Quel est le sommet de plus haut degré de Γ ? En déduire un encadrement de n.
4°/ Après avoir classé l’ensemble des sommets de Γ par ordre de degré décroissant,5°/ Combien de concerts l’organisateur doit-il prévoir ?
Proposer une répartition des musiciens pour chacun de ces
concerts.
| Solution : |
1°/ On est en présence d'un graphe d'ordre 7. La matrice du graphe contient donc 7 lignes et 7 colonnes. un élément mi,j est égal à 1 ou 0 suivant qu'il existe ou non une arête du sommet i vers le sommet j. Le graphe étant non orienté, la matrice sera symétrique et la diagonale est remplie de 0 puisqu'aucun sommet n'est relié à lui-même (pas de boucle : un musicien se tolère lui-même...) :
2°/ Le sous-graphe est complet car deux quelconques de ses sommets sont adjacents (reliés). Le nombre chromatique d'un graphe complet est égal à son ordre et celui d'un graphe est supérieur ou égal au nombre chromatique d'un de ses sous-graphes. On en déduit n ≥ 4.
3°/ Le degré le plus élevé est celui de F, à savoir 6 (nombre d'arêtes d'origine ou extrémité F). On sait que le nombre chromatique d'un graphe est au moins égal à d + 1, d désignant le degré le plus élevé. On en déduit donc l'encadrement 4 ≤ n ≤ 7.
4°/ On classe les sommets dans l'ordre demandé et on commence par colorier celui de plus haut degré, soit F. Le sous-graphe restreint à A, E, F, G de 2° étant complet : il nécessite 4 couleurs. On le colore en premier et on obtient ensuite très facilement un coloriage au moyen de ces 4 couleurs :
5°/ Les 4 couleurs qui ont été utilisées permettent d'associer des musiciens acceptant de jouer ensemble. Deux sommets de même couleur peuvent être associés car ils sont alors non adjacents donc acceptant de jouer ensemble. Résumons par ordre alphabétique :
A jouera avec C;
B jouera avec G;
D jouera avec E;
F jouera tout seul !
Ce qui nous fait 4 concerts.