Rediffusion d’un article publié en 2018
Jeux sur graphes
Pista verde El 7 octubre 2021 Ver los comentarios (1)
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.
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.
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):
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:
Notas
[1] Le jeu des demoiselles, dans récréations mathématiques
[2] Expérience menée lors de la semaine des maths 2018 dans une école élémentaire REP+
[3] en 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.
[4] Les 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!
[5] Cet 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.
[6] Penser aussi à regarder «les énigmes de Col» pour s’occuper l’esprit pendant l’été.
[7] ayant 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.
[8] Si 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.
[9] Ce genre de jeu peut se jouer à la plage, avec un galet comme pion, et le graphe orienté dessiné sur le sable.
[10] Voir par exemple la page 2 de ce document.
[11] Pourtant un cycle peut permettre de changer de parité, en se retrouvant sur le même sommet mais avec les deux joueurs échangés.
[12] En serait-il de même si on dessinait des graphes à l’école?
[13] Le clic sur «récupérer un graphe» fait apparaître un rectangle titré «json» sur lequel il suffit de faire glisser le fichier.
[14] Il s’agit en fait d’une version simplifiée de l’algorithme de Sprague-Grundy
[15] La 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.
Comparte este artículo
Para citar este artículo:
Alain Busser — «Jeux sur graphes» — Images des Mathématiques, CNRS, 2021
Comentario sobre el artículo
Voir tous les messages - Retourner à l'article
Jeux sur graphes
le 12 de julio de 2021 à 15:53, par mariuslettres