Théorie des graphes

Des points et des lignes entre eux : un graphe n'est rien de plus. Pourtant, le même dessin décrit une carte routière, un réseau d'amis, une molécule et Internet, et les questions qu'on peut se poser à son sujet, du nombre de couleurs nécessaires à la possibilité de le tracer d'un seul trait, occupent les mathématiciens depuis 1736.

Un graphe à dix sommets, le graphe de Petersen, dont les sommets sont coloriés en trois couleurs de sorte qu'aucune arête ne relie deux sommets de même couleur
Un graphe à dix sommets, le graphe de Petersen, dont les sommets sont coloriés en trois couleurs de sorte qu'aucune arête ne relie deux sommets de même couleur

Sommets et arêtes

Un graphe possède des sommets, aussi appelés nœuds, et des arêtes, qui relient chacune deux sommets. L'endroit où l'on dessine les sommets n'a pas d'importance, seules comptent les paires reliées, si bien que le même graphe peut avoir des allures très différentes sur le papier. Les graphes de l'atelier sont simples : aucune arête d'un sommet vers lui-même, et au plus une arête entre deux sommets. Avec n sommets, il peut y avoir au plus n(n − 1) / 2 arêtes ; un graphe qui les a toutes est dit complet, et K5 est le graphe complet à cinq sommets.

Les degrés et le lemme des poignées de main

Le degré d'un sommet est le nombre d'arêtes qui en partent. En additionnant tous les degrés, on obtient exactement le double du nombre d'arêtes, car chaque arête a deux extrémités et est comptée une fois à chacune. C'est le lemme des poignées de main : dans n'importe quel groupe, les poignées de main comptées personne par personne font au total le double du nombre de poignées de main. Il en découle aussi que le nombre de sommets de degré impair est toujours pair. Un graphe dont tous les sommets ont le même degré k est dit k-régulier.

Graphes connexes, arbres et cycles

Un graphe est connexe lorsqu'on peut aller de chaque sommet à tous les autres en suivant les arêtes ; sinon, il se divise en morceaux, appelés composantes connexes. Un cycle est un circuit qui revient à son point de départ sans passer deux fois par le même sommet, et la longueur du plus court s'appelle la maille. Un graphe connexe sans cycle est un arbre, et un arbre à n sommets a toujours exactement n − 1 arêtes : une de moins et il se divise, une de plus et il contient un cycle. Tout graphe connexe contient un arbre couvrant, un arbre qui atteint chaque sommet en n'utilisant qu'une partie des arêtes.

Graphes bipartis et coloration

Coloriez les sommets de sorte qu'aucune arête ne relie deux sommets de même couleur. Le plus petit nombre de couleurs qui le permet est le nombre chromatique. Une seule couleur ne suffit qu'en l'absence d'arêtes. Deux couleurs suffisent exactement lorsque le graphe est biparti : ses sommets se répartissent en deux côtés et chaque arête passe de l'un à l'autre. Dénes Kőnig a montré en 1936 que cela revient à n'avoir aucun cycle de longueur impaire, car un cycle impair ne peut pas alterner entre deux couleurs. Pour trois couleurs ou plus, on ne connaît aucun test aussi simple : décider si trois couleurs suffisent est NP-complet, alors les programmes cherchent, comme le fait l'atelier.

Un exemple : le graphe de Petersen

Prenez un pentagone A–B–C–D–E et, à l'intérieur, une étoile à cinq branches F–H–J–G–I, puis reliez chaque coin du pentagone à une pointe de l'étoile : A–F, B–G, C–H, D–I et E–J. Voilà le graphe de Petersen, avec 10 sommets et 15 arêtes. Chaque sommet est de degré 3, donc la somme des degrés vaut 30, le double de 15. Son plus court cycle est de longueur 5, il n'a donc aucun triangle, mais le pentagone est un cycle impair, il n'est donc pas biparti et il lui faut 3 couleurs. Deux sommets quelconques sont à au plus 2 arêtes l'un de l'autre, son diamètre vaut donc 2. Ses dix degrés sont tous impairs, il n'a donc aucun parcours eulérien, et on ne peut pas le dessiner sans croisements.

Les chemins eulériens et les ponts de Königsberg

La ville de Königsberg avait sept ponts reliant quatre parties de terre, et l'on se demandait s'il était possible de traverser chaque pont exactement une fois. En 1736, Leonhard Euler a montré que c'était impossible, et la théorie des graphes est née. Chaque fois qu'une promenade traverse une partie de terre, elle utilise deux ponts, si bien que seuls le départ et l'arrivée peuvent en avoir un nombre impair, or les quatre parties de Königsberg en avaient toutes un nombre impair. Un parcours qui emprunte chaque arête une fois s'appelle aujourd'hui un chemin eulérien, ou un cycle eulérien lorsqu'il se termine là où il a commencé. Carl Hierholzer a démontré en 1873 que la condition est aussi suffisante : si toutes les arêtes forment un seul morceau et qu'au plus deux degrés sont impairs, le parcours existe, et sa méthode, qui consiste à raccorder des circuits, permet toujours de le trouver.

Une carte historique à vol d’oiseau de Königsberg (Koningsberga), montrant la Pregel et l’île au cœur du problème des sept ponts. En 1736, Leonhard Euler montra qu’aucune promenade ne pouvait traverser chaque pont exactement une fois, et la théorie des graphes commença.
Une carte historique à vol d’oiseau de Königsberg (Koningsberga), montrant la Pregel et l’île au cœur du problème des sept ponts. En 1736, Leonhard Euler montra qu’aucune promenade ne pouvait traverser chaque pont exactement une fois, et la théorie des graphes commença.
Portrait de Leonhard Euler
Portrait de Leonhard Euler

Distance, diamètre et complémentaire

La distance entre deux sommets est le plus petit nombre d'arêtes d'un chemin qui les relie, et le diamètre est la plus grande distance dans le graphe ; dans un graphe non connexe, il est infini. Les réseaux sociaux ont de petits diamètres, c'est l'idée derrière les six degrés de séparation. Le complémentaire d'un graphe a les mêmes sommets et relie exactement les paires qui n'étaient pas reliées. D'un graphe et de son complémentaire, l'un au moins est toujours connexe.

À vous de jouer

L'atelier s'ouvre sur le graphe de Petersen colorié en trois couleurs. Cliquez sur Degrés et vérifiez le lemme des poignées de main, cliquez sur Biparti pour voir un cycle impair, puis chargez le cube et regardez apparaître les deux côtés. Chargez la maison et cliquez sur Parcours eulérien pour voir où le trait doit commencer. Dessinez votre propre graphe et ajoutez les arêtes une à une : regardez le plus court cycle raccourcir, le diamètre diminuer et le nombre chromatique augmenter quand la dernière arête d'un K4 est ajoutée.

Questions fréquemment posées

Quelle est la différence entre chaîne, chaîne simple et chaîne élémentaire ?

Une chaîne est une suite quelconque de sommets reliés par des arêtes, qui peut répéter les uns comme les autres. Une chaîne simple peut repasser par un sommet mais pas par une arête, c'est pourquoi un parcours eulérien peut traverser un sommet plusieurs fois. Une chaîne élémentaire ne répète ni sommet ni arête.

Qu'est-ce que le théorème des quatre couleurs ?

Il affirme que tout graphe que l'on peut dessiner sur papier sans croisement d'arêtes peut être colorié avec au plus quatre couleurs, si bien qu'aucune carte n'a besoin de plus de quatre couleurs. Il a été démontré en 1976 par Kenneth Appel et Wolfgang Haken à l'aide d'un ordinateur, le premier grand théorème démontré de cette façon.

Qu'est-ce qu'un cycle hamiltonien ?

Un cycle qui passe exactement une fois par chaque sommet, au lieu de chaque arête. La question ressemble à celle d'Euler, mais on ne connaît aucun test simple pour y répondre : décider si un graphe en possède un est NP-complet. Le graphe de Petersen a une chaîne hamiltonienne, mais pas de cycle hamiltonien.

Où utilise-t-on la théorie des graphes ?

Les calculateurs d'itinéraire explorent des graphes routiers, les moteurs de recherche classent les pages web d'après leurs liens, les compilateurs colorient des graphes pour partager les registres du processeur, les emplois du temps évitent les conflits en coloriant un graphe d'incompatibilités, les chimistes dénombrent les molécules comme des graphes, et les réseaux d'ordinateurs, de lignes électriques et d'amis sont étudiés comme des graphes.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir l'Atelier de théorie des graphes