Cet atelier permet aux élèves de découvrir la notion de coloration de graphes et son intérêt pour la modélisation.

On commence par une activité grandeur nature. Chaque élève reçoit un prénom et une liste de personnes avec qui il ou elle ne veut absolument pas être assis·e à table. Objectif : faire le plan de table de sorte à ce que personne ne soit assis·e avec quelqu’un·e qu’il ou elle n’aime pas.

Ensuite, les élèves travaillent sur la représentation de ce problème pour arriver à la modélisation de celui-ci en termes de coloration de graphes. Mais comment colorer un graphe de sorte que deux sommets reliés par une arête ne soient pas de la même couleur ? Est-ce possible ? Avec combien de couleurs ? Existe-t-il des algorithmes qui permettent de le faire efficacement ?

Vous trouverez ici le déroulé complet de l’activité prévue pour durer 1 h 15 ainsi que tout le matériel nécessaire à imprimer :

Télécharger le déroulé détaillé de l’atelier

Télécharger l’ensemble des documents à imprimer et les diaporamas

Contact : nina.gasking@ens-lyon.fr

Cette activité a été créée par Eric Duchêne, Aline Parreau et Nina Gasking.

Cet atelier est mis à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale – Partage dans les Mêmes Conditions 4.0 International.