Les graphes en moyenne et grande sections

Fête de la science 2020 à l’école Aristide Briand
samedi 21 novembre 2020
par  Alain BUSSER

Que ce soit en Grande Section ou en Moyenne Section, la classe a été divisée en 3 groupes de 8 élèves, qui ont passé 20 minutes sur chacune des activités suivantes :

  • Jeux à deux joueurs (déplacement de pions sur le graphe)
  • Coloriage de graphes
  • Dessin de graphe (création)

pour un total d’une heure, chaque élève ayant donc eu l’occasion de tester les trois activités.

En cycle 2 aussi on peut jouer sur des graphes

Pendant que les élèves de moyenne et grande sections jouaient sur des graphes « papier » dans leur salle de cours, les élèves de CP puis de CE1 ont décodé des messages binaires sur l’automate décodeur de Huffman.

Ici deux élèves de CP décodent un message binaire sous le regard bienveillant des élèves de l’Alefpa.

Certains messages binaires à décoder étaient écrits sur des bandes de papier :

Pour décoder un message binaire, on parcourt à pied l’automate. Cela amène à verbaliser :

et surtout cela aide à apprendre par engagement corporel total. Les élèves (et leurs enseignants semble-t-il) ont adoré l’animation, et se sont déplacés à plusieurs en même temps sur le graphe :

Il y en a même qui ont inventé leur propre variante de la marelle, sur ce graphe :

Deux critiques d’une enseignante :

  1. un seul automate, c’est largement insuffisant pour une classe entière
  2. 45 minutes, c’est trop court pour une classe entière.

Il faut reconnaître que la promesse d’un effectif maximum de 12 en CP n’est pas encore une réalité à l’école Aristide Briand...

Durant l’année scolaire 2020-2021, des ressources seront mises au point par l’Alefpa : un descriptif du kit permettant à tous les enseignants désireux de tester l’activité, de reproduire le kit sans nécessiter la visite de l’Alefpa (et en plus, en plusieurs exemplaires par classe), et une fiche d’activités réalisables avec le kit.

Voici les activités menées en grande section :

Vocabulaire

En montrant quelques graphes aux élèves, on leur présente les mots suivants :

  • graphe (l’objet montré)
  • sommet (les cercles représentés)
  • arête (un trait entre deux sommets)
  • adjacents (sommets entre lesquels se trouve une arête).
  • théorème (à propos de celui des 4 couleurs, dont l’énoncé est compréhensible en GS [1].

Le simple fait de compter les sommets et les arêtes d’un graphe, suffit déjà à rendre cet objet mathématique plus familier.

Jeux

La collection de jeux de l’IREM est riche en graphes dont une sélection de 4 a été effectuée (4 jeux à deux joueurs occupent 8 élèves) :

dans ce jeu [2], il faut 3 pions par joueur, le but du jeu étant de mener ses trois pions en face. Le jeu du fer à cheval se joue avec deux pions par joueur. Ils sont posés puis glissés. Ce jeu nécessite un pion (le tangue) pour un joueur, et 3 pions (les chiens) pour l’autre joueur. Ce jeu se joue avec un seul pion, partagé entre deux joueurs [3].

Coloriage

Pour colorier un graphe, il faut un graphe, et des crayons de couleur.

Colorier un graphe, c’est colorier ses sommets (les cercles). La seule restriction est que l’on ne veut pas que deux sommets adjacents soient de la même couleur. Par exemple, ce coloriage de graphe comporte une erreur : les deux sommets rouges en haut à droite, sont adjacents :

Autres erreurs

Ici ce sont les sommets mauves qui sont adjacents :

Ici ce sont les deux sommets oranges (les deux sommets du haut sont dans des nuances de roses différentes et ne sont donc pas en erreur) :

Ici ce sont les sommets oranges (cela ne saute pas aux yeux qu’ils sont adjacents, car l’arête les joignant n’est pas rectiligne) :

Ici également ce sont les sommets oranges qui sont adjacents :

Ici c’est plus intéressant : en réalisant que les deux sommets mauves sont adjacents, une élève a commencé à recolorier l’un d’entre eux en rouge... pour ensuite se rendre compte qu’il est déjà adjacent à un sommet rouge :

Une mésaventure similaire est arrivée ici : en voyant que deux sommets cyans sont adjacents, une tentative a été faite, de colorier l’un d’entre eux en bleu, pour ensuite remarquer qu’il est déjà adjacent à un autre sommet bleu :

Le coloriage peut être mené à deux en même temps, du moment qu’on est bien synchronisés :

Dodécaèdre

Le coloriage du dodécaèdre (20 sommets) occupe pendant un bout de temps.

Mais certains élèves y arrivent seuls.

Ceci dit, ce coloriage a nécessité 9 crayons, alors qu’on pouvait y arriver avec seulement 3 crayons.

Avec deux crayons

Le graphe de Herschel qui comporte 11 sommets, peut être colorié avec bien moins que 11 crayons : E. qui colorie avec aisance, s’est vu lancer le défi de n’utiliser qu’un crayon bleu et un crayon rouge pour colorier ce graphe. Il a d’abord commencé par observer le graphe sans toucher aux crayons, puis a démarré tranquillement le coloriage :

On est tenté, à ce stade, de penser qu’il a déjà la solution. En tout cas, il semble avoir compris qu’il y a une solution. Cette impression qu’il sait ce qu’il fait, reste présente au cours du coloriage :

Avant même le coloriage du dernier sommet, il semble évident que E. sait comment il va colorier le dernier sommet, et qu’il sait qu’il a réussi :

Il faut dire que E. a manifesté un vif intérêt pour les graphes en général, et il a dit avoir aimé les trois activités (création, coloriage et jeux). C’est la première fois qu’un élève de l’école maternelle réussit à colorier un graphe avec seulement deux crayons. Félicitations à E. pour cet exploit.

Création

Le plus intéressant est de voir à quoi ressemble un graphe créé par un enfant.

On copie l’exemple du tableau

ou on s’en inspire

Ce dessin est décrit par sa créatrice comme celui de 3 graphes (connexes) et non un graphe ayant 3 composantes connexes. La notion de connexité semble attribuée de facto à tous les graphes, en GS.

Mais la planarité n’est pas automatique en GS.

Les multigraphes aussi ont la cote en GS :

Une variante a consisté à colorier les arêtes du graphe :

Avec numérotation des sommets

Le meilleur moyen pour savoir combien le graphe a de sommets, c’est de numéroter ces derniers.

En moyenne section aussi, les activités ont eu du succès. Mais avec des phénomènes qui n’étaient pas apparus en grande section.

Jeux

Si on définit le verbe « jouer » comme une action effectuée sur le plateau de jeu (comme bouger un pion), alors un joueur passe l’essentiel de son temps à ne pas jouer : il attend que l’autre joueur ait joué son coup pour chercher quoi faire ensuite. Par exemple, au jeu des deux parkings :

pendant qu’un joueur réfléchit à ce qu’il va faire (et avec lequel de ses trois pions), normalement, l’autre joueur ne fait qu’attendre qu’il ait fini son mouvement, avant de commencer à réfléchir à son tour, à la riposte.

Mais pas en MS, où souvent les deux joueurs bougent les voitures dans tous les sens et simultanément. Ce qui mène à des protestations (« il fait que tricher ») et à une intéressante verbalisation (signification du verbe tricher, rappel de la règle du jeu par les élèves...).

Finalement, le jeu le plus facile à apprendre a été celui de Nim, parce que comme il n’y a qu’un seul pion, l’autre joueur est forcé d’attendre son tour, ne serait-ce que pour pouvoir prendre le pion :

Coloriage

Les meilleurs exemples sont visibles dans le port-folio en bas de l’article : ce sont des coloriages effectués par des élèves de GS/MS.

graphe du poisson

Remarque d’une élève de GS : il manque les écailles et les branchies 🤣.

En seulement 4 couleurs (le minimum possible est 3) :

En 5 couleurs :

Il n’y a pas d’erreur, les deux teintes de rouge sont différentes :

En travail collaboratif :

Graphe de Hajos

En 5 couleurs (le minimum est 3) :

La coloration avec un minimum de couleurs a été réussie par un autre élève (« il faut colorier pareil en face ») de GS :

Graphe de Herschel

Le graphe de Herschel (qu’il est possible de colorier en seulement 2 couleurs, comme l’a prouvé E. en GS -voir plus haut) a donné lieu à des erreurs de coloriage. Il faut dire qu’il comporte 11 sommets.

Ici deux sommets rouges sont adjacents :

Et ici ce sont deux sommets bleus qui sont adjacents :

Une bonne manière de colorier un graphe sans erreur, est d’utiliser un crayon par sommet (mais là on est loin du minimum). Avec le graphe de Goldner cela nécessite 11 crayons, alors on est tenté d’essayer avec moins de crayons. Malgré cela, il y a eu une erreur de coloriage :

En effet, le sommet à gauche est rose, comme celui du centre. Ou plutôt, était : la colorieuse a corrigé le tir en ajoutant du bleu, comme elle le montre :

La même technique a été utilisée sur le dodécaèdre ci-dessous, où le sommet du haut, initialement en rouge (alors qu’il est adjacent à un sommet rouge) a été repassé en noir :

Des erreurs qui n’en sont pas

Ici les deux teintes de rose en bas à droite sont différentes, il n’y a donc pas d’erreur :

Par contre il n’y a pas non plus optimisation : 3 couleurs auraient suffi.

Ici ce sont les sommets noir et marron en bas à gauche qui se ressemblent, mais il n’y a pas d’erreur :

Par contre il est possible de colorier ce graphe avec seulement 3 crayons.

Création

La créativité semble plus présente en MS qu’en GS.

Un multigraphe :

Connexité

En MS comme en GS, on considère que tout graphe est connexe, et les dessins ci-dessous ne sont pas considérés comme des graphes ayant plusieurs composantes connexes, mais comme des dessins de plusieurs graphes.

Les graphes à colorier sont disponibles dans cet article.

Pour en savoir plus, ne pas hésiter à consulter ce livre : Jeux et graphes 🤣.


[1Ce qui met sur un pied d’égalité les élèves de GS et les étudiants de l’université : dans les deux cas, on comprend facilement l’énoncé du théorème des 4 couleurs, mais on est totalement incapable de comprendre la preuve de ce théorème.

[2d’ailleurs créé par une ancienne élève de l’école Aristide Briand

[3En GS, les plus rapides se sont vus proposer la variante suivante :

Nim sur rectangle

Portfolio

JPEG - 88.2 ko JPEG - 76.4 ko JPEG - 66.1 ko JPEG - 105.2 ko JPEG - 82.1 ko

Commentaires