Coloration de graphes dès l’école maternelle

samedi 27 juillet 2019
par  Alain BUSSER

Colorier un graphe, c’est donner une couleur à chacun de ses sommets. Une coloration est dite « propre » si des sommets adjacents ne sont jamais de la même couleur. L’exercice consistant à colorier proprement un graphe est relativement difficile intellectuellement mais abordable dès que les enfants commencent à percevoir les arêtes (en moyenne et grande sections selon les enfants et par épisodes).

Par exemple, il ne faut qu’une fraction de seconde pour vérifier que le graphe de Goldner-Harary a été correctement colorié :

Cela « saute aux yeux ». Mais pour obtenir cette coloration, cela a pris plusieurs minutes même en coloriant rapidement les sommets.

Par exemple voici le graphe de Goldner-Harary colorié en 5 couleurs, en 2 minutes, par une élève de CM1 :

Il y a du rouge, du bleu, du jaune, du gris et du marron : Cela fait bien 5 couleurs [1].

Le même graphe, colorié par un élève de CP (là encore en quelques minutes) :

Là encore on dénombre 5 couleurs : rouge, noir, magenta, cyan ... et le dernier sommet est resté blanc (c’est une couleur) faute de réussir à le colorier dans une des 4 couleurs précédentes : Il est adjacent à des sommets déjà coloriés dans les 4 couleurs en question.

Lorsque cela prend beaucoup moins de temps pour vérifier qu’une solution est bonne, que pour trouver une solution, le problème est dit NP [2]. L’exemple ci-dessus illustre donc le fait que colorier un graphe est un problème NP. Cela a été vu dans la dernière partie du sujet de Capes 2019. Mais la difficulté à résoudre ce problème n’est réelle que si on cherche à minimiser le nombre de crayons de couleurs utilisés.

Nombre chromatique du graphe de Goldner-Harary

Les deux élèves d’école primaire ont réussi à descendre à seulement 5 couleurs alors que le graphe comprend 11 couleurs. Beau score, mais en comptant les couleurs du premier exemple (rouge, vert, bleu, jaune) on en trouve encore moins, à savoir 4. Ceci dit, compter les couleurs prend encore beaucoup moins de temps que trouver comment colorier le graphe de Goldner-Harary en seulement 4 couleurs : Le problème reste NP.

Et en 3 couleurs ? Y a-t-il un moyen d’utiliser encore moins de crayons (se passer du jaune par exemple) pour colorier en 3 couleurs seulement ce graphe ?

La réponse est non, parce que dans le graphe de Goldner-Harary il y a un tétraèdre :

Or rien que dans cette partie du graphe, chaque sommet est adjacent à 3 autres sommets ce qui nécessite de n’utiliser chaque couleur que sur un seul de ces sommets : 4 couleurs sont nécessaires.

Cette activité permet aussi de découvrir l’énoncé du théorème des quatre couleurs : Pour colorier proprement un graphe planaire, 4 crayons suffisent (si on se débrouille bien).

Ceci n’empêche pas que dans certains cas (autres que le graphe de Goldner-Harary) on puisse aller encore plus bas, avec par exemple 2 crayons seulement [3] pour le graphe de Herschel :

Avec correction d’une erreur

Trop de précipitation nuit à l’attention et aboutit à un début de coloriage (en jaune) d’un sommet déjà adjacent à du jaune :

Graphes du poisson, de Hajos et de Frucht

Le graphe du poisson peut être colorié en 3 couleurs seulement :

Mais on ne peut pas descendre plus bas, parce que dans le graphe du poisson il y a un triangle :

Chacun des sommets de ce triangle est adjacent aux deux autres sommets et il faut donc autant de couleurs que de sommets du triangle, soit 3 couleurs. Comme la coloration en 3 couleurs a été réussie, cela prouve que le nombre chromatique du graphe du poisson est égal à 3.

Le graphe de Hajos présente beaucoup de symétrie ce qui aboutit plus ou moins automatiquement à une coloration en 3 couleurs, elle-même très symétrique (toujours en CP) :

Ce coloriage est en général fait assez rapidement. Et comme il y a des triangles dans le graphe de Hajos, on sait qu’on ne peut pas descendre en-dessous : Le graphe de Hajos est de nombre chromatique 3.

De même la présence de triangles dans le graphe de Frucht montre qu’on ne peut pas le colorier en moins de 3 couleurs. Mais en 3 couleurs exactement on peut (CP) :

Nombre chromatique du graphe de Moser

Voici une tentative ratée (en CP) pour colorier en seulement 3 couleurs le graphe de Moser :

En effet le dernier sommet non colorié est déjà adjacent à trois sommets de couleurs différentes, et nécessite une quatrième couleur (ici le blanc, c’est une couleur).

En coloriant en premier le sommet de plus haut degré [4]. (en gris, en haut) ça devrait aller mieux. Et bien non :

De fait, le nombre chromatique du graphe de Moser est 4, bien qu’il n’y ait pas de tétraèdre dans le graphe (les difficultés ne sont pas toujours locales).

Graphe de Bidiakis et prisme pentagonal

Bien qu’ilsne comprennent pas de triangles, le graphe de Bidiakis et le prisme pentagonal ne peuvent pas être coloriés en moins de 3 couleurs. Mais on peut colorier le cube de Bidiakis avec seulement 3 crayons :

Pour le prisme pentagonal ça ne marche pas :

Mais en s’y prenant autrement, si :

Pour finir en beauté, comme le dodécaèdre comporte des pentagones qu’il est impossible de colorier en moins de 3 couleurs, on a la preuve (CP) que son nombre chromatique est 3, en le coloriant avec seulement 3 crayons.

Apparemment ce n’est pas si facile quand on arrive à deux sommets adjacents qui ne peuvent être coloriés ni en vert ni en mauve :

Mais en s’y prenant autrement, on finit par y arriver :


[1Le dernier sommet a dû être colorié en rouge car il est déjà adjacent à des sommets bleus, jaune, gris et marron. Pour le bleu il faut bien regarder toutes les arêtes.

[2abréviation de Nondeterminist Polynomial, autrement dit un problème qui prend un temps long (typiquement exponentiel, en tout cas, pas molynomial) à être résolu, mais qui devient plus facile (polynomial) une fois qu’on introduit du nondéterminisme, ici incarné par un bout de chou qui pense avoir réussi la coloration et vient la montrer.

[3découverte récurrente des participants à la semaine des maths 2018, la fête de la science 2018 et la semaine des maths 2019

[4L’algorithme s’appelle DSATUR.


Portfolio

PNG - 70.8 ko PNG - 54.5 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Réunion de rentrée de l’IREM

- Mercredi 11 septembre 2019, 14h-18h, salle S23.6, PTU, Saint-Denis.

Séminaire de l’IREM

- Mercredi 9 octobre 2019, 14h-18h : campus du Tampon.
- Mercredi 6 novembre 2019, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 27 novembre 2019, 14h-18h : campus du Tampon.
- Mercredi 5 février 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 4 mars 2020, 14h-18h : campus du Tampon.
- Mercredi 8 avril 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.

Fête de la science

- Jeudi 14 novembre 2019 : campus du Moufia et IUT de Saint-Pierre.
- Vendredi 15 novembre 2019 : campus du Moufia et campus du Tampon.

Semaine des mathématiques

- Du 23 au 28 mars 2020.


Brèves

Nouveaux programmes pour la maternelle

mercredi 3 juin 2015

Les lecteurs attentifs des futurs programmes de la maternelle, qui rentreront en vigueur à la rentrée 2015, ont pu remarquer qu’ils reprennent les positions défendues par Rémi Brissiaud depuis des années sur la construction du nombre. Le site de la CFEM (Commission française pour l’enseignement des mathématiques) propose une page résumant le débat sur ce thème, avec deux contributions de ce chercheur.

thaMographe

mardi 30 décembre 2014

Le thaMographe, médaille d’or au Concours Lépine européen 2013, est un instrument pratique, peu cher, performant, qui remplace à lui seul les quatre outils usuels de géométrie (compas, règle graduée, équerre, rapporteur). De nombreuses écoles l’on mis sur leur liste de fournitures scolaires. Le site d’accompagnement contient des tutoriels pour une utilisation du primaire au post-bac.

Sur le Web : thaM thaM

Cellule de Géométrie

mardi 9 avril 2013

La Cellule de Géométrie (Haute École en Hainaut, Belgique) met à la disposition des professeurs des documents concernant l’enseignement de la géométrie de 5 à 18 ans. L’objectif est de permettre aux élèves de s’approprier progressivement et naturellement la démarche scientifique.

Sur le Web : Cellule de Géométrie

Artluxultra

samedi 20 octobre 2012

Artluxultra est un site d’art mathématique qui présente, sous un angle figuratif, les relations entre la géométrie, l’algèbre et la topologie.

Sur le Web : Artluxultra

Enigmath 2011

samedi 12 novembre 2011

Un Quizz de Mathématiques GRATUIT ne nécessitant que des connaissances élémentaires.

Les objectifs principaux sont de mettre en valeur auprès du grand public la place occupée par les mathématiques dans notre vie de tous les jours, et d’aborder des aspects de la recherche en mathématiques ou liés aux mathématiques, tout en permettant aux participants de s’évaluer sur des questions de mathématiques simples.

Sur le Web : Enigmath 2011

Statistiques

Dernière mise à jour

jeudi 5 septembre 2019

Publication

847 Articles
Aucun album photo
140 Brèves
11 Sites Web
145 Auteurs

Visites

954 aujourd'hui
1095 hier
2931693 depuis le début
65 visiteurs actuellement connectés