Au XVIIIe siècle, la ville prussienne de Königsberg est traversée par la Pregel, qui enserre deux îles. Sept ponts relient les îles et les rives, et les habitants se demandent s’il est possible de se promener en traversant chaque pont une et une seule fois. Personne n’y parvient, mais personne ne sait prouver que c’est impossible.

En 1736, Leonhard Euler règle la question, et fonde du même coup la théorie des graphes. Son idée est d’oublier tout ce qui ne compte pas : la forme des rives, la longueur des ponts, le tracé des rues. Il ne reste que quatre zones de terre, les sommets, et sept ponts qui les relient, les arêtes. Chaque fois qu’on traverse une zone, on y entre par un pont et on en ressort par un autre : les ponts d’une zone traversée vont par deux. Seules la zone de départ et la zone d’arrivée peuvent avoir un nombre impair de ponts. Or à Königsberg, les quatre zones en ont un nombre impair.
Le nombre d’arêtes qui partent d’un sommet est son degré. Euler a montré qu’une promenade passant une fois par chaque arête, aujourd’hui appelée chemin eulérien, existe si et seulement si le graphe est connexe et compte zéro ou deux sommets de degré impair. Le critère se vérifie d’un coup d’œil, quelle que soit la taille du graphe : inutile d’essayer toutes les promenades.
Königsberg est devenue Kaliningrad, ville russe. Deux des sept ponts ont été détruits par les bombardements de 1944, et deux autres remplacés par une voie rapide. Il en reste cinq, et le problème a changé de réponse : deux zones seulement ont désormais un nombre impair de ponts. La promenade d’Euler est enfin possible, à condition de partir d’une île pour finir sur l’autre.
La somme des degrés vaut toujours le double du nombre d’arêtes, puisque chaque arête a deux bouts. Elle est donc paire, et le nombre de sommets de degré impair l’est aussi. C’est le « lemme des poignées de main » : dans une soirée, le nombre de personnes ayant serré un nombre impair de mains est toujours pair.
Des sommets, et des traits pour les relier : cette simplicité fait la puissance des graphes. Des aéroports et des vols, des carrefours et des rues, des neurones et des synapses, des pages web et des liens, des personnes et des amitiés, des atomes et des liaisons chimiques : tous ces réseaux se décrivent de la même façon, et les mêmes algorithmes s’y appliquent.
Quelques mots suffisent pour en parler :
Deux représentations dominent. La liste d’adjacence associe à chaque sommet la liste de ses voisins, ce qu’un dictionnaire Python fait naturellement. La matrice d’adjacence est un tableau $n\times n$ où la case $(i,j)$ vaut $1$ s’il y a une arête de $i$ vers $j$, et $0$ sinon.
| Opération | Liste d'adjacence | Matrice d'adjacence |
|---|---|---|
| mémoire occupée | $n+m$ | $n^2$ |
| énumérer les voisins d'un sommet | proportionnel à son degré | $n$ |
| tester si deux sommets sont reliés | proportionnel au degré | $1$ |
| trouver les prédécesseurs (graphe orienté) | $n+m$ | $n$ |
Ordres de grandeur, pour un graphe de $n$ sommets et $m$ arêtes.
La plupart des réseaux réels sont creux : chaque sommet n’a que quelques voisins parmi des millions. La matrice y gaspille une place immense en zéros, et la liste d’adjacence l’emporte. La matrice a pourtant un tour dans son sac : le coefficient $(i,j)$ de sa puissance $M^k$ compte les chemins de longueur $k$ qui vont de $i$ à $j$. Un chemin de longueur $k$ est en effet un chemin de longueur $k-1$ vers un sommet intermédiaire, suivi d’une arête, et c’est exactement ce que somme le produit matriciel.
Pour savoir quels sommets on peut atteindre depuis un sommet de départ, il faut explorer le graphe méthodiquement, sans tourner en rond. Deux stratégies s’offrent à nous : le parcours en largeur, qui explore par couches de plus en plus éloignées, comme une onde qui s’étend, et le parcours en profondeur, qui s’enfonce le plus loin possible avant de revenir sur ses pas.
Les deux parcours s’écrivent avec le même code. On range dans une structure les sommets qui restent à voir ; on en retire un, on le marque comme vu s’il ne l’est pas déjà, et l’on range ses voisins. Tout dépend de l’élément qu’on retire. Avec une file, on retire le premier arrivé, comme dans une file d’attente : c’est le parcours en largeur. Avec une pile, on retire le dernier arrivé, comme dans une pile d’assiettes : c’est le parcours en profondeur.
Chaque sommet est marqué une fois, et chaque arête examinée une fois (deux fois si elle n’est pas orientée) : les deux parcours coûtent un temps proportionnel à $n+m$. En Python, L.pop(0) décale toute la liste et coûte cher sur de grandes listes ; la structure deque du module collections retire en temps constant aux deux bouts.
L’animation ci-dessous parcourt le graphe des quartiers d’une ville, des Minimes jusqu’au Stade. Les poids des arcs sont des durées de trajet. On peut y suivre le contenu de la structure et l’ordre dans lequel les sommets sont vus.
Le parcours en largeur trouve le chemin qui compte le moins de tronçons : il atteint d’abord tous les sommets à distance $1$, puis tous ceux à distance $2$, et ainsi de suite. Le parcours en profondeur, lui, trouve un chemin quelconque. Dans un labyrinthe, la différence saute aux yeux : la largeur progresse comme une tache d’encre, la profondeur comme un explorateur qui suit un mur.
La pile du parcours en profondeur n’est autre que la pile d’exécution d’une fonction récursive, qui s’écrit alors en quelques lignes :
def profondeur(G, s, vus):
vus.add(s)
for v in G[s]:
if v not in vus:
profondeur(G, v, vus)
return vus
En 1967, le psychologue Stanley Milgram demande à des habitants du Nebraska de faire parvenir une lettre à un agent de change de Boston, en ne la confiant qu’à des connaissances qu’ils tutoient. Les lettres qui arrivent ont changé de mains environ six fois : c’est l’origine de l’expression « six degrés de séparation ». En 2016, Facebook mesure la distance moyenne entre deux de ses utilisateurs, à l’échelle d’un milliard et demi de sommets : $4{,}57$, soit $3{,}57$ intermédiaires seulement.
Les mathématiciens ont leur nombre d’Erdős, la distance à Paul Erdős dans le graphe des cosignatures d’articles ; les cinéphiles leur nombre de Bacon, la distance à l’acteur Kevin Bacon dans le graphe des acteurs ayant tourné ensemble. Dans les deux cas, presque tout le monde est à moins de cinq ou six pas. Pourquoi un monde si petit ? Si chacun a $k$ amis, on atteint environ $k^d$ personnes en $d$ pas : la distance typique croît comme le logarithme de la population.
Dans l’animation des quartiers, le parcours en largeur rejoint le Stade par l’Hôpital : trois tronçons seulement, mais vingt-neuf minutes de trajet, alors qu’un détour par Tasdon, Lafond et Mireuil n’en demande que vingt. Pour tenir compte des poids, Edsger Dijkstra remplace la file par une file de priorité, dont on retire toujours l’élément de plus petite valeur : ici, le sommet le plus proche du départ parmi ceux qui attendent. Le reste du code ne change pas.
Pourquoi est-ce juste ? Quand un sommet sort de la file de priorité, tous ceux qui attendent sont au moins aussi loin du départ ; comme les poids sont positifs, aucun détour par l’un d’eux ne pourra faire mieux. La distance de ce sommet est donc définitive. L’argument tombe si certains poids sont négatifs, et l’algorithme peut alors se tromper.
En 1956, Edsger Dijkstra, jeune programmeur au Centre mathématique d’Amsterdam, cherche une démonstration frappante pour l’inauguration d’un nouvel ordinateur, l’ARMAC. Il choisit de calculer le plus court trajet entre deux villes des Pays-Bas. « Un matin, je faisais des courses à Amsterdam avec ma jeune fiancée, et, fatigués, nous nous sommes assis à la terrasse d’un café pour boire une tasse de café. J’ai juste réfléchi à la façon de le faire, et j’ai alors conçu l’algorithme du plus court chemin. C’était une invention de vingt minutes. » Sans papier ni crayon, ce qui l’oblige, dira-t-il, à éviter toute complication inutile.
Pour retirer sans cesse le plus petit élément, chercher le minimum dans une liste à chaque tour coûterait un temps proportionnel à sa longueur. Un tas fait bien mieux. C’est un arbre binaire rangé dans une simple liste (les enfants de la case $i$ sont les cases $2i+1$ et $2i+2$) où chaque parent est plus petit que ses enfants : le minimum est toujours à la racine. Pour ajouter un élément, on le place au bout et on le fait remonter tant qu’il est plus petit que son parent ; pour retirer la racine, on la remplace par le dernier élément et on fait redescendre celui-ci. Chaque opération parcourt une seule branche de l’arbre, soit environ $\log_2 n$ étages.
Ce même tas donne un algorithme de tri, le tri par tas : on range tous les éléments dans un tas, puis on les retire un à un, du plus petit au plus grand. Il trie en place, en $n\log n$ opérations même dans le pire cas.
Dijkstra s’étend dans toutes les directions à la fois, sans savoir où se trouve l’arrivée. En 1968, pour guider le robot Shakey de l’institut de recherche de Stanford, Peter Hart, Nils Nilsson et Bertram Raphael lui ajoutent une estimation de la distance restante. La priorité d’un sommet devient le coût déjà payé plus une estimation optimiste de ce qui reste à payer, comme la distance à vol d’oiseau. Tant que l’estimation ne surestime jamais le coût réel, le chemin trouvé reste le meilleur, et la recherche se dirige vers la cible. C’est l’algorithme A*, omniprésent dans les jeux vidéo et les logiciels de navigation.
Sur la carte ci-dessous, l’herbe coûte $1$, le marécage $3$, le lac $10$, et les murs sont infranchissables. Un grand lac barre toujours la ligne droite entre le départ et l’arrivée. Quatre algorithmes partent ensemble, et, à chaque instant, chacun a validé le même nombre de cases :
On veut relier des villes par un réseau électrique, des serveurs par des câbles, des champs par des canaux, en dépensant le moins possible. Le réseau doit être connexe, et il n’a aucun intérêt à contenir un cycle : une arête d’un cycle peut être retirée sans rien déconnecter. On cherche donc un arbre couvrant, qui relie tous les sommets, de poids total minimal.
Essayer tous les arbres est hors de question : Arthur Cayley a montré en 1889 qu’un graphe complet à $n$ sommets en contient $n^{n-2}$, soit plus de $10^{23}$ pour vingt villes. Mais une stratégie gloutonne, qui fait à chaque étape le choix qui semble le meilleur sans jamais revenir dessus, trouve l’arbre optimal. Kruskal examine les arêtes de la plus courte à la plus longue et garde chacune d’elles, sauf si elle fermait un cycle. Prim fait pousser un seul arbre en lui ajoutant toujours l’arête la plus courte qui en sort.
Pour savoir si une arête fermerait un cycle, Kruskal doit savoir si ses deux extrémités sont déjà dans le même morceau. Une structure astucieuse, l’union-find, répond en un temps quasi constant : chaque sommet pointe vers un autre sommet de son morceau, jusqu’à un représentant qui pointe vers lui-même. Deux sommets sont dans le même morceau s’ils ont le même représentant, et fusionner deux morceaux revient à faire pointer un représentant vers l’autre.
Le premier algorithme d’arbre couvrant minimal n’est dû ni à Kruskal ni à Prim, mais au mathématicien tchèque Otakar Borůvka, en 1926. Une compagnie d’électricité lui demande comment relier au moindre coût les villes de la Moravie du Sud. Vojtěch Jarník publie en 1930 la méthode que Prim redécouvrira en 1957, et que Dijkstra retrouvera encore deux ans plus tard. Le labyrinthe de l’animation des parcours, plus haut, est lui-même, à quelques murs près, un arbre couvrant minimal : celui que construit Kruskal sur une grille dont chaque mur a reçu un poids tiré au hasard. On y a ensuite percé quelques murs de plus, pour créer des boucles.
Passer une fois par chaque arête, c’est le problème d’Euler, et le critère des degrés le tranche instantanément. Passer une fois par chaque sommet semble un problème voisin. Il est en réalité d’une tout autre difficulté.
En 1857, l’astronome et mathématicien irlandais William Rowan Hamilton invente le « jeu icosien » : un plateau de vingt villes, reliées par trente routes, sur lequel il faut faire un tour complet en passant une seule fois par chaque ville. Le plateau n’est autre qu’un dodécaèdre aplati : ses vingt sommets vus en perspective à travers l’une de ses faces. Hamilton le vend à un fabricant de jouets pour 25 livres, et le jeu est un échec commercial. Le circuit qu’il demande, passant une fois par chaque sommet et revenant au départ, porte aujourd’hui son nom : un cycle hamiltonien.
Le dodécaèdre compte trente cycles hamiltoniens. Pour les trouver, l’ordinateur n’a pas mieux qu’une exploration systématique : prolonger le chemin tant que c’est possible, et revenir en arrière dans les impasses. On ne connaît aucun critère simple, comparable à celui d’Euler, pour décider si un graphe possède un cycle hamiltonien : le problème est NP-complet. Chercher le plus court d’entre eux, quand les arêtes ont des longueurs, c’est le célèbre problème du voyageur de commerce.