Le Petit Prince d’Antoine de Saint Exupéry a dit avoir eu peur de devenir comme les grandes personnes qui ne s’intéressent plus qu’aux chiffres. C’est la raison pour laquelle il a acheté une boîte de couleurs et des crayons. De nombreux mathématiciens ont suivi cette voie et ont développé ce qu’on appelle aujourd’hui la théorie des graphes. Alors qu’on demande au Petit Prince de dessiner un mouton, la tâche des mathématiciens est de construire des horaires, de planifier des déplacements, d’optimiser la production de biens, et ils le font en dessinant des graphes colorés. Car un graphe vaut mille mots et permet de dégager l’essence d’un problème en offrant une vision imagée des données et des contraintes d’un problème mathématique complexe.
Qu’est-ce qu’un graphe?
Aucune connaissance mathématique n’est nécessaire pour dessiner un graphe. Il suffit de prendre une feuille de papier, de choisir quelques emplacements en les marquant avec de petits cercles, et d’ajouter quelques liai- sons entre certaines paires d’emplacements. Les petits cercles sont appelés des sommets alors que les liaisons sont appelées des arêtes. Deux sommets reliés par une arête sont dits voisins, et le degré d’un sommet est son nombre de voisins. Par exemple, le graphe ci-dessus contient 12 sommets, 23 arêtes, et les degrés sont inscrits sur chaque sommet.
On accorde généralement à Leonard Euler l’origine de la théorie des graphes. Ce mathématicien et physicien suisse a été le premier en 1736 à résoudre un problème (celui des ponts de Königsberg) en démontrant une propriété des graphes. Aujourd’hui, l’utilisation des graphes est devenue monnaie courante, car ceux-ci offrent une représentation imagée et colorée de situations très variées auxquelles nous faisons face au quotidien.
Détecter des incohérences
Les propriétés des graphes permettent parfois de mettre à jour des incohérences. Supposez par exemple qu’un de vos amis se vante d’avoir sept ordinateurs, et pré- tend qu’il les a mis en réseau en connectant chacun d’eux à trois autres. Vous pouvez lui dire, sans avoir peur de vous tromper, que ses propos sont incohérents. S’il persiste dans ses affirmations, mettez-le au défi de représenter sur une feuille de papier l’ensemble des liens entre les ordinateurs. En d’autres termes, demandez-lui de dessiner le graphe des connections. Il n’y arrivera pas, à cause du Lemme des poignées de mains démontré par Leonard Euler en 1736.
Les ponts de Königsberg
La ville de Königsberg est traversée par une rivière qui entoure deux grandes îles reliées entre elles et aux deux rives par sept ponts. En 1736, les habitants cherchaient un chemin permettant de passer par chaque pont exactement une fois et de revenir au point de départ. Leonhard Euler a établi que, pour que ce soit possible, il aurait fallu que chacune des quatre zones géographiques (les deux îles et les deux rives) soit atteinte par un nombre pair de ponts. En termes de graphes, cela signifie qu’il aurait fallu que chacun des sommets du graphe associé à ce problème soit de degré pair. Ce résultat est considéré comme le premier théorème de la théorie des graphes.
Euler a donc démontré une condition nécessaire pour l’existence d’un parcours eulérien1. Ce n’est cependant qu’en 1873 que Carl Hierholzer a réussi à démontrer une condition nécessaire et suffisante, à savoir qu’un graphe possède un parcours eulérien si et seulement si le graphe est connexe2 et tous ses sommets sont de degré pair.
Ainsi, par exemple, on peut dessiner les arêtes du graphe ci-dessous à gauche, sans lever le crayon (saurez-vous le faire?) alors que c’est impossible pour celui de droite, car les deux sommets rouges sont de degré impair.
Lemme des poignées de mains
Dans tout graphe, il y a un nombre pair de sommets de degré impair.
La preuve de ce lemme est assez simple à comprendre. S’il existait un nombre impair de sommets de degré impair, la somme de tous les degrés des sommets serait un nombre impair. Cela est impossible puisque cette somme est le double du nombre d’arêtes dans le graphe, et donc un nombre pair.
Votre ami ne dit donc pas la vérité puisqu’il doit vous dessiner un graphe avec sept sommets de degré impair trois.
Qui a rendu visite à mamie?
Tournons-nous maintenant du côté d’une mère de famille qui a pris l’habitude de se plaindre du comportement de ses 4 enfants, car ils ne rendent pas assez souvent visite à leur grand-mère qui est alitée dans une maison de retraite. Ce dimanche elle a cependant tenu à les féliciter tous les quatre, car ils lui ont tous annoncé avoir vu mamie samedi après-midi. Chacun d’eux est resté environ une heure. Daniel était déjà parti lorsque Phil est arrivé, mais les deux garçons ont rencontré Céline et Sarah durant leur visite. Les deux filles confirment avoir rencontré leurs deux frères chez mamie, bien qu’elles ne se soient pas croisées.
Cette mère de famille pourrait facilement réaliser, à l’aide de la théorie des graphes, qu’au moins un de ses enfants ne dit pas la vérité. Pourquoi? Un graphe vaut mille mots. Dans le carré de l’illustration ci-contre, chaque sommet représente l’un des enfants et chaque arête représente une rencontre dans la chambre de mamie. Le temps n’étant pas circulaire, ce graphe démontre une incohérence dans les affirmations des enfants. En effet, s’ils disaient tous la vérité, les deux filles devaient être chez mamie lorsque Daniel est parti, et y sont restées jusqu’à l’arrivée de Phil. Elles ont donc forcément dû passer quelques minutes ensemble dans la chambre, bien qu’elles prétendent le contraire.
Les graphes d’intervalles
Cette petite histoire familiale illustre le concept de graphes d’intervalles: étant donnés plusieurs intervalles dans le temps, il est possible de leur associer un graphe dans lequel chaque sommet représente un intervalle, et où deux sommets sont reliés par une arête lorsque les deux intervalles correspondants ont une intersection commune. Ces graphes sont très utiles en pratique.
Supposons par exemple qu’une compagnie aérienne désire déterminer le nombre minimum de pilotes nécessaires pour réaliser tous les vols qu’elle a prévu d’offrir à ses clients. Dans le petit exemple ci-dessous, nous avons représenté six vols à l’aide de six intervalles de temps durant lesquels les pilotes devront être aux commandes de leur avion. Le graphe d’intervalles associé à ces vols contient donc six sommets, et le problème à résoudre en est un de coloriage: il faut attribuer une couleur à chaque sommet du graphe, en évitant de donner la même couleur à des sommets reliés par une arête. Chaque couleur correspond à un pilote. Un coloriage en 3 couleurs démontre que 3 pilotes suffisent pour couvrir tous les vols.
Un même graphe, dans des contextes différents
Bien que les six sommets du graphe que nous venons de construire représentaient six vols à attribuer à des pilotes, ce même graphe peut être utilisé dans des contextes totalement différents. Supposons par exemple qu’une école désire déterminer un horaire pour ses 6 cours C1,…,C6 , chacun d’eux ayant une durée d’une heure. L’un des deux professeurs donne les cours C1, C2 et C3 alors que l’autre donne les 3 autres. De plus, les cours C2, C3 et C4 s’adressent à la même classe, et les cours C3 et C5 doivent être donnés dans l’unique salle de gymnastique dont l’école dispose. On peut construire un graphe en représentant chaque cours par un sommet et en reliant deux cours lorsque ceux-ci ne peuvent pas être donnés simultanément. Le graphe à six sommets que nous avons construit pour la compagnie aérienne représente en fait les incompatibilités d’horaires entre les six cours: les triangles reliant 1, 2 et 3 ainsi que 4, 5 et 6 indiquent qu’un même professeur ne peut pas donner deux cours simultanément; les arêtes reliant 2 et 3 à 4 indiquent qu’une classe ne peut pas suivre deux cours durant la même période; finalement, l’arête reliant 3 à 5 signale la nécessité de planifier ces deux cours à des périodes différentes car il n’existe qu’une seule salle de gymnastique. La même coloration du graphe que nous avons utilisée plus haut démontre qu’on peut construire un horaire sur 3 périodes.
Imaginons maintenant une carte géographique sur laquelle sont représentés quelques pays. On peut associer un graphe à cette carte en représentant chaque pays par un sommet et en reliant deux pays par une arête lorsque ceux-ci ont une frontière commune. La coloration des sommets du graphe correspond cette fois-ci à un coloriage de la carte géographique sous la contrainte que deux pays limitrophes ne peuvent pas avoir la même couleur.
Colorer un graphe
Colorer un graphe, c’est attribuer une couleur à chacun de ses sommets de telle sorte que chaque arête ait ses extrémités de couleurs différentes.
Les premiers résultats sur ce problème ont principalement porté sur la coloration de cartes géographiques. En 1852, alors qu’il cherchait à mettre en couleurs une carte des comtés d’Angleterre, Francis Guthrie remarqua qu’il n’y avait besoin que de quatre couleurs pour que deux comtés ayant une frontière commune soient de couleurs différentes. Il s’est demandé si cette constatation était valide pour toute carte géographique. Le frère de Guthrie transmit la question à son professeur de mathématiques, Auguste de Morgan.
En 1879, Alfred Kempe publia ce qu’il prétendit être une démonstration que quatre couleurs suffisent toujours, et pendant une décennie, on crut que le problème des quatre couleurs était résolu.
Ce n’est qu’en 1890 que Percy John Heawood fit remarquer que la démonstration de Kempe était erronée. Et c’est finalement en 1976 que Kenneth Appel et Wolfgang Haken ont réussi à démontrer cette conjecture. L’essentiel de la vérification de leur preuve a été réalisée par ordinateur, ce qui a soulevé d’importants problèmes méthodologiques.
Aujourd’hui, le champ d’applications de la coloration des graphes couvre notamment les problèmes de confection d’horaires et l’attribution de fréquences en télécommunication.
Problèmes de cheminements
Les graphes constituent un modèle naturel pour représenter un réseau routier: les carrefours deviennent des sommets et les routes des arêtes. Lorsque vous demandez à votre GPS (système de Géo-positionnement par Satellite) comment vous rendre d’un point A à un point B, celui-ci a mémorisé sous forme de graphe la carte routière sur laquelle vous circulez. Il ne lui reste donc qu’à déterminer un plus court chemin de A vers B dans le graphe en question, ce qui est considéré, de nos jours, comme un problème facile à résoudre.
L’origine A et la destination B d’un chemin ne correspondent pas nécessairement à des positions sur une carte géographique, et les distances ne se calculent pas nécessairement en kilomètres. Par exemple, supposons que vous disposez de deux seaux non gradués, l’un de 5 litres et l’autre de 3 litres. Vous n’avez aucun autre moyen de stocker de l’eau ni aucun autre outil de mesure, et on vous demande de mettre exactement 4 litres dans le grand seau. L’eau que vous pouvez puiser à un robinet est une denrée précieuse et vous voulez donc en consommer aussi peu que possible. Que devez-vous faire?
Ce problème peut être modélisé à l’aide d’un graphe. Chaque sommet est représenté par un couple x,y de nombres qui correspondent aux contenus des deux seaux. Par exemple, le sommet 2,1 signifie que le grand seau de 5 litres n’en contient que 2, alors que le petit seau de 3 litres en contient 1. On crée un lien orienté d’un sommet vers un autre si on peut passer de la situation correspondant au premier sommet à celle du deuxième sommet en vidant le contenu d’un seau, en remplissant l’un à ras bord, ou en transvasant le contenu d’un seau dans l’autre jusqu’à ce que l’un soit vide ou que l’autre soit plein. Le graphe de toutes les possibilités est représenté ci-des- sous à gauche. Les distances sur les liens correspondent aux nombres de litres puisés au robinet. Ainsi, par exemple, si on se rend du sommet 1,0 au sommet 1,3, la distance est de 3 puisqu’il faut puiser 3 litres pour remplir le petit seau. Par contre, la distance de 1,3 à 1,0 est nulle puisqu’il suffit de vider le petit seau pour se rendre du premier au deuxième sommet. Le problème à résoudre correspond ainsi à trouver un chemin aussi court que possible allant du sommet 0,0 (situation initiale avec les deux seaux vides) au sommet 4,0 ou 4,3 (sommets pour lesquels le grand seau contient 4 litres). Le chemin optimal et la solution correspondante sont représentés dans la figure de la page précédente. Les liens noirs ont une distance nulle alors que les liens rouges ont une distance égale à 3. Il faut donc puiser au minimum 9 litres au robinet.
Le problème auquel le commis voyageur doit faire face est bien plus complexe. Il doit partir de son domicile le matin pour rendre visite à un certain nombre de clients, puis retourner chez lui le soir. L’ordre des visites n’étant pas fixé, il a tout avantage à choisir un ordre qui lui fera parcourir aussi peu de kilomètres que possible, ce qui lui permettra de rejoindre sa famille le plus tôt possible.
À nouveau, un même graphe est utilisé dans des contextes totalement différents. La tournée que nous avons associée à un commis voyageur peut être celle d’une infirmière offrant des soins à domicile à des patients. Ou alors, il s’agit du parcours d’un laser qui doit percer un certain nombre de trous lors de la production de circuits intégrés (aussi appelés puces électroniques). La distance totale parcourue dans la tournée peut donc varier de quelques dizaines de kilomètres à quelques millimètres. Qu’importe, le dessin montre dans quel ordre les villes, les patients ou les trous doivent être visités par le commis voyageur, l’infirmière ou le laser.
Le problème du commis voyageur
Étant donné un ensemble de villes et les distances séparant chaque ville, le problème du commis voyageur consiste à trouver un chemin de longueur totale mini- male qui passe exactement une fois par chaque ville et revienne au point de départ (le domicile).
Ce problème est plus compliqué qu’il n’y paraît. Pour un très grand nombre de villes, on devra souvent se contenter de solutions non optimales, car on se retrouve face à une explosion combinatoire. Par exemple, le nombre de chemins possibles passant par 70 villes est supérieur au nombre d’atomes dans tout l’univers3.
Se concentrer sur l’essentiel
Comme nous l’avons vu, les graphes permettent de modéliser de nombreuses situations que vous pourriez rencontrer dans votre vie. Comment se rendre du point A au point B? Comment planifier les horaires de cours dans une école? Combien de pilotes une compagnie aérienne doit-elle engager? Quelle est la façon la plus économique de produire un circuit intégré? Comment planifier la tournée d’une infirmière offrant des soins à domicile? Ce ne sont là que quelques exemples parmi une infinité d’autres. La seule limite est celle de votre imagination. Dessiner un graphe, c’est modéliser une situation possiblement complexe à l’aide de points et de traits, ce qui permet d’évacuer l’inutile pour se concentrer sur l’essentiel.
Pour en s\(\alpha\)voir plus!
- Pour découvrir la théorie des graphes sous forme d’énigmes policières
– Hertz, A. L’agrapheur : intrigues policières à saveur mathématique, Presses Internationales Polytechnique, 2010, ISBN: 978-2-553-01543-4
– Hertz, A. GRAPHITI – L’Inspecteur Manori enquête à Paris, Éditions Amalthée, 2014, ISBN: 978-2-310-01908-8 - Pour le problème des ponts de Königsberg
– La publication originale (en latin) de Leonhard Euler de 1736 est accessible à l’url
https://math.dartmouth.edu/~euler/docs/originals/E053.pdf
– Gribkovskaia I., Halskau Sr. Ø. et Laporte G., The bridges of Königsberg – A historical perspective, Networks 49/3 (2007) 199-203 - Pour la coloration de graphes
– Beineke L.W. et Wilson R.J., Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and Its Applications 156, Cambridge University Press, 2015
– Fritsch R. et Fritsch G. The Four Color Theorem: History, Topological Foundations and Idea of Proof, traduit de la version originale en allemand par Julie Peschke., New York: Springer, 1998, ISBN 978-0-387-98497 1 - Pour le problème du commis voyageur
– Cook W.J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012, ISBN: 978-0-691-15270-7
– Lawler E.L, Lenstra J.K., Rinnooy Kan A.H.G. et Shmoys D.B., The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, 1985, ISBN: 978-0-471-90413-7
- Un graphe connexe est eulérien si et seulement si chacun de ses sommets est incident à un nombre pair d’arêtes. ↩
- Un graphe dont on peut parcourir les arêtes dans un sens ou dans l’autre est dit connexe s’il existe toujours une suite d’arêtes reliant deux sommets quelconques. ↩
- Pour un voyageur de commerce qui doit visiter 70 villes, le nombre de chemins possibles est 70! ≈ 10100 alors que le nombre d’atomes dans l’univers visible est estimé à 1080. ↩