Introduction à la Théorie des Graphes

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce qu'étudie réellement la théorie des graphes

La théorie des graphes étudie une seule idée, toute petite : une collection d'objets et un relevé des paires qui sont reliées entre elles. C'est tout le sujet. Ce qui justifie un siècle et demi de mathématiques, c'est qu'un nombre considérable de questions pratiques se révèlent être des questions portant exactement là-dessus, et sur rien d'autre.

Prenons quatre problèmes qui semblent sans rapport. Une entreprise de livraison cherche l'itinéraire le plus court entre deux dépôts. Un compilateur a besoin de l'ordre dans lequel construire les modules d'un projet. Une biologiste veut savoir quelles protéines interagissent, directement ou par des intermédiaires. Un opérateur réseau veut savoir quel câble, s'il était coupé, isolerait une région. En tant qu'histoires, elles n'ont rien en commun. Structurellement, ce sont la même poignée de problèmes posés sur le même type d'objet, et les algorithmes qui les résolvent sont interchangeables. Cette transférabilité explique pourquoi la discipline est enseignée tôt et utilisée partout : dès qu'une situation est écrite sous forme de graphe, un vaste catalogue de résultats devient disponible d'un seul coup, et aucun d'eux ne se soucie de ce que représentaient à l'origine les sommets.

Remarquez ce que l'image de droite ne contient pas. Les localités ont bougé, les routes sont droites, et rien n'indique que l'une est deux fois plus longue qu'une autre. Si ces faits comptent pour votre question, vous devez les rajouter explicitement, sous forme de nombres sur les arêtes. S'ils ne comptent pas, les jeter est précisément ce qui rend le problème traitable.

Cet article est un premier cours en une seule page : les définitions dans l'ordre, les petits résultats sur lesquels repose tout le reste, la façon dont les graphes sont stockés et parcourus dans du vrai code, les problèmes classiques, et une carte honnête des questions auxquelles un ordinateur répond en quelques secondes et de celles auxquelles il ne peut pas répondre du tout. Chaque section renvoie à un article plus approfondi si vous voulez en savoir plus sur ce sujet précis.

2. La définition, et ce qu'elle laisse de côté volontairement

Presque toutes les présentations grand public disent qu'un graphe, ce sont « des points reliés par des lignes ». Cette image est utile, et c'est aussi la raison pour laquelle beaucoup de gens se retrouvent bloqués quelques semaines plus tard : les points et les lignes sont un dessin de l'objet, pas l'objet. L'objet est un couple d'ensembles. L'ouvrage de Diestel, Graph Theory, la référence standard de niveau master, l'énonce sous sa forme la plus épurée :

Un graphe est un couple G = (V, E) d'ensembles tel que E ⊆ [V]², où [V]² est l'ensemble de toutes les parties à 2 éléments de V.

Déplié, cela dit quatre choses :

• V est un ensemble d'objets, appelés sommets (ou nœuds). On ne suppose absolument rien à leur sujet. Ce peuvent être des villes, des personnes, des atomes, des pages web ou des entiers. La théorie ne regarde jamais à l'intérieur d'un sommet ; elle a seulement besoin de pouvoir en distinguer deux.
• E est un ensemble de parties à 2 éléments de V. Une arête est littéralement l'ensemble {u, v}. Ce n'est ni une flèche ni une courbe, et elle ne porte aucune autre information que la paire qu'elle relie.
• Comme E est un ensemble, une arête est présente ou absente. Elle ne peut pas apparaître deux fois.
• Comme chaque arête a deux éléments distincts, aucune arête ne relie un sommet à lui-même.

Ces deux dernières conséquences ne sont pas des règles supplémentaires ajoutées par quelqu'un ; elles découlent directement de la théorie des ensembles, et un graphe qui les respecte est dit simple. Autoriser des arêtes répétées ou des boucles revient à modifier la définition elle-même, ce que font les multigraphes à la section 5.

Deux autres notations apparaissent partout. On écrit V(G) et E(G) lorsque plusieurs graphes sont en jeu. Et les deux mesures de taille ont un nom : on appelle ordre du graphe son nombre de sommets, et tailleson nombre d'arêtes, abrégés dans presque tous les textes d'algorithmique en n = |V| et m = |E|.

Ce que la définition laisse de côté est aussi instructif que ce qu'elle contient. Il n'y a aucune géométrie, donc deux dessins du même graphe sont le même graphe, même si l'un ressemble à une spirale et l'autre à une grille. Il n'y a aucun ordre sur les sommets. Il n'y a ni distances, ni capacités, ni coûts ; ceux-ci proviennent d'une fonction supplémentaire, généralement notée w: E → ℝ, ajoutée quand un problème en a besoin. L'objet nu est volontairement appauvri, et c'est cette pauvreté qui rend les théorèmes qui le concernent si largement applicables. Le guide complémentaire sur les sommets et arêtes reprend la même définition plus en détail.

3. Les origines : sept ponts et une promenade impossible

La discipline a une date de naissance. En 1736, Leonhard Euler, alors à l'Académie de Saint-Pétersbourg, soumit un mémoire intitulé Solutio problematis ad geometriam situs pertinentis, « la solution d'un problème relatif à la géométrie de position ». Le problème venait de la ville prussienne de Königsberg, aujourd'hui Kaliningrad. La rivière Pregel divisait la ville en quatre terres, reliées par sept ponts, et les habitants s'amusaient d'une question : peut-on traverser la ville en franchissant chaque pont exactement une fois ?

Le premier geste d'Euler est le geste dont parle tout cet article. La taille et la forme des terres sont sans importance, la longueur des ponts est sans importance, et la seule chose qui compte est quelle terre est reliée à quelle autre, et combien de fois. Retirez le reste et il vous reste quatre objets et sept connexions, que les manuels modernes dessinent comme un multigraphe à quatre sommets et sept arêtes.

Son raisonnement est assez court pour être donné en entier. Supposons que la promenade existe, et prenons n'importe quelle terre qui n'est ni son départ ni son arrivée. Chaque fois que la promenade y arrive, elle doit aussi en repartir, donc les ponts de cette terre sont utilisés par paires et leur nombre doit être pair. À Königsberg, les quatre terres avaient 5, 3, 3 et 3 ponts, tous impairs. Une promenade n'a que deux extrémités, donc au plus deux terres peuvent avoir un nombre impair. Quatre, c'est trop, et une telle promenade n'existe pas.

Euler énonça aussi la réciproque, mais ne la démontra pas ; cette lacune resta ouverte jusqu'à ce que Carl Hierholzer en donne une démonstration constructive, publiée à titre posthume en 1873. L'énoncé moderne est net : un graphe connexe possède une marche fermée utilisant chaque arête exactement une fois, un cycle eulérien, si et seulement si tous ses sommets sont de degré pair, et une marche ouverte, une chaîne eulérienne, si et seulement si exactement deux sommets sont de degré impair. L'histoire complète figure dans le guide consacré au chemin et cycle eulériens.

Le siècle suivant a consolidé les fondements, des arbres couvrants de Kirchhoff en 1847 à Sylvester empruntant le mot « graphe » à la chimie en 1878, jusqu'au premier manuel de Kőnig en 1936. Cette histoire est racontée dans l'histoire de la théorie des graphes.

4. Le vocabulaire et le premier théorème

La suite de cet article utilise un seul exemple récurrent, un graphe à sept sommets et huit arêtes. Il est assez petit pour vérifier chaque affirmation à la main et assez grand pour être intéressant.

V = {A, B, C, D, E, F, G}                          n = 7
E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,E},
      {D,E}, {D,F}, {F,G} }                        m = 8

Voici les termes, chacun défini uniquement à partir des deux ensembles :

• Adjacents. Deux sommets reliés par une arête. B et D sont adjacents, A et D ne le sont pas.
• Incidente. Une arête est incidente à chacune de ses deux extrémités. L'adjacence relie un sommet à un sommet, l'incidence relie un sommet à une arête, et les débutants confondent régulièrement les deux.
• Voisinage. N(v), l'ensemble des sommets adjacents à v. Ici N(D) = {B, E, F}.
• Degré. deg(v), le nombre d'extrémités d'arêtes aboutissant en v, qui, dans un graphe simple, vaut simplement |N(v)|. Ici deg(B) = 3 et deg(G) = 1.
• Feuille et sommet isolé. Degré 1, comme G, et degré 0. Les sommets isolés sont autorisés, et ce sont les données le plus souvent perdues quand un graphe est construit à partir d'une liste d'arêtes, car une liste d'arêtes n'a aucun moyen de les mentionner.
• Degré minimum et maximum. δ(G) et Δ(G), ici 1 en G et 3 en B, C et D.

Une fois le degré défini, le premier théorème n'est plus qu'à une ligne. Les sept degrés ont pour somme 2 + 3 + 3 + 3 + 2 + 2 + 1 = 16, exactement le double des huit arêtes, et ce n'est pas une coïncidence propre à ce graphe.

Cette technique, compter une même collection de deux façons, s'appelle le double dénombrement, et c'est le cheval de bataille de la combinatoire élémentaire. Le lemme a un corollaire qui surprend la première fois : le nombre de sommets de degré impair est toujours pair. Ici ce sont B, C, D et G, soit quatre. La raison est arithmétique : le total est pair et les sommets de degré pair apportent une contribution paire, donc les sommets de degré impair doivent apporter ensemble une contribution paire, ce qui exige qu'ils soient en nombre pair. En termes de tous les jours, le nombre de personnes dans une pièce ayant serré un nombre impair de mains est pair. Le raisonnement d'Euler sur Königsberg n'est autre que ce corollaire appliqué à une promenade.

5. Les familles de graphes

La définition nue de la section 2 est la plus restrictive. Tout problème de modélisation réel finit par avoir besoin d'une variante, et chaque variante est une modification précise, qui porte un nom, de ce qu'une arête a le droit d'être. Savoir dans quelle famille on se trouve décide des algorithmes même applicables, ce n'est donc pas du vocabulaire pour le plaisir.

Les graphes simples sont le cas par défaut : pas de boucles, pas d'arêtes répétées, et tout résultat d'un manuel énoncé sans précision les concerne. Les multigraphes autorisent les arêtes parallèles, et les pseudographes autorisent en plus les boucles. Königsberg exige vraiment un multigraphe, puisque deux de ses terres étaient reliées par deux ponts, et une boucle ajoute 2 au degré de son sommet car ses deux extrémités y aboutissent. Voir graphes simples et multigraphes.

Les graphes orientés, ou digraphes, remplacent la paire non ordonnée {u, v} par le couple ordonné (u, v), appelé arc, de sorte qu'un digraphe peut contenir un sens, les deux ou aucun, et le degré se scinde en degré entrant et degré sortant. C'est le bon modèle chaque fois que la relation n'est pas symétrique : rues à sens unique, « A suit B », « le module A importe le module B », « la tâche A doit se terminer avant la tâche B ». Voir graphes orientés et non orientés.

Les graphes pondérés ajoutent une fonction w qui attribue un nombre à chaque arête : kilomètres, minutes, prix, capacité, similarité. Les algorithmes ont des exigences fermes sur ces nombres. L'algorithme de Dijkstra exige qu'ils soient positifs ou nuls, Bellman-Ford tolère les valeurs négatives mais pas les cycles négatifs, et le parcours en largeur les ignore totalement, ce qui explique pourquoi lancer un BFS sur un graphe pondéré et appeler le résultat un plus court chemin est l'un des bugs les plus fréquents du code débutant. Voir graphes pondérés et non pondérés.

Les graphes bipartis partagent l'ensemble des sommets en deux parties, toutes les arêtes allant de l'une à l'autre. Étudiants et cours, candidats et postes, acheteurs et produits : toute situation d'affectation à deux côtés est bipartie. Un graphe est biparti exactement lorsqu'il ne contient aucun cycle impair, et un seul parcours en largeur qui colore les sommets en deux couleurs le décide en temps linéaire.

Les graphes complets, notés Kn, possèdent toutes les arêtes possibles. Comme une arête est un choix de 2 sommets parmi n, leur nombre est n(n-1)/2, donc K5 a 10 arêtes et K100 en a 4 950. C'est aussi le plafond de tout graphe simple à n sommets, et c'est la référence à laquelle on mesure la densité d'un graphe.

Les arbres sont des graphes connexes sans cycle, le sujet de la section 8. Les DAG, graphes orientés acycliques, sont des digraphes sans circuit, et ils ont la forme de toute dépendance et de tout planning : formules de tableur, cibles de build, commits Git et opérations d'un réseau de neurones sont tous des DAG, et l'algorithme qui les range dans un ordre valide est le tri topologique.

Une dernière famille mérite d'être connue par son nom : les graphes planaires peuvent être dessinés sans croisement d'arêtes, ce qui compte pour le routage de circuits et la coloration de cartes, et la section 12 y revient.

6. Marches, pistes, chemins et cycles

Quatre mots décrivent le déplacement dans un graphe ; dans la conversation courante, on les emploie indifféremment, mais ils désignent quatre choses différentes. Bien les distinguer évite par la suite une quantité surprenante de confusions, car les théorèmes sont énoncés avec le mot précis et la différence entre eux constitue souvent tout le contenu du résultat.

• Une marche est n'importe quelle suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Rien n'est interdit. Une marche peut emprunter la même arête et revenir au même sommet aussi souvent qu'elle le veut.
• Une piste est une marche sans arêterépétée. Les sommets peuvent encore se répéter. Le problème des ponts d'Euler demande une piste utilisant toutes les arêtes, c'est pourquoi on parle, en toute rigueur, de piste eulérienne et non de chemin eulérien.
• Un chemin est une marche sans sommetrépété, ce qui interdit automatiquement aussi les arêtes répétées. Quand quelqu'un dit « l'itinéraire de A à G », c'est de cela qu'il parle.
• Un cycle est un chemin fermé : il commence et finit au même sommet et ne répète rien d'autre. Dans l'exemple, B, C, E, D, B est un cycle de longueur 4, et A, B, C, A est un triangle, un cycle de longueur 3.

La longueur de chacun d'eux est son nombre d'arêtes, pas son nombre de sommets, une erreur de décalage d'une unité qui ne demande qu'à se produire. La distance d(u, v) est la longueur d'un plus court chemin. Ici d(A, G) = 4, en passant par A, B, D, F, G ; l'itinéraire A, C, E, D, F, G arrive aussi mais utilise cinq arêtes, c'est donc un chemin, mais pas un plus court. Le diamètre est la plus grande distance entre deux sommets, une manière compacte de dire à quel point un réseau est étendu.

Un fait en découle immédiatement et sert en permanence : s'il existe une marche de u à v, il existe un chemin de u à v. Coupez la boucle entre deux passages par le même sommet et vous obtenez une marche plus courte ; l'opération se termine donc sur une marche sans sommet répété. C'est pourquoi les algorithmes d'accessibilité ne considèrent jamais les marches.

7. Connexité, composantes et les arêtes qu'on ne peut pas perdre

Un graphe est connexe lorsque chaque sommet peut être atteint depuis tous les autres. Sinon, il se décompose en composantes connexes, qui sont les morceaux maximaux connexes en eux-mêmes. La connexité est la première chose à vérifier sur tout graphe que vous n'avez pas construit vous-même, car un nombre surprenant de jeux de données réels arrivent en plusieurs morceaux, et la plupart des bugs signalés du type « l'algorithme a renvoyé l'infini » ne sont que ce fait découvert à ses dépens.

Au sein d'un graphe connexe, certaines parties de la structure sont plus critiques que d'autres. Un pont est une arête dont la suppression augmente le nombre de composantes, et un sommet d'articulation, ou point d'articulation, est un sommet dont la suppression fait de même. Ce sont les points de défaillance uniques, et les trouver est l'analyse initiale standard de tout réseau dont la fiabilité compte.

Dans l'exemple récurrent, les arêtes DF et FG sont des ponts, et D et F sont des sommets d'articulation. Remarquez ce qui n'est pas un pont : aucune des cinq arêtes situées sur un cycle, car un cycle offre toujours un détour. C'est la règle générale, et elle mérite d'être énoncée comme un fait plutôt que comme une observation. Une arête est un pont exactement lorsqu'elle n'appartient à aucun cycle. La même intuition explique pourquoi la redondance des réseaux réels se mesure en cycles : un second itinéraire est un cycle passant par le premier.

Pour les graphes orientés, la notion se dédouble : un digraphe est faiblement connexe si, en ignorant le sens des arcs, on obtient un graphe connexe, et fortement connexe si chaque sommet atteint tous les autres en suivant les arcs dans le bon sens. L'algorithme de Tarjan de 1972 trouve les composantes fortement connexes en temps linéaire, et dans un graphe de dépendances, une telle composante comptant plus d'un sommet est précisément une dépendance circulaire.

Sur le plan du calcul, tout cela est bon marché. Un seul balayage en largeur ou en profondeur étiquette chaque composante en O(n + m), et les ponts et sommets d'articulation sortent d'un unique parcours en profondeur enrichi des valeurs low-link de Tarjan, également en O(n + m). Il y a rarement une raison de ne pas vérifier la connexité avant toute autre chose.

8. Les arbres : le cas particulier le plus utile

Un arbre est un graphe connexe sans cycle. C'est de loin le cas particulier le plus important de la discipline, en partie parce que les arbres apparaissent partout en informatique, et en partie parce qu'un très grand nombre de problèmes difficiles deviennent faciles quand l'entrée se trouve en être un.

Ce qui rend les arbres remarquables, c'est le nombre de descriptions d'apparence différente qui désignent les mêmes objets. Pour un graphe G à n sommets, toutes les propositions suivantes sont équivalentes, et n'importe laquelle peut servir de définition :

1. G est connexe et sans cycle.
2. G est connexe et possède exactement n - 1 arêtes.
3. G est sans cycle et possède exactement n - 1 arêtes.
4. Entre chaque paire de sommets, il existe exactement un chemin.
5. G est connexe, et la suppression de n'importe quelle arête le déconnecte, donc chaque arête est un pont.
6. G est sans cycle, et l'ajout de n'importe quelle nouvelle arête crée exactement un cycle.

L'équivalence se démontre par une chaîne circulaire d'implications, présentée dans le guide sur les arbres en théorie des graphes. Deux conséquences sont à garder en tête. Le nombre d'arêtes est imposé, donc un « arbre » à 100 sommets et 120 arêtes n'est pas un arbre, et quelque chose en amont est faux. Et l'unicité des chemins explique pourquoi les problèmes sur les arbres sont faciles : il n'y a rien à chercher, puisqu'il n'existe jamais qu'un seul itinéraire.

Une forêt est un graphe acyclique qui n'est pas forcément connexe, donc une union disjointe d'arbres, et une forêt à n sommets et c composantes possède exactement n - c arêtes. Un arbre couvrant d'un graphe connexe est un sous-graphe qui est un arbre et contient tous les sommets, le squelette le moins coûteux qui maintient le graphe d'un seul tenant. Les deux parcours en produisent un gratuitement au passage, et quand les arêtes portent des poids, trouver le plus léger est le problème de l'arbre couvrant de poids minimum .

Les arbres existent aussi en version enracinée, où un sommet est distingué et où les mots parent, enfant, ancêtre, sous-arbre et profondeur deviennent disponibles, comme dans les systèmes de fichiers, les arbres syntaxiques et les tas. L'enracinement est un choix posé par-dessus le graphe plutôt qu'une propriété de celui-ci, et c'est tout le propos de l'article sur les arbres enracinés.

9. Comment un graphe est stocké dans un ordinateur

Tout ce qui précède relève des mathématiques. Dès qu'une machine doit répondre à une question sur un graphe, il faut choisir sa disposition en mémoire, et ce choix n'est pas un détail d'implémentation : il change le coût des opérations d'un facteur de plusieurs milliers, et une représentation mal adaptée est la raison la plus fréquente pour laquelle un algorithme correct s'exécute trop lentement. Il existe trois dispositions standard, et elles stockent exactement la même information.

La liste d'arêtes est l'ensemble E écrit tel quel. Elle est compacte, c'est ce que vous fournit un fichier CSV ou une API, et c'est ce que veut l'algorithme de Kruskal, puisqu'il trie les arêtes par poids et ne demande jamais rien sur un sommet particulier. Sa faiblesse : « quels sont les voisins de D ? » impose de parcourir les m lignes.

La matrice d'adjacence est une grille n sur n dont la case (u, v) vaut 1 lorsque l'arête est présente. Vérifier si deux sommets donnés sont adjacents se fait en une seule consultation, et pour les graphes non orientés la matrice est symétrique, elle stocke donc chaque information deux fois. Le prix à payer est l'espace : n au carré cases, qu'il y ait des arêtes ou non. C'est aussi la porte d'entrée des méthodes spectrales, où les valeurs propres de la matrice, ou du laplacien qui lui est étroitement lié, révèlent les regroupements et la connexité, le sujet de la théorie spectrale des graphes en apprentissage automatique.

La liste d'adjacence conserve, pour chaque sommet, la liste de ses voisins. Itérer sur les voisins de v coûte O(deg v), ce qui est optimal, et l'espace total est O(n + m). C'est le choix par défaut en pratique, et la disposition que supposent tous les parcours qui suivent.

Ce qui tranche la question en pratique, c'est que les réseaux réels sont creux : le nombre moyen de voisins reste de l'ordre de quelques dizaines quelle que soit la taille du réseau, car les carrefours ont trois ou quatre routes et les personnes un nombre limité d'amis. Pour un graphe d'un million de sommets et cinq millions d'arêtes, la liste d'adjacence contient environ dix millions d'entrées, alors que la matrice nécessiterait mille milliards de cases, plusieurs téraoctets pour un graphe qui tient par ailleurs sans peine en mémoire. Utilisez la matrice lorsque le graphe est petit, réellement dense ou destiné à l'algèbre linéaire ; sinon, utilisez la liste d'adjacence. Le traitement approfondi, y compris les formats compressés par lignes (CSR), se trouve dans représentation des graphes.

Construire une liste d'adjacence à partir d'une liste d'arêtes prend quatre lignes, et le commentaire du milieu est précisément ce que les débutants se trompent à faire :

edges = [('A','B'), ('A','C'), ('B','C'), ('B','D'),
         ('C','E'), ('D','E'), ('D','F'), ('F','G')]

graph = {v: [] for v in 'ABCDEFG'}   # partir de V, pour que les sommets isolés survivent
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)               # omettre cette ligne pour un graphe orienté

Partir de l'ensemble des sommets plutôt que des arêtes est ce qui garde les sommets isolés dans le graphe. Construisez le dictionnaire au fil de l'eau à partir de la liste d'arêtes, et tout sommet sans arête disparaît silencieusement, ce qui change n et fausse tous les calculs qui divisent par lui.

10. Parcours : en largeur et en profondeur

Presque tout algorithme de graphe est un parcours assorti d'un peu de comptabilité. Il y en a deux, ils diffèrent par une seule structure de données, et comprendre cette différence est l'heure la plus rentable qu'un débutant puisse consacrer au sujet. Tous deux partent d'un sommet, maintiennent une collection de sommets découverts mais pas encore traités, et répètent : en retirer un, examiner ses voisins, ajouter les nouveaux. Le parcours en largeur les retire dans l'ordre où ils sont entrés, à l'aide d'une file. Le parcours en profondeur retire le plus récemment ajouté, à l'aide d'une pile ou de la pile d'appels d'une fonction récursive. Ce seul choix produit deux formes d'exploration complètement différentes.

Voici le parcours en largeur complet, qui renvoie l'ordre de visite, la distance au départ et l'arbre des parents qui permet de reconstruire les itinéraires réels :

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()          # une file : premier entré, premier sorti
        order.append(u)
        for v in graph[u]:
            if v not in dist:        # pas encore découvert
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return order, dist, parent

order, dist, parent = bfs(graph, 'A')
# order  ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# dist   {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}

La propriété importante se trouve dans le dictionnaire dist . Comme BFS termine une couche entière avant de commencer la suivante, la première fois qu'il atteint un sommet, il a utilisé le moins d'arêtes possible, donc BFS résout le problème du plus court chemin dans les graphes non pondérés en O(n + m). Recourir à Dijkstra quand toutes les arêtes coûtent la même chose, c'est du travail gaspillé.

Le parcours en profondeur est le même squelette, avec une pile au lieu d'une file :

def dfs(graph, start):
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()              # une pile : dernier entré, premier sorti
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]): # inversé, pour que le premier voisin soit pris en premier
            if v not in seen:
                stack.append(v)
    return order

dfs(graph, 'A')   # ['A', 'B', 'C', 'E', 'D', 'F', 'G']

DFS ne donne pas de distances, et le résultat utile est l'ordre dans lequel il termine les sommets plutôt que l'ordre dans lequel il les commence. C'est à partir de cet ordre de fin que sont construits le tri topologique, la détection de cycles, les composantes fortement connexes et la recherche de ponts, dans le sillage de l'article de Tarjan de 1972 qui a fait du parcours en profondeur non plus une technique mais une boîte à outils.

Une comparaison plus complète des deux, y compris les bugs auxquels chacun expose, se trouve dans BFS contre DFS.

11. Les problèmes classiques et leurs algorithmes

Une fois le parcours acquis, le catalogue standard est à portée de main. Chacun de ces problèmes est une question que l'on se pose réellement sur des réseaux réels, et chacun a un algorithme qui porte un nom.

Plus courts chemins. Sans poids, BFS y répond. Avec des poids positifs ou nuls, l'algorithme de Dijkstra, publié dans une note de trois pages en 1959, fixe les sommets par ordre croissant de distance et s'exécute en O(m + n log n) avec une bonne file de priorité. Avec des poids négatifs, l'hypothèse centrale de Dijkstra tombe et il vous faut Bellman-Ford, qui relâche chaque arête n-1 fois en O(nm) et détecte en prime les cycles négatifs. Pour toutes les paires à la fois, Floyd-Warshall le fait en O(n3) avec trois boucles imbriquées, et quand vous avez une destination et une estimation raisonnable de la distance restante, la recherche A* s'en sert pour n'examiner qu'une fraction du graphe. L'arbre de décision complet se trouve dans algorithmes de plus court chemin.

Arbres couvrants de poids minimum. Trouver l'ensemble d'arêtes le moins coûteux qui garde un graphe pondéré connexe. L'algorithme de Kruskal trie les arêtes et ajoute toute arête qui ne ferme pas de cycle, en utilisant une structure union-find pour le vérifier en temps quasi constant ; celui de Prim fait croître un seul arbre vers l'extérieur, en prenant toujours l'arête la moins chère qui en sort. Tous deux sont gloutons, tous deux sont optimaux de façon démontrable, et tous deux s'exécutent en O(m log n). C'est l'algorithme qui permet de poser des câbles et de la fibre au moindre coût, et on le retrouve aussi dans des méthodes de clustering.

Ordonnancement et flot. Étant donné un DAG de dépendances, le tri topologique produit un ordre dans lequel chaque tâche vient après ce dont elle dépend, en O(n + m), et il échoue exactement lorsqu'un cycle existe. Étant donné des canalisations avec des capacités, le flot maximum demande combien on peut faire passer d'une source à un puits ; formalisé par Ford et Fulkerson en 1956, il modélise le trafic, la bande passante, les chaînes d'approvisionnement et, par une réduction standard, le couplage biparti. Voir flot de réseau, flot maximum et coupe minimum.

Coloration. Étiqueter les sommets de sorte que deux sommets adjacents ne partagent jamais la même étiquette, en utilisant le moins d'étiquettes possible. Ce nombre est le nombre chromatique, et il modélise les emplois du temps d'examens, l'attribution de fréquences et l'allocation de registres. Contrairement à tout ce qui précède, ce problème est NP-difficile et la pratique repose sur des heuristiques. Voir le problème de coloration de graphes.

Tournées. Un cycle hamiltonien visite chaque sommet exactement une fois, et le problème du voyageur de commerce demande le moins coûteux. Il ressemble à une petite variante de la question d'Euler de 1736, qui se résout en temps linéaire, et il compte pourtant parmi les problèmes les plus difficiles du catalogue. Son cousin pratique, qui consiste à organiser les tournées d'une flotte depuis un dépôt sous contraintes de capacité, est le problème de tournées de véhicules.

12. Cinq résultats à connaître par leur nom

Un premier cours, c'est en partie un ensemble d'algorithmes et en partie un ensemble de résultats qui façonnent la manière de penser les objets. Le lemme des poignées de main de la section 4 est le premier d'entre eux. Les cinq suivants reviennent tout aussi constamment, en entretien, dans les articles et dans la conversation, et chacun peut s'énoncer en une phrase.

Le critère d'Euler pour parcourir toutes les arêtes (1736, complété par Hierholzer en 1873)

Un graphe connexe possède une piste fermée utilisant chaque arête exactement une fois si et seulement si tous ses sommets sont de degré pair, et une piste ouverte si et seulement si exactement deux sommets sont de degré impair. C'est le genre de théorème précieux : il transforme une recherche dans un espace immense d'itinéraires en une vérification qui se fait en comptant, en temps linéaire.

La formule d'Euler pour les graphes planaires (1758)

Dessinez un graphe planaire connexe sans croisement et soit f le nombre de faces, en comptant la région extérieure non bornée. Alors

n - m + f = 2

L'exemple récurrent, dessiné comme dans les figures, a n = 7, m = 8 et trois faces : le triangle ABC, le quadrilatère BCED et la région extérieure, et on a bien 7 - 8 + 3 = 2. Le corollaire a de vraies conséquences : tout graphe planaire simple ayant au moins trois sommets vérifie m ≤ 3n - 6, donc les graphes planaires sont toujours creux, et K5 , avec ses 5 sommets et 10 arêtes, ne peut pas être planaire puisque 3n - 6 vaut 9. Le théorème de Kuratowski de 1930 complète le tableau : un graphe est planaire exactement lorsqu'il ne contient aucune subdivision de K5 ni de K3,3. Hopcroft et Tarjan ont montré en 1974 que la planarité peut être testée en temps linéaire.

Le théorème des quatre couleurs (Appel et Haken, 1976)

Tout graphe planaire peut être correctement coloré avec au plus quatre couleurs, donc aucune carte n'a besoin de plus de quatre couleurs pour que des pays ayant une frontière commune soient différenciés. Francis Guthrie a posé la question en 1852 et elle a résisté à toute démonstration pendant 124 ans. L'argument finalement trouvé a réduit le problème à un ensemble fini de configurations, vérifiées par ordinateur, ce qui a lancé un véritable débat philosophique sur ce qu'est une démonstration ; il a été simplifié en 1997 par Robertson, Sanders, Seymour et Thomas, puis vérifié formellement en Coq par Georges Gonthier en 2005. Notez l'asymétrie : quatre couleurs suffisent toujours, mais décider si trois suffisent est NP-complet.

Le théorème de Kőnig (1931)

Dans un graphe biparti, la taille d'un couplage maximum est égale à la taille d'une couverture par sommets minimum. Un couplage est un ensemble d'arêtes sans extrémité commune, une façon d'associer des personnes à des postes ; une couverture par sommets est un ensemble de sommets touchant toutes les arêtes. Deux problèmes d'optimisation apparemment sans rapport ont la même réponse : c'est la première dualité que rencontrent la plupart des étudiants, et c'est elle qui rend le couplage maximum calculable en temps polynomial. Dans les graphes quelconques, l'égalité tombe et la couverture par sommets minimum est NP-difficile.

Le théorème flot maximum, coupe minimum (Ford et Fulkerson, 1956)

Dans tout réseau de flot, le flot maximum de la source au puits est égal à la capacité totale de la plus petite coupe qui les sépare : le maximum que l'on peut faire passer est exactement ce que permet le goulot d'étranglement le plus serré. C'est encore la dualité, sous sa forme la plus citée, qui transforme une maximisation sur tous les flots en une minimisation sur toutes les coupes. Elle sous-tend la segmentation d'images, la sélection de projets et l'analyse de fiabilité, et le théorème de Kőnig en découle comme cas particulier.

13. Ce qui est facile, ce qui est difficile, et pourquoi c'est important

La chose la plus importante en pratique qu'un débutant puisse apprendre sur les graphes n'est pas un algorithme. C'est que deux problèmes peuvent s'énoncer presque avec les mêmes mots et se situer de part et d'autre d'un immense fossé calculatoire. Trouver le plus court chemin entre deux sommets prend quelques millisecondes sur un graphe de plusieurs millions de sommets ; trouver le plus long chemin élémentaire entre les deux mêmes est NP-difficile et sans espoir au-delà de quelques dizaines de sommets. Décider si un graphe possède une piste fermée utilisant chaque arête une fois est une vérification de degrés en temps linéaire ; décider s'il possède un cycle passant une fois par chaque sommet est NP-complet. Décider si deux couleurs suffisent se fait en un seul BFS ; décider si trois suffisent est NP-complet.

L'énoncé formel est qu'une grande famille de problèmes de graphes est NP-complète, une notion introduite par Cook en 1971 et dotée de son premier catalogue substantiel par Richard Karp en 1972, dont la célèbre liste de 21 problèmes est dominée par des problèmes de graphes : clique, couverture par sommets, circuit hamiltonien, nombre chromatique, ensemble d'arcs de rétroaction, et d'autres. Aucun algorithme en temps polynomial n'est connu pour l'un d'eux, et un tel algorithme pour l'un d'eux en donnerait un pour tous. Personne ne s'attend à ce que cela arrive.

La conséquence pratique n'est pas le désespoir, mais un changement de question. Quand un problème tombe dans la colonne de droite, vous cessez de réclamer l'optimum et vous choisissez parmi quatre stratégies honnêtes :

• Accepter une approximation. Pour le TSP métrique, l'algorithme de Christofides de 1976 garantit en temps polynomial une tournée d'au plus 1,5 fois l'optimum.
• Utiliser une heuristique et la mesurer. La recherche locale, comme 2-opt ou le recuit simulé, arrive régulièrement à quelques pour cent de l'optimum sur des milliers de villes, sans la moindre garantie.
• Exploiter la structure de vos instances. Difficile en général ne veut pas dire difficile pour vous : la coloration est facile sur les graphes cordaux, beaucoup de problèmes sont faciles sur les arbres et sur les graphes de faible largeur arborescente, et les réseaux routiers ont une géométrie que les algorithmes de routage spécialisés exploitent sans pitié.
• Résoudre exactement des instances plus petites. Les solveurs de programmation en nombres entiers prouvent couramment l'optimalité d'instances du TSP comptant des milliers de villes. Exponentiel ne veut pas dire impossible, cela veut dire que le plafond arrive vite.

Une mise en garde : « NP-difficile » décrit les pires cas à mesure que l'entrée grandit, pas un verdict sur votre problème particulier. Un traitement plus complet du coût de chaque algorithme se trouve dans algorithmes de graphes et complexité.

14. Où les graphes apparaissent réellement

Affirmer que la théorie des graphes est partout est facile, et cela mérite d'être étayé. Voici où le contenu de cet article travaille en ce moment même, sur l'appareil sur lequel vous lisez ces lignes.

Navigation. Toute application d'itinéraires modélise le réseau routier comme un graphe orienté pondéré, les carrefours comme sommets et les tronçons de route comme arcs pondérés par le temps de trajet prévu. La requête est un plus court chemin et l'algorithme est un descendant très optimisé de Dijkstra et d'A*, qui utilise des hiérarchies précalculées pour qu'un itinéraire à l'échelle d'un continent ne touche que quelques milliers de sommets au lieu de dizaines de millions. Les rues à sens unique expliquent pourquoi le graphe doit être orienté ; le trafic en temps réel explique pourquoi les poids changent de minute en minute.

Recherche et réseaux sociaux. Le web est un graphe orienté de pages et de liens, et PageRank, décrit par Brin et Page en 1998, classe une page selon la probabilité qu'un internaute aléatoire suivant des liens y aboutisse, ce qui revient à un calcul de vecteur propre sur la structure d'adjacence. Sur les réseaux sociaux, les personnes sont des sommets et les relations des arêtes : l'expérience des lettres de Milgram en 1967 a donné les célèbres « six degrés de séparation », et une analyse de 2012 portant sur l'ensemble du graphe de Facebook a établi la distance moyenne entre deux utilisateurs à 4,74. La détection de communautés, la recommandation d'amis et l'estimation de l'influence sont toutes des calculs de graphes standard exécutés à grande échelle.

Génie logiciel. Les systèmes de build, les gestionnaires de paquets et les moteurs de tableur maintiennent un DAG et le trient topologiquement. L'historique d'un gestionnaire de versions est un DAG de commits, et une fusion est une question d'ancêtres communs. Les compilateurs construisent des graphes de flot de contrôle pour l'optimisation et des graphes d'interférence pour l'allocation de registres, où attribuer les registres revient littéralement à colorer un graphe, et l'élimination du code mort est une requête d'accessibilité. Voir la théorie des graphes en génie logiciel.

Logistique. L'organisation des livraisons est le problème de tournées de véhicules, l'implantation d'entrepôts relève de la localisation d'installations, et les chaînes d'approvisionnement sont des réseaux de flot avec capacités. Ici, l'écart entre un bon et un mauvais algorithme se mesure en carburant et en masse salariale, et la discipline qui l'étudie est la recherche opérationnelle.

Sciences et apprentissage automatique. Une molécule est un graphe d'atomes et de liaisons, et interroger une base de données chimique relève de l'isomorphisme de sous-graphes. L'assemblage de génomes reconstitue une séquence en trouvant un chemin eulérien dans un graphe de De Bruijn, ce qui permet au critère d'Euler de 1736 de gagner sa vie 280 ans plus tard. Le clustering spectral partitionne les données à l'aide des vecteurs propres d'un laplacien de graphe, et les réseaux de neurones sur graphes généralisent la convolution aux structures irrégulières en faisant circuler des messages le long des arêtes. Les réseaux électriques et de télécommunications sont analysés pour y trouver ponts et sommets d'articulation, car c'est là que commencent les défaillances en cascade. Un panorama plus large se trouve dans applications de la théorie des graphes.

15. Les erreurs que les débutants commettent immanquablement

Ce sont les erreurs qui reviennent sans cesse dans le code des étudiants, en entretien et dans les bugs de production. Chacune est facile à éviter une fois qu'on l'a vue nommée.

• Perdre les sommets isolés. Construire le graphe à partir d'une liste d'arêtes signifie qu'un sommet sans arête n'apparaît jamais. L'ordre n change silencieusement, les moyennes sont fausses et le nombre de composantes est sous-estimé. Construisez d'abord l'ensemble des sommets.
• Marquer comme visité trop tard dans BFS. Marquez un sommet au moment où vous l'ajoutez à la file, pas au moment où vous l'en retirez. Le marquer au retrait permet au même sommet d'entrer dans la file une fois par arête incidente, ce qui transforme un algorithme linéaire en problème de mémoire.
• Lancer BFS sur un graphe pondéré. BFS minimise le nombre d'arêtes, pas leur poids total. Dans un graphe où un itinéraire de deux arêtes coûte 100 et un itinéraire de cinq arêtes coûte 5, BFS renvoie avec assurance le plus cher. Les graphes pondérés ont besoin de Dijkstra.
• Lancer Dijkstra avec des poids négatifs. Dijkstra suppose qu'une fois un sommet fixé, aucun itinéraire moins coûteux vers lui ne peut apparaître plus tard. Une arête négative brise cette hypothèse, et le résultat est faux silencieusement au lieu de produire une erreur. Utilisez Bellman-Ford.
• Compter la longueur d'un chemin en sommets. La longueur est le nombre d'arêtes, donc un chemin passant par cinq sommets est de longueur 4. C'est la source d'une grande partie des erreurs de décalage d'une unité dans le code de plus court chemin.
• Ignorer à quelle famille appartient le graphe. Un algorithme correct sur les graphes non orientés peut être silencieusement faux sur les graphes orientés, et un résultat démontré pour les graphes simples peut échouer sur un multigraphe. Vérifiez la famille avant de choisir l'algorithme.
• Supposer que le graphe est connexe. Les données réelles arrivent en morceaux. Vérifiez le nombre de composantes avant de vous fier à une distance, un diamètre ou une moyenne.
• Récurser trop profondément dans DFS. Un DFS récursif sur un chemin d'un million de sommets nécessite un million de cadres de pile. Écrivez la version itérative quand l'entrée peut être grande.
• N'ajouter qu'un seul sens dans un graphe non orienté. Une arête non orientée doit figurer dans les deux listes d'adjacence. Omettre le second append produit un graphe qui semble juste sur un dessin et se comporte comme un digraphe dans tous les parcours.
• Croire le dessin. Deux arêtes qui se croisent sur une image ne signifient rien. Seuls les ensembles comptent, et c'est pourquoi « ce graphe est-il planaire ? » est une vraie question, et non quelque chose que l'on tranche en plissant les yeux devant un schéma.
• Supposer que n - 1 arêtes signifient un arbre. Ce n'est vrai qu'avec la connexité, ou avec l'absence de cycle. Un triangle plus un sommet isolé a 4 sommets et 3 arêtes, et ce n'est pas un arbre.

16. Pour aller plus loin

L'étape suivante la plus utile est de construire un graphe et d'y exécuter quelque chose, plutôt que de lire d'autres définitions. Saisissez l'exemple récurrent dans le visualiseur interactif, lancez le parcours en largeur depuis A et regardez les couches se remplir, puis lancez le parcours en profondeur depuis le même sommet et comparez l'ordre. Quatre-vingt-dix secondes de cet exercice font ce qu'aucune quantité de prose ne peut faire.

Ensuite, l'enchaînement naturel suit l'ordre de cet article : vocabulaire, parcours, plus courts chemins pondérés, arbres couvrants, puis les problèmes plus difficiles. La feuille de route de la théorie des graphes présente ce parcours avec un calendrier, et les leçons structurées le suivent de manière interactive. Pour les entretiens techniques, le guide théorie des graphes pour les entretiens techniques couvre les schémas qui reviennent réellement, avec en complément l'aide-mémoire des algorithmes.

Côté manuels : l'ouvrage de West, Introduction to Graph Theory , est le cours de licence standard sous forme de livre, celui de Diestel, Graph Theory , est la référence de niveau master et la source de la définition de la section 2, et les chapitres sur les graphes de Cormen, Leiserson, Rivest et Stein restent la présentation la plus claire des implémentations. Une comparaison plus complète, incluant des cours et des séries de vidéos, se trouve dans les meilleures ressources pour apprendre la théorie des graphes.

17. Glossaire

Tous les termes employés ci-dessus, réunis en un seul endroit.

19. Références

Les définitions, théorèmes, dates et bornes de complexité ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (paru en 1741), 128 à 140. Le mémoire sur les ponts de Königsberg.
2. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4, 109 à 140. La formule des polyèdres derrière n - m + f = 2.
3. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 à 508.
4. Hierholzer, C. (1873). "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 à 32.
5. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. Le premier emploi moderne du mot « graphe ».
6. Cayley, A. (1889). "A theorem on trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 à 378.
7. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 à 283.
8. König, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 à 119.
9. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
10. Ford, L. R. et Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 à 404.
11. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society 7(1), 48 à 50.
12. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal 36(6), 1389 à 1401.
13. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269 à 271.
14. Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM 5(6), 345.
15. Held, M. et Karp, R. M. (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 à 210.
16. Milgram, S. (1967). "The small world problem." Psychology Today 2(1), 60 à 67.
17. Cook, S. A. (1971). "The complexity of theorem-proving procedures." Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151 à 158.
18. Karp, R. M. (1972). "Reducibility among combinatorial problems." Dans Complexity of Computer Computations, 85 à 103. New York : Plenum Press.
19. Tarjan, R. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 à 160.
20. Hopcroft, J. et Tarjan, R. (1974). "Efficient planarity testing." Journal of the ACM 21(4), 549 à 568.
21. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Rapport 388, Carnegie Mellon University.
22. Appel, K. et Haken, W. (1977). "Every planar map is four colorable." Illinois Journal of Mathematics 21(3). Partie I, 429 à 490 ; Partie II, avec J. Koch, 491 à 567.
23. Fredman, M. L. et Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM 34(3), 596 à 615.
24. Brin, S. et Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 à 7), 107 à 117.
25. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall.
26. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
27. Gonthier, G. (2008). "Formal proof: the four-color theorem." Notices of the American Mathematical Society 55(11), 1382 à 1393.
28. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, Massachusetts : MIT Press.
29. Backstrom, L., Boldi, P., Rosa, M., Ugander, J. et Vigna, S. (2012). "Four degrees of separation." Proceedings of the 4th Annual ACM Web Science Conference, 33 à 42.
30. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Source de la définition citée à la section 2.