Jeux sur graphes

Piste verte Le 22 novembre 2018  - Ecrit par  Alain Busser Voir les commentaires

Les graphes sont des objets mathématiques essentiels des mathématiques du XXIe siècle, une structure de donnée fondamentale pour appréhender le réel et accessibles de manière très élémentaire. Nous décrivons ici des activités dont l’objectif principal est de rendre ces objets plus familiers.

Depuis plusieurs années maintenant, des jeux sont proposés par l’IREM de La Réunion, dont certains portent sur des graphes.

Temps de lecture 30 minutes

Ces activités, adaptables à la classe du primaire (sur une séance ou deux), sont source d’images, dessinées ou coloriées de manière réfléchie par des enfants, les plaçant en tant que scientifiques suivant des règles logiques plutôt que dessinateurs. Cet article propose des exemples comme :

  • — la création de graphes orientés dans le cadre de jeux de type Nim ;
  • — le coloriage de graphes planaires pour le jeu de Col ;
  • — le coloriage de graphes planaires pour le jeu de Snort ;
  • — le calcul de degrés des sommets (activité arithmétique) pour les besoins de l’analyse des jeux.

Jeu de Col sur un prisme pentagonal

Sans rentrer dans les détails, cet article décrit également quelques outils techniques, pour l’enseignant, comme des logiciels utiles pour dessiner des graphes, supports d’activités de coloriage ludique et réfléchi.

Nous terminons sur des scénarios possibles d’utilisation en classe, de la fin de cycle 1 au cycle 3.

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 XIXe 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.

Du jeu vers la théorie

Ces activités sont des jeux, une fois les règles bien appliquées, il n’y a donc pas d’erreur mais un perdant, qui peut devenir gagnant avec un peu plus de recherche impliquant la logique élémentaire et la réflexion stratégique.

Ainsi donc, en jouant sur les graphes (ou en créant des graphes pour jouer dessus), des enfants parfois aussi jeunes que la Grande Section ont exploré des notions de théorie des graphes, qu’il ne s’agit bien sûr pas d’expliciter, comme

La notion de degré apparaît par exemple pour l’analyse de ce jeu où l’un des joueurs (les « chiens ») doit bloquer l’autre (le « tangue » ou tenrec ecaudatus) :

En effet, comme aucun sommet du graphe du jeu n’a un degré inférieur à 3, il est impossible aux chiens de bloquer le tangue s’ils ne sont que 2.

Parfait exemple d’une notion arithmétique apparue par nécessité (pour analyser les jeux), le degré permet, en cycle 3, de donner des exercices (ou jeux ?) consistant à donner les degrés des sommets d’un graphe sans arêtes dessinées, et demander de reconstituer le graphe, c’est-à-dire dessiner les arêtes manquantes.


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.

Jeu de Snort sur ordinateur

Ce jeu de Snort, joué sur Nirina974, montre que le jeu peut être considéré comme un jeu de stratégie, plus précisément de conquête de territoire :

Sachant que ce sont les bleus qui ont joué en premier, qui a gagné la partie ?

On peut aussi imaginer, dans le cas où le graphe ressemble à une grille, un habillage où ce sont les conflits qu’il s’agit d’éviter en préservant une zone vide, comme dans ce jeu où on cherche à éviter des réactions chimiques dangereuses.


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.

De Nim vers les graphes

Pour jouer à un jeu similaire à Nim, on peut déplacer sur le graphe du jeu un pion représentant la phase courante du jeu. L’habillage obtenu pour le jeu s’appelle parfois Geography mais Aviezri Fraenkel préfère parler de « Nim » [10].

Du coup, pour inventer un jeu de type Nim, il suffit de créer un graphe ayant les propriétés suivantes :

  • il doit être orienté ;
  • il doit comporter au moins un sommet d’où ne parte aucune arête (son degré sortant doit être nul), appelé « arrivée » dans la suite : Le but du jeu est en effet d’être le premier à mener l’unique pion à une arrivée ;
  • il doit comporter un unique sommet, appelé « départ », de degré entrant nul (aucune arête ne doit y mener) qui sera l’emplacement où on pose le pion au début du 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.

La version Nirina974

L’application Nirina974 est un outil très simple en ligne de construction de graphes sur ordinateur :
On clique dans le vide pour créer un sommet, on control-clique pour le déplacer, on clique-glisse pour créer une arête.

En cliquant sur le lien graphes orientés on peut, à l’aide du bouton « Récupérer un graphe », charger [13] le graphe ci-dessous :

JSON - 7.7 ko

Le coloriage a été fait en cliquant sur le bouton « triche » (un peu caché, exprès !) et le résultat, exporté par un clic sur le bouton « svg », est ceci :

Une fois le graphe créé, on peut jouer en cliquant sur jouer, ce qui a pour effet de placer un pion noir sur le départ. Les joueurs s’appellent A et B, et le nom du joueur courant est affiché en haut de la page. Pour déplacer le pion, on clique sur une des arêtes adjacentes à sa position actuelle.

La version Python

Cette version est très impressionnante pour le non initié, fermez vite ce bloc si cela vous fait peur :

from graphviz import *

g = Digraph(format='svg')

for n in range(1,12):
        g.node(str(n),' ',shape='doublecircle')
       
g.edge('1','2')
g.edge('2','3')
g.edge('1','3')
g.edge('3','4')
g.edge('1','4')
g.edge('4','5')
g.edge('4','6')
g.edge('4','7')
g.edge('5','6')
g.edge('6','7')
g.edge('3','7')
g.edge('3','11')
g.edge('7','8')
g.edge('8','9')
g.edge('9','10')
g.edge('8','10')
g.edge('10','11')

g.render('grafe4',view=True)

Si vous n’avez pas refermé ce bloc, vous êtes assez aventureux⋅se pour tenter de comprendre la signification de ce code : on utilise la bibliothèque graphviz et on commence par dire qu’on va créer un graphe orienté (« digraph ») qu’on voudra exporter au format SVG. Dans la première boucle on prépare ensuite 12 sommets (« node »), nommés par leur numéro de 1 à 12, rendus par un double cercle. Puis on renseigne l’adjacence des sommets en listant les arêtes (« edge ») une à une, du nom d’un sommet au sommet adjacent, à la main. Enfin, on fait dessiner (« render ») le graphe. Il est à noter que les traductions anglaises des mots sommet, arête etc., ne troublent pas vraiment plus les enfants, que les mots français correspondants.

Si vous voulez interpréter ce code, il vous faut installer Python et le module graphviz sur votre ordinateur et un éditeur de programme comme Pyzo.

L’exécution de ce programme produit le dessin suivant :

sur lequel le coloriage en rouge et vert ci-dessous a été effectué (le graphe original ayant été soigneusement colorié, comme on peut le voir ci-dessus, par sa créatrice).

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.

La stratégie gagnante

Chaque graphe étant fini, il existe forcément une stratégie gagnante ou des échecs. Pour notre problème, l’expliciter sans énumérer toutes les configurations possibles est cependant possible.

Tout d’abord il est possible de colorier ainsi tous les sommets du graphe orienté, en commençant par l’arrivée qui est en vert puisque le but du jeu est d’y mener le pion. L’algorithme est récursif, mais converge parce que le nombre de sommets à colorier est fini, et que le graphe est acyclique.

Ensuite, il n’est pas possible de voler la stratégie de celui qui l’applique : par construction, si je viens de mener le pion vers un sommet vert, mon adversaire ne peut à son tour le mener que vers un sommet rouge. Et une fois que c’est fait, je peux à mon tour mener le pion jusqu’à un sommet vert, puisque par construction, il en existe un qui est accessible depuis le sommet rouge.

Mais au fait, quelle est-elle, la stratégie ? « Toujours mener le pion vers un sommet vert ».

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) :

Post-scriptum :

L’article sous sa forme actuelle est la conséquence de propositions et encouragements des relecteur-trice-s suivant⋅e⋅s : Sylvia, François Sauvageot, Véronique Vanackère, Jean Aymes et Philippe Levallois. Des améliorations importantes ont été faites directement dans le corps de l’article par l’éditeur (voire coauteur, à ce point-là !) Christian Mercat. Merci à tou⋅te⋅s !

Les graphes en sortant de l’école ont déjà été traités :

Pour en savoir plus, voir :

Article édité par Christian Mercat

Notes

[1Le jeu des demoiselles, dans récréations mathématiques

[2Expérience menée lors de la semaine des maths 2018 dans une école élémentaire REP+

[3en collège on a matérialisé un réseau social en demandant à ses sommets de se tenir par la main s’ils le pouvaient pour matérialiser les arêtes du graphe/réseau. Il s’agissait d’un graphe non orienté comme le sont tous les réseaux sociaux.

[4Les enfants ayant découvert expérimentalement le théorème des 4 couleurs entrent immédiatement dans ce jeu. Ils sont en effet habitués à la contrainte de ne pas donner la même couleur à deux sommets adjacents, et certains l’inventent même !

[5Cet habillage peut d’ailleurs être reconduit sur un graphe de plusieurs mètres de diamètre, initialement inoccupé, et une équipe de filles jouant contre une équipe de garçons : Lors du premier coup, une des filles se positionne sur un sommet du graphe, et n’en bougera plus jusqu’à la fin du jeu. Ensuite un des garçons se met sur un sommet du graphe, non adjacent à un sommet occupé par l’équipe adverse, et ainsi de suite jusqu’à ce que l’une des équipes ne puisse plus jouer sans aboutir à l’adjacence entre une fille et un garçon. Cette équipe a alors perdu. Même joué par des adultes ce jeu est hilarant. Et le choix du sommet à occuper, proposé par le-la capitaine de l’équipe puis débattu avant de jouer, impose une verbalisation.

[6Penser aussi à regarder « les énigmes de Col » pour s’occuper l’esprit pendant l’été.

[7ayant eu lieu peu après la victoire de la France à la coupe du monde de football, mais l’apparence bleu-blanc-rouge obtenue finalement est typique des fins de parties de Snort, et n’a rien à voir avec un quelconque élan patriotique ; d’ailleurs le premier joueur joue cyan et non bleu.

[8Si cela pose un problème de budget, on peut en faire tirer moins et au lieu de colorier vraiment un sommet en rouge, l’enfant mettra un jeton rouge sur le graphe qui pourra alors resservir. Mais il faut que les enfants comprennent qu’alors le jeton ne devra plus bouger une fois posé, c’est une difficulté supplémentaire.

[9Ce genre de jeu peut se jouer à la plage, avec un galet comme pion, et le graphe orienté dessiné sur le sable.

[10Voir par exemple la page 2 de ce document.

[11Pourtant un cycle peut permettre de changer de parité, en se retrouvant sur le même sommet mais avec les deux joueurs échangés.

[12En serait-il de même si on dessinait des graphes à l’école ?

[13Le clic sur « récupérer un graphe » fait apparaître un rectangle titré « json » sur lequel il suffit de faire glisser le fichier.

[14Il s’agit en fait d’une version simplifiée de l’algorithme de Sprague-Grundy

[15La pose de jetons au lieu de vrai coloriage permet de corriger les erreurs de « calcul ». Ceci dit, il semble que dès l’âge de 7 ans, un enfant gère assez remarquablement les hypothèses imbriquées du genre « si A joue ceci alors si B joue cela alors ... » ; mais pour s’en rendre compte il faut permettre à l’enfant de « mettre un haut-parleur sur sa pensée » ce qui nécessite des effectifs réduits ou des passages au tableau dans la phase de verbalisation.

Partager cet article

Pour citer cet article :

Alain Busser — «Jeux sur graphes» — Images des Mathématiques, CNRS, 2018

Crédits image :

Image à la une - Les photos illustrant cet article proviennent du site de l’IREM de La Réunion. Les créateurs des graphes sont en général trop jeunes pour qu’on puisse donner leur nom.
Jeu de Col sur un prisme pentagonal - IREM La Réunion
img_18835 - Alain Busser 2018

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM