Arbre couvrant minimal : Kruskal et Prim

Choisissez Douze villages et suivez Kruskal étape par étape. Il examine les 66 routes possibles de la plus courte à la plus longue : K–L, qui mesure 13,89 km, est donc retenue immédiatement. C–D et B–C sont écartées, car le chemin tracé en rouge relie déjà leurs extrémités. Passez à Prim, qui développe un réseau unique à partir de A. L’ordre change, K–L arrive en dernier, les deux mêmes routes sont écartées, et l’on retrouve les mêmes 11 routes pour un total de 199,04 km. Les deux algorithmes appliquent la même règle, appelée propriété de la coupe : quelle que soit la manière de répartir les points en deux groupes, la route la plus courte entre ces groupes appartient à l’arbre couvrant minimal, dès lors que toutes les longueurs sont différentes. Si on l’omet, le chemin qui relie ses extrémités dans l’arbre traverse nécessairement la coupe par une route plus longue ; remplacer celle-ci raccourcit l’arbre. À chaque étape de Prim, le réseau ombré forme l’un des côtés d’une telle coupe. Choisissez maintenant Plus proche voisin. Cet algorithme diffère de Prim sur un point : il ne cherche qu’à partir du dernier village atteint, au lieu de considérer tout le réseau. À sa troisième étape, il retient D–F, longue de 17,96 km, alors que A–C traverse la coupe en 17,67 km. Il délaisse encore A–C à sept reprises et termine avec 10,76 % de longueur supplémentaire. Otakar Borůvka, qui résolut le problème le premier en 1926 pour concevoir le réseau électrique du sud de la Moravie, l’énonçait pour des points dont les « distances mutuelles sont différentes ». C’est précisément la condition qui empêche Kruskal et Prim de diverger.

Choisissez Villes autour d’un lac. Dix villes bordent un lac ; l’arbre suit la rive, sauf sur un tronçon : la plus grande ouverture, entre J et A. Ces deux villes sont distantes de 25,89 km en ligne droite, mais de 128,30 km le long de l’arbre, soit 4,96 fois plus, car l’unique trajet de l’une à l’autre parcourt tout le réseau. Le trait violet en pointillé signale cette paire. Déplacez une ville : la page repère aussitôt le nouveau détour maximal. Un arbre couvrant minimal réduit autant que possible la longueur totale, sans rien garantir sur la distance entre deux villes particulières. Construire aussi la route de 25,89 km rendrait direct le trajet de A à J. Reste à savoir si ce gain justifie la route supplémentaire. C’est une question de plus court chemin, reprise dans la page consacrée à l’algorithme de Dijkstra.

Choisissez Trois villes. Elles sont distantes de 40 km, et l’arbre mesure donc 80,00 km. Un carrefour central où trois routes se rencontrent à 120° les relie en 69,28 km, soit 13,40 % de moins ; cette économie vaut 1 − √3/2. Choisissez Quatre villes en carré : deux carrefours font gagner 8,93 %. Revenez au triangle et faites descendre C vers A et B. Dès que l’angle en C dépasse 120°, le carrefour rejoint C ; au-delà, aucun carrefour n’apporte plus rien. La recherche des meilleurs carrefours constitue le problème de l’arbre de Steiner. En 1968, Edgar Gilbert et Henry Pollak ont conjecturé que le triangle équilatéral représente le pire cas : pour tout ensemble de points du plan, la longueur d’un arbre de Steiner serait au moins égale à √3/2 de celle de son arbre couvrant minimal. Du et Hwang ont publié une démonstration en 1990. En 2010, Innami et trois collègues ont présenté des éléments indiquant qu’une étape essentielle de cette preuve était fausse. Puis, en 2012, Ivanov et Tuzhilin, qui en signalaient les lacunes depuis 2002, ont écrit que la conjecture restait ouverte. Un recueil de problèmes ouverts sur les arbres de Steiner paru en 2025 la donne encore comme telle. Nul ne sait si une disposition de points permet d’économiser davantage que les 13,40 % du triangle.