Une entre­pri­se sou­hai­te trans­por­ter six pro­duits chi­mi­ques dif­fé­rents mais cer­tains ne peu­vent pas voya­ger ensem­ble, à cau­se du ris­que d’explosion. Com­bien de wagons seront néces­sai­res pour que les pro­duits incom­pa­ti­bles puis­sent être convoyés sépa­ré­ment ? Quel­ques crayons de cou­leur et un peu de métho­de per­met­tent de résou­dre ce pro­blè­me !

Il s’agit de conver­tir le pro­blè­me en une figu­re géo­mé­tri­que, com­po­sée d’arêtes et de som­mets, que l’on nom­me un gra­phe. Ici, les som­mets repré­sen­te­ront les pro­duits chi­mi­ques et les arê­tes relie­ront les pro­duits incom­pa­ti­bles.

On essaie ensui­te de colo­rier les som­mets de sor­te que deux som­mets reliés pos­sè­dent des cou­leurs dif­fé­ren­tes. Ça sem­ble faci­le, mais il s’agit pour cela d’utiliser le moins de cou­leurs pos­si­bles ! On obtient alors le « nom­bre chro­ma­ti­que », soit le plus petit nom­bre de cou­leurs per­met­tant de résou­dre le gra­phe. Dans notre cas, ce nom­bre repré­sen­te­ra le nom­bre de wagons néces­sai­res.
Il est temps de pas­ser à la pra­ti­que !

Pre­nons six pro­duits chi­mi­ques dif­fé­rents que l’on nom­me­ra P1, P2, P3, P4, P5 et P6. Sachant que…
P1 ne peut être trans­por­té avec P2 et P3
P2 ne peut être trans­por­té avec P1, P3 ou P5
P3 ne peut être trans­por­té avec P1, P2P4
P5 ne peut être trans­por­té avec P2 ou P6
La pre­miè­re éta­pe du rai­son­ne­ment consis­te donc à réa­li­ser le gra­phe de cet­te situa­tion.

Sans titre

Cher­cher au hasard est tou­jours pos­si­ble, mais il exis­te une tech­ni­que infailli­ble, la métho­de de Wel­sh et Powell ! Com­men­çons par créer un tableau de deux lignes, une avec le nom des pro­duits chi­mi­ques et l’autre avec le nom­bre d’incompatibilités (soit le nom­bre d’arêtes).

Pro­duit chi­mi­que P1 P2 P3 P4 P5 P6
Nom­bre d’incompatibilités 2 3 3 1 2 1

 

Il s ‘agit main­te­nant d’attribuer une cou­leur à cha­que pro­duit chi­mi­que. L’astuce consis­te à com­men­cer par le pro­duit avec le plus d’incompatibilités. P1 et P2 répon­dent à ce cri­tè­re et sont incom­pa­ti­bles. Pre­nons P2, on lui asso­cie le rou­ge. Ensui­te, on don­ne la même cou­leur au plus de pro­duits chi­mi­ques pos­si­bles qui ne sont pas reliées : P4 et P6 héri­tent de la cou­leur rou­ge.
P3 est le deuxiè­me pro­duit chi­mi­que avec le plus d’incompatibilités : on lui attri­bue une nou­vel­le cou­leur, la cou­leur bleue. P5 qui n’est pas relié à P3, reçoit la même cou­leur. A ce sta­de, il res­te P1 sans cou­leur. On lui don­ne une nou­vel­le cou­leur, le jau­ne.

image3-correc-OL

Seules trois cou­leurs ont été néces­sai­res pour colo­rer le gra­phe. Conclu­sion : trois wagons suf­fi­sent pour le trans­port de ces pro­duits chi­mi­ques !

Cet exem­ple mon­tre à quel point la colo­ra­tion des gra­phes est inté­res­san­te pour résou­dre de nom­breux pro­blè­mes. Elle est uti­le pour colo­rer des car­tes géo­gra­phi­ques, répar­tir des pois­sons dans des aqua­riums, ou enco­re trou­ver le nom­bre de sal­les de clas­se néces­sai­res pour évi­ter tout bavar­da­ge…
A votre tour d’en décou­vrir tous les usa­ges et de « gra­pher » un maxi­mum !

Les auteurs : Sul­li­van Watel­le – Paul Four­nier – Rudy Meres­se – Hugo Niles

Pour en savoir plus, voi­ci une sélec­tion de liens sur la colo­ra­tion d’un gra­phe :
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

Partager

A propos de l'auteur

Lycée Baggio - Lille

Historiquement tourné vers la culture scientifique et technologique, le Lycée Baggio vise à amener la jeunesse au plus haut niveau des savoir et des savoir faire – sans négliger l’importance actuelle des savoir être -, en s’appuyant sur une devise fédératrice : Réussir ensemble.

Laisser un commentaire