À taaable !

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 avec quelqu’un 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.