Une entreprise souhaite transporter six produits chimiques différents mais certains ne peuvent pas voyager ensemble, à cause du risque d’explosion. Combien de wagons seront nécessaires pour que les produits incompatibles puissent être convoyés séparément ? Quelques crayons de couleur et un peu de méthode permettent de résoudre ce problème !
Il s’agit de convertir le problème en une figure géométrique, composée d’arêtes et de sommets, que l’on nomme un graphe. Ici, les sommets représenteront les produits chimiques et les arêtes relieront les produits incompatibles.
On essaie ensuite de colorier les sommets de sorte que deux sommets reliés possèdent des couleurs différentes. Ça semble facile, mais il s’agit pour cela d’utiliser le moins de couleurs possibles ! On obtient alors le « nombre chromatique », soit le plus petit nombre de couleurs permettant de résoudre le graphe. Dans notre cas, ce nombre représentera le nombre de wagons nécessaires.
Il est temps de passer à la pratique !
Prenons six produits chimiques différents que l’on nommera P1, P2, P3, P4, P5 et P6. Sachant que…
– P1 ne peut être transporté avec P2 et P3
– P2 ne peut être transporté avec P1, P3 ou P5
– P3 ne peut être transporté avec P1, P2, P4
– P5 ne peut être transporté avec P2 ou P6
La première étape du raisonnement consiste donc à réaliser le graphe de cette situation.
Chercher au hasard est toujours possible, mais il existe une technique infaillible, la méthode de Welsh et Powell ! Commençons par créer un tableau de deux lignes, une avec le nom des produits chimiques et l’autre avec le nombre d’incompatibilités (soit le nombre d’arêtes).
| Produit chimique | P1 | P2 | P3 | P4 | P5 | P6 |
| Nombre d’incompatibilités | 2 | 3 | 3 | 1 | 2 | 1 |
Il s ‘agit maintenant d’attribuer une couleur à chaque produit chimique. L’astuce consiste à commencer par le produit avec le plus d’incompatibilités. P1 et P2 répondent à ce critère et sont incompatibles. Prenons P2, on lui associe le rouge. Ensuite, on donne la même couleur au plus de produits chimiques possibles qui ne sont pas reliées : P4 et P6 héritent de la couleur rouge.
P3 est le deuxième produit chimique avec le plus d’incompatibilités : on lui attribue une nouvelle couleur, la couleur bleue. P5 qui n’est pas relié à P3, reçoit la même couleur. A ce stade, il reste P1 sans couleur. On lui donne une nouvelle couleur, le jaune.
Seules trois couleurs ont été nécessaires pour colorer le graphe. Conclusion : trois wagons suffisent pour le transport de ces produits chimiques !
Cet exemple montre à quel point la coloration des graphes est intéressante pour résoudre de nombreux problèmes. Elle est utile pour colorer des cartes géographiques, répartir des poissons dans des aquariums, ou encore trouver le nombre de salles de classe nécessaires pour éviter tout bavardage…
A votre tour d’en découvrir tous les usages et de « grapher » un maximum !
Les auteurs : Sullivan Watelle – Paul Fournier – Rudy Meresse – Hugo Niles
Pour en savoir plus, voici une sélection de liens sur la coloration d’un graphe :
http://www.mathematiquesfaciles.com/graphes-2-coloration-d-un-graphe-niveau-terminale-es_2_45761.htm
http://fr.wikipedia.org/wiki/Coloration_de_graphe
http://www.apprendre-en-ligne.net/graphes-ancien/coloration/sommets.html
Commenter l’article