De la planification horaire à la coloration, et même en lançant une pièce, ce morceau de mathématiques astucieux est la réponse, dit Katie Steckles
«Les graphiques… sont extrêmement efficaces pour modéliser des ensembles d'objets et les relations entre eux»
Récemment, un ami a demandé de l'aide avec un problème délicat: il organisait une pièce de théâtre, et le script avait un grand nombre de personnages. Ils ne voulaient pas embaucher un acteur pour chaque rôle, et bien qu'ils puissent doubler, ils rencontreraient des problèmes si le même acteur jouait deux personnages dans une scène.
Heureusement, j'étais la bonne personne à venir chercher de l'aide. Il y a un morceau de mathématiques qui est efficace pour résoudre de nombreux problèmes de ce type, de lancer un jeu à la planification du calendrier – et même de colorer.
Graphiques – Les réseaux de points rejoints par les lignes sont extrêmement efficaces pour la modélisation d'ensembles d'objets et les relations entre eux, avec des utilisations évidentes pour décrire des structures telles que les réseaux informatiques ou les routes entre les villes. Les mathématiciens sont souvent particulièrement intéressés par les propriétés des graphiques car ils nous disent quelque chose de plus sur la structure sous-jacente.
Une telle propriété est la coloration du graphique. Cela implique d'attribuer une couleur à chaque point, de sorte que deux points joints à une ligne se voient attribuer des couleurs différentes. Trouver le nombre minimum de couleurs nécessaires pour ce faire peut nous dire quelque chose d'utile sur la structure du graphique. Par exemple, un graphique avec un triangle de points tous joint à un quatrième point du centre aura besoin d'au moins quatre couleurs pour le remplir.
Une application est dans des problèmes impliquant une coloration réelle: étant donné une image divisée en régions connectées, existe-t-il un moyen de le remplir en utilisant uniquement un ensemble limité de couleurs, donc les régions adjacentes sont des teintes différentes? La preuve du théorème des quatre couleurs a confirmé que pour les diagrammes dessinés sur du papier, quatre couleurs au plus seront nécessaires. Ceux-ci correspondent à des graphiques qui peuvent être dessinés sur une page sans traversée de lignes.
Même si un graphique ne peut pas être dessiné sans traversées, nous pouvons toujours trouver le nombre minimum de couleurs nécessaires pour la remplir et l'utiliser pour résoudre les problèmes.
L'une de mes utilisations préférées de la coloration des graphiques est les problèmes de planification: imaginez un ensemble de classes, avec un ensemble partagé d'étudiants. Nous pouvons dessiner un graphique, indiquant chaque classe par un point, et rejoindre deux points si ces classes ont des élèves qui prennent les deux (donc ils ne peuvent pas se produire en même temps).
Ensuite, nous trouvons un moyen de colorer le graphique en utilisant le moins de couleurs possibles. Le nombre minimum de couleurs nous indiquera combien de créneaux horaires nous aurons besoin: chaque couleur représente un ensemble de classes sans chevauchement chez les étudiants, afin qu'ils puissent tous se produire simultanément.
Cela peut vous dire comment j'ai résolu le problème de mon ami: j'ai suggéré qu'ils dessinent un graphique, représentant chaque personnage avec un point, et rejoignent deux personnages avec une ligne s'ils apparaissaient dans des scènes ensemble. Colorer ce graphique au minimum, alors leur a dit exactement combien d'acteurs ils auraient besoin pour mettre en scène la pièce. Une autre victoire pour les mathématiques – avec le spectacle!
Katie Steckles est mathématicien, maître de conférences, Youtuber et auteur basée à Manchester, au Royaume-Uni. Elle est également conseillère pour la colonne de puzzle de Issues.fr, Brentwister. Suivez-la @Steck
Pour d'autres projets, visitez newscientist.com/maker
