La notion de graphe est la base de nombreuses notions mathématiques fondamentales (relations, mathématiques discrètes, topologie), formalisant les notions de voisinage, d’ordre, de connexité: deux sommets sont voisins s’ils sont reliés par une arête d’un graphe non orienté, un sommet précède un autre s’ils sont reliés par une arête orientée, la composition d’arêtes en chemins permet de connecter ses sommets. Dans un réseau social par exemple, les sommets représentent les personnes, et deux sommets sont adjacents si les personnes représentées par ces sommets, sont amies. Les réseaux électriques, internet, fluviaux, aériens, routiers, ferroviaires, etc. étant modélisés par des graphes, cette notion se prête remarquablement à l’abstraction. Et Édouard Lucas qui dès la fin du XIX^e siècle créait et analysait des jeux sur ce qu’il appelait réseaux, avait même utilisé des graphes pour modéliser les rondes des enfants de l’école maternelle [1]!

Les enfants dès la grande section s’approprient rapidement [2] le vocabulaire qui remplace ou précise celui des dessins habituels, de ronds et de traits afin de formaliser les règles qu’on introduit quand il y en a besoin:

• les objets dessinés en rond s’appellent les sommets du graphe;
• les traits entre les sommets s’appellent les arêtes du graphe;
• lorsqu’une arête joint deux sommets, on dit que ces sommets sont adjacents;
• le nombre d’arêtes se rencontrant en un sommet s’appelle le degré du sommet;
• le plus petit nombre de couleurs dont on a besoin pour colorier un graphe en respectant la règle du jeu s’appelle le nombre chromatique du graphe.

On peut très bien rentrer dans les activités sans introduire le vocabulaire mais changer de mots permet de changer de regard sur l’objet, qui d’un dessin devient un graphe [3]. L’objectif principal de ces jeux est de rendre plus familière cette structure de données si fondamentale aux mathématiques contemporaines et d’en explorer quelques propriétés de base émergeant de ces jeux, faisant travailler la logique élémentaire. Parmi les compétences développées on peut citer la vision dans le plan, la reconnaissance des formes (lignes, cercles, flèches), le raisonnement hypothético-déductif, le comptage, la planification, le repérage dans l’espace, la perception des aires et des couleurs, la pensée algorithmique et l’abstraction. L’étendue des concepts qu’on peut modéliser à l’aide des graphes est très large, le langage par exemple est éclairé par la notion de réseau sémantique.

Énumérer les éléments d’un graphe, le nombre de sommets ou d’arêtes, le degré des sommets, est une activité en soi intéressante, en particulier si le sommet n’est pas planaire (polyèdre par exemple), l’enfant devant développer une stratégie d’énumération, dont on peut graduer la difficulté en autorisant ou pas à marquer les sommets/arêtes déjà énuméré(e)s, à manipuler ou pas l’objet. Ces activités d’énumération peuvent ou non accompagner, préparer ou réinvestir les activités de jeu décrites ici.

Col et Snort

L’intérêt porté par les enfants à la coloration de graphes (en jouant à Nim, voir plus bas) a mené à une expérimentation sur des jeux de coloriages de graphes, les jeux de Col et Snort avec des règles différant légèrement selon le jeu choisi parmi ces deux. Dans les deux cas, chaque joueur (traditionnellement appelés «Bleu» et «Rouge») colorie un sommet actuellement blanc dans sa propre couleur, mais:

• dans Col, il ne faut pas que deux sommets adjacents soient de la même couleur [4];
• dans Snort, il ne faut pas au contraire que deux sommets adjacents soient de couleurs différentes.

Pour jouer à Col ou Snort, il faut un graphe non orienté et non encore colorié. Chaque joueur a son propre crayon de couleur et le mot «adjacent» a été expliqué brièvement aux élèves avant de jouer.

Règle de Col

Le joueur qui a le crayon bleu commence. Il colorie en bleu un des sommets de son choix. Ensuite c’est au tour du joueur ayant le crayon rouge de jouer, il colorie un des sommets restants en rouge. Puis le joueur aux crayons bleus colorie un des sommets restants en bleu, et ainsi de suite. Mais il ne faut jamais colorier un sommet dans la même couleur qu’un des sommets voisins (auxquels il est adjacent).

Le premier qui ne peut plus jouer (parce que tous les sommets blancs sont adjacents à un sommet de sa couleur, et que c’est à son tour de jouer) a perdu le jeu.

Règle de Snort

Le joueur qui a le crayon bleu commence. Il colorie en bleu un des sommets de son choix. Ensuite c’est au tour du joueur ayant le crayon rouge de jouer, il colorie un des sommets restants en rouge. Puis le joueur aux crayons bleus colorie un des sommets restants en bleu, et ainsi de suite. Mais il ne faut jamais qu’un sommet rouge et un sommet bleu soient adjacents.

Le premier qui ne peut plus jouer (parce que tous les sommets blancs sont adjacents à un sommet de la couleur de son adversaire, et que c’est à son tour de jouer) a perdu le jeu.

Le nom de Col est à la fois une allusion au nom de son créateur (Colin Vout) et au fait qu’il s’agit d’un jeu de coloriage. Le nom de Snort est également une double allusion:

• au nom de son créateur Simon Norton;
• à un habillage agricole. Dans la version initiale deux éleveurs se partageaient un ranch en plaçant des vaches et des taureaux, tout en préservant la chasteté nécessaire [5]. Or les ruminants commençaient par se renifler (to snort) s’ils étaient trop proches les uns des autres ...

Les plus jeunes joueurs s’étant affrontés dans ces jeux (de coloriage, pas de reniflage) étaient en Moyenne Section. Par exemple la photo qui ouvre cet article montre une partie de Col entre élèves de Grande Section (on constate d’ailleurs avec quel soin ils colorient). De belles réalisations sont visibles dans cet article [6].

Les plus jeunes joueurs ont parfois tendance à se tromper, en coloriant par erreur un sommet qui leur était interdit (adjacent à un sommet de sa propre couleur dans Col, à un sommet de la couleur adverse dans Snort). Dans ce cas, les enfants conviennent spontanément que celui qui a commis l’erreur est perdant du jeu («tu as triché donc j’ai gagné»).

Voici un jeu de Snort [7]:

Saurez-vous deviner

• quel est le joueur qui a joué en premier ?
• qui a gagné le jeu?

Quant à l’âge du capitaine plus jeune joueur (les rouges), c’est 6 ans, comme on peut le deviner à sa calligraphie.

Comment puis-je faire jouer mes élèves à Col?

• La première étape est de dessiner (soi-même, à l’aide des logiciels ci-dessus, ou par les élèves) un ou plusieurs graphes planaires. On peut aussi simplement télécharger ceux qui sont dans le bloc «ressources» tout en bas de cet article.
• Ensuite il faut en faire tirer environ autant d’exemplaires que l’on a d’élèves à faire jouer [8].
• Enfin, pour ce qui est du matériel, il faut un crayon de couleur par joueur.

Il faut prévoir plusieurs parties pour que les enfants ne se trompent plus dans le coloriage et pour partager les graphes coloriés obtenus; en effet il arrive souvent que des joueurs veuillent garder le résultat, dont ils apprécient la beauté, et deux joueurs doivent parfois choisir lequel des deux pourra garder le jeu.

Les énigmes de Col et Snort

Les questions posées ci-dessus (qui a joué en premier? Qui a perdu le jeu?) sont des exercices intéressants à mener. Par exemple on peut récupérer des parties terminées par des élèves d’une autre classe (ou les scanner pour les vidéoprojeter) puis les soumettre aux élèves en groupe et leur poser ce genre de questions, les amenant ainsi à verbaliser leur raisonnement. De toute manière, dès la fin du jeu, une question assez naturelle est «J’ai perdu mais aurais-je pu gagner?» et tenter d’y répondre peut mener à un travail de recherche avec analyse des différents cas, initiant ainsi les élèves à la recherche scientifique.

Il est à noter à ce propos que les jeux de Col et Snort sont liés à des problèmes ouverts, notamment de recherche de stratégie gagnante (on n’en connaît pas à l’heure actuelle).

Théorème des quatre couleurs

Il faut quelques minutes pour familiariser un élève de cycle 2 ou 3 au vocabulaire sommet-arête-adjacence-degré-nombre chromatique et le fait que ce soient uniquement les sommets d’un graphe qu’on colorie (plutôt que les régions sur une carte) permet de mener l’activité assez rapidement (typiquement moins d’une demi-heure avec un groupe d’une dizaine d’élèves) pour apprendre à colorier:

• les sommets (et non les faces du graphe) sans trop déborder, en Petite Section;
• en respectant la consigne de ne pas colorier de la même couleur deux sommets adjacents, en Grande Section;
• en minimisant le nombre de couleurs (atteindre le nombre chromatique du graphe) dès le CP.

Par exemple, lors de la semaine des maths, il a été demandé à des élèves de 4e, de dessiner à la craie, puis colorier, un graphe de nombre chromatique 3, puis 4, puis 5, en quelques minutes. L’impression qu’ils ne pouvaient pas réussir avec 5 couleurs est vite apparue, même s’il n’était pas question de leur demander de prouver le théorème des quatre couleurs! Dans le contexte présent, le théorème peut s’énoncer ainsi:

Pour colorier n’importe quel graphe planaire (sans croisement des arềtes) de manière que jamais deux sommets adjacents ne soient de la même couleur, quatre crayons suffisent.

Jeux de Nim

Le jeu de type Nim sur un graphe orienté nécessite de particulariser deux sommets, le «départ» où on pose en premier le pion et l’«arrivée» coloriée; ensuite chaque joueur à son tour déplace le pion [9] depuis le sommet où il se trouve jusqu’à un sommet adjacent, en suivant le sens de la flèche. Celui qui mène le pion à une arrivée gagne le jeu.

La pratique de cette activité a mené à deux constatations:

• la plupart des enfants ont du mal à voir et concevoir les graphes non planaires et les graphes qu’ils créent sont en général planaires (voir exemple ci-dessous), un sommet est naturellement le lieu où deux traits se rencontrent sur le papier;
• si le graphe orienté comporte un cycle, on court le risque que la partie dure un temps infini et les cycles sont rapidement évités par les jeunes créateurs de graphes [11].

Ces constatations ne sont pas des problèmes en soi, il est naturel de jouer sur des graphes planaires et de bannir les cycles, et s’en tenir là, ces notions abstraites ne sont pas des visées de cette activité mais peuvent apparaître comme questionnements. On peut attendre le collège pour aborder l’existence de graphes non planaires par exemple en jouant à Planarity.

Dessiner un graphe comme un jeu

Créer un graphe est si ludique qu’il arrive parfois un miracle: le simple dessin d’un graphe orienté, pour peu qu’on le contraigne à quelques propriétés, est en lui-même considéré comme un jeu [12]. Dans le cadre d’un atelier IREM, a ainsi été développé un outil en ligne très simple d’aide à la création de graphes: ce logiciel décrit dans la suite et que vous pouvez utiliser pour construire vous-même de jolis graphes à imprimer pour votre classe.

Voici un graphe orienté créé pour jouer avec un unique pion dessus:

Dessiner de manière agréable et sans ambiguïté ce graphe n’est pas forcément évident. Deux petits logiciels, l’un interactif en ligne, l’autre textuel en Python, permettent de fabriquer une image numérique (au format SVG) qu’on peut ensuite utiliser, après impression puis éventuelle plastification, pour jouer plusieurs fois sur le même graphe.

Sur ce graphe précis, trouver une stratégie gagnante n’est pas très difficile. Mais un algorithme existe pour en trouver sur n’importe quel graphe, en coloriant le graphe [14]; on colorie en vert les sommets où on veut mener le pion, car ils sont gagnants:

• si au moins une arête issue d’un sommet va vers un sommet déjà colorié en vert, je colorie ce sommet en rouge (le feu est rouge car je ne veux pas y aller, en effet je perdrais le jeu en laissant mon adversaire aller vers la case verte);
• à l’inverse, si aucune arête issue d’un sommet ne va vers un sommet vert, je colorie ce sommet en vert: le feu est vert pour moi, puisque pour mon adversaire il n’y a que des feux rouges.

L’algorithme décrit ainsi est récursif, notion peu accessible à de jeunes enfants, mais le départ du coloriage est facile à verbaliser: L’arrivée (ou les arrivées) ne menant à aucun sommet vert (puisqu’elle ne mène à aucun sommet), est coloriée en vert. C’est le point de départ du coloriage.

Colorié par sa créatrice [15], le graphe montre l’existence d’une stratégie gagnante pour celui qui joue en premier (depuis le départ):