Combien de créneaux faut-il au minimum pour organiser des examens sans qu'aucun élève n'en ait deux en même temps ?
On relie deux épreuves qui ont un élève en commun ; il faut colorier le graphe sans que deux sommets voisins aient la même couleur. Un triangle impose au moins 3 couleurs, et l'algorithme glouton en utilise au plus Δ + 1, où Δ est le plus grand degré. Sur l'exemple, 3 créneaux suffisent.
Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.
Pourquoi cette question : un modèle d'introduction
Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.
Lors des épreuves du bac blanc, je me suis demandé comment l'administration construisait le planning : certains élèves passent des spécialités différentes, et aucune ne doit tomber au même moment pour un même élève. En NSI, j'ai découvert que ce problème s'appelle la coloration de graphe, et qu'il se pose aussi pour les fréquences radio ou les cartes de géographie.
L'enjeu et les notions du programme
Modéliser des contraintes par un graphe, encadrer le nombre de couleurs nécessaires et analyser un algorithme glouton.
Mathématiques
- Raisonnement : minorant et majorant d'un nombre (seconde)
- Raisonnement par récurrence (terminale)
- Pour aller plus loin : graphes, degré (maths expertes)
Numérique et sciences informatiques
- Graphes non orientés, voisinage (terminale)
- Algorithmes gloutons (première)
Le plan de l'exposé en 9,5 min
1. Introduction
1 minCinq épreuves : maths (M), physique (P), SES (S), histoire (H), anglais (A). Des élèves passent à la fois M et P, M et S, P et S, S et H, H et A, A et M. Problématique : combien de créneaux faut-il au minimum ?
2. Mathématiques : encadrer le nombre de couleurs
4 minGraphe : un sommet par épreuve, une arête quand deux épreuves ont un élève commun. Un créneau est une couleur ; deux sommets reliés doivent avoir des couleurs différentes. Le plus petit nombre de couleurs possible s'appelle le nombre chromatique.
Minorant : M, P et S sont reliés deux à deux (triangle). Ils demandent 3 couleurs différentes : il faut au moins 3 créneaux.
Majorant : on propose M = 1, P = 2, S = 3, H = 1, A = 2. On vérifie chaque arête : M–P (1, 2), M–S (1, 3), P–S (2, 3), S–H (3, 1), H–A (1, 2), A–M (2, 1). Tout est correct : 3 créneaux suffisent. Le nombre chromatique vaut donc exactement 3.
Résultat général : si chaque sommet a au plus Δ voisins, Δ+1 couleurs suffisent toujours. Par récurrence sur le nombre de sommets : on colorie le graphe privé d'un sommet, puis ce sommet a au plus Δ voisins, donc au moins une couleur libre parmi Δ+1. Ici Δ=3 : au plus 4 couleurs.
3. NSI : l'algorithme glouton
3 minOn parcourt les sommets dans un ordre donné et l'on attribue à chacun la plus petite couleur non utilisée par ses voisins déjà colorés. C'est exactement la preuve de la borne Δ+1, transformée en programme.
Le résultat dépend de l'ordre : un mauvais ordre peut utiliser beaucoup plus de couleurs que nécessaire. Une heuristique classique traite d'abord les sommets de plus grand degré. Trouver le nombre chromatique exact est un problème difficile en général (NP-complet). Pour une carte de géographie, le théorème des quatre couleurs, démontré en 1976 avec l'aide d'un ordinateur, garantit que 4 couleurs suffisent toujours.
4. Conclusion
1,5 minUn triangle d'épreuves impose 3 créneaux, et une coloration explicite montre que 3 suffisent. L'algorithme glouton garantit au plus Δ+1 couleurs, sans toujours trouver l'optimum. J'ouvre sur l'attribution des fréquences aux antennes de téléphonie, qui est le même problème.
Ce que j'écris au tableau
Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.
χ≤Δ+1=4 ( glouton )
Conclusion : la réponse à la question
Le planning optimal se trouve en encadrant le nombre de couleurs : un triangle donne le minorant, une coloration explicite le majorant. L'algorithme glouton offre une garantie simple, démontrée par récurrence.
Les questions probables du jury
Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.
Pourquoi un triangle impose-t-il 3 couleurs ?
Les trois sommets sont voisins deux à deux : ils doivent avoir trois couleurs distinctes.
Combien de couleurs pour un cycle de 5 sommets ?
3 : un cycle de longueur impaire ne peut pas être colorié avec 2 couleurs alternées.
Le glouton peut-il utiliser plus de couleurs que nécessaire ?
Oui, selon l'ordre de parcours ; il existe des graphes où un mauvais ordre utilise beaucoup trop de couleurs.
Que dit le théorème des quatre couleurs ?
Toute carte plane peut être coloriée avec 4 couleurs sans que deux pays voisins aient la même.
Quel est le degré de S dans l'exemple ?
3 : S est relié à M, P et H.
Les pièges qui coûtent des points
- Donner une coloration à 3 couleurs sans montrer qu'on ne peut pas faire avec 2.
- Croire que le glouton trouve toujours le minimum.
- Relier les épreuves sans élève commun.
Revoir les notions
Autres questions : graphes et réseaux
- Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
- Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
- Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
- Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
Préparer l'oral, pas seulement le contenu
Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.
Méthode : traiter une question de Grand oral →