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