Arbres couvrants minimaux

En 1926, on demanda à Otakar Borůvka de planifier le réseau électrique du sud de la Moravie au moindre coût. Sa question, comment relier chaque lieu avec la plus petite longueur totale de ligne, est le problème de l'arbre couvrant minimal, et elle a certaines des réponses les plus simples et les plus élégantes de toute l'informatique.

Un graphe dont les arêtes ont des longueurs, avec en surbrillance les arêtes courtes d'un arbre qui grandit, en pointillés rouges une arête passée qui fermerait un cycle, et dessous la liste des arêtes encore à essayer
Un graphe dont les arêtes ont des longueurs, avec en surbrillance les arêtes courtes d'un arbre qui grandit, en pointillés rouges une arête passée qui fermerait un cycle, et dessous la liste des arêtes encore à essayer

Le problème

Prenez un graphe connexe dont les arêtes ont des longueurs, ou des coûts. Un arbre couvrant est un ensemble d'arêtes qui relie tous les nœuds et ne contient aucun cycle ; avec n nœuds, il a toujours exactement n − 1 arêtes, car chaque arête relie un nœud de plus. Parmi tous les arbres couvrants, un arbre couvrant minimal a la plus petite longueur totale. Un graphe peut avoir un nombre énorme d'arbres couvrants, mais inutile de tous les essayer.

Pourquoi l'approche gloutonne marche

Séparez les nœuds en deux groupes, comme vous voulez. La plus courte arête qui va d'un groupe à l'autre appartient toujours à un arbre couvrant minimal : si un arbre utilisait à la place une arête plus longue entre les groupes, l'échanger contre la plus courte relierait les mêmes nœuds pour moins cher. C'est la propriété de la coupe. Le revers de la médaille est la propriété du cycle : la plus longue arête d'un cycle n'est jamais nécessaire. Les deux algorithmes ci-dessous ne font qu'appliquer ces règles, encore et encore.

Un exemple

Prenez les arêtes A–B de longueur 1, B–C 2, A–C 3, C–D 4 et B–D 5. L'algorithme de Kruskal prend A–B, puis B–C, puis passe A–C, car A et C sont déjà reliés et elle fermerait un cycle, puis prend C–D. L'arbre a trois arêtes pour quatre nœuds, il est donc terminé, avec une longueur totale de 7, et B–D n'est même jamais examinée. L'algorithme de Prim depuis A ajoute d'abord B par A–B ; l'arête B–C (2) de B bat A–C (3) comme accès à C, donc C rejoint l'arbre par B–C ; l'arête C–D (4) de C bat B–D (5), donc D le rejoint par C–D. Le même arbre, le même 7.

Kruskal, Prim et Borůvka

L'algorithme de Kruskal, publié par Joseph Kruskal en 1956, trie les arêtes et utilise une structure union-find pour passer les arêtes internes à un morceau, donc son travail croît en E log E. L'algorithme de Prim a d'abord été décrit par Vojtěch Jarník en 1930, puis redécouvert par Robert Prim en 1957 et par Edsger Dijkstra en 1959 ; avec un tas binaire, son travail croît en E log V, et avec un simple tableau en V², ce qui convient aux graphes denses. L'algorithme de Borůvka, de 1926, laisse chaque morceau prendre en même temps sa plus courte arête sortante, ce qui convient aux ordinateurs parallèles.

Otakar Borůvka en 1981. En 1926, on lui demanda de planifier au moindre coût le réseau électrique de la Moravie du Sud, et il donna le premier algorithme d’arbre couvrant de poids minimal.
Otakar Borůvka en 1981. En 1926, on lui demanda de planifier au moindre coût le réseau électrique de la Moravie du Sud, et il donna le premier algorithme d’arbre couvrant de poids minimal.

Usages

Les arbres couvrants minimaux servent à concevoir des réseaux bon marché de câbles, de conduites et de routes. Ils regroupent des données en clusters : retirez les plus longues arêtes de l'arbre, et les morceaux qui restent sont les clusters. Ils donnent vite une tournée pour le problème du voyageur de commerce, au plus deux fois plus longue que la meilleure quand les distances respectent l'inégalité triangulaire. Et l'algorithme de Kruskal ou de Prim sur une grille aux longueurs d'arêtes aléatoires est une façon classique de générer un labyrinthe.

À vous de jouer

Ouvrez l'application, choisissez Kruskal ou Prim, et appuyez sur Étape. Avec Kruskal, les arêtes encore à essayer sont listées sous le graphe, de la plus courte à la plus longue ; les arêtes qui fermeraient un cycle sont tracées en pointillés rouges. Avec Prim, les nœuds en attente sont listés avec la longueur de leur meilleure arête, tracée en pointillés. Lancez les deux sur le même graphe et comparez : l'ordre diffère, mais la longueur totale est toujours la même.

Questions fréquemment posées

Combien d'arêtes a un arbre couvrant ?

Exactement une de moins que le nombre de nœuds. Avec moins d'arêtes, on ne pourrait pas relier tous les nœuds, et une de plus créerait toujours un cycle.

Lequel est le plus rapide, Kruskal ou Prim ?

L'algorithme de Kruskal, qui trie les arêtes, est en général plus simple et rapide sur les graphes creux, qui ont peu d'arêtes. L'algorithme de Prim avec un tas s'en sort bien sur les graphes denses, et avec un simple tableau il lui faut environ V² étapes, quel que soit le nombre d'arêtes.

Qu'est-ce que l'union-find ?

Une structure de données qui retient quels nœuds sont dans le même morceau. Elle répond à « ces deux-là sont-ils reliés ? » et fusionne deux morceaux presque instantanément, exactement ce dont l'algorithme de Kruskal a besoin pour chaque arête.

Un arbre couvrant minimal marche-t-il pour les graphes orientés ?

Pas tel quel. Pour les graphes aux arêtes à sens unique, le problème correspondant est l'arborescence couvrante minimale, que résout l'algorithme de Chu–Liu/Edmonds.

Prêt à l'essayer ?

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

Construire un arbre couvrant minimal