On considère un ensemble fini S de points du plan, que l'on
souhaite relier par des segments, de façon à ce qu'il existe un
chemin entre 2 points quelconques de S (i.e. que le graphe formé
par les points et les segments soit connexe), et que la somme des
longueurs des segments soit minimale.
Il s'agit d'un problème classique d'algorithmique, connu sous le
nom de recherche d'ARPM (Arbre Recouvrant de Poids Minimal),
facilement (et rapidement) résolu par
l'algorithme
de Kruskal. La solution optimale est un arbre, i.e. un graphe
sans cycle (c'est un petit raisonnement très simple).
L'applet ci-dessous illustre cet algorithme. L'ARPM
est tracé en bleu à chaque modification de S.
Click gauche: ajouter/déplacer un point
Click sur un point existant: supprimer un point
Il y a de nombreuses applications à des problèmes réels (ou
souvent à des versions un peu naïves de problèmes réels):
minimiser la longueur de cables pour relier des serveurs en ligne
droite, le nombre de km d'oléoducs nécessaires pour relier des
villes, etc.
Formulation du problème euclidien de Steiner
Le problème Euclidien de Steiner est le même, si ce n'est que l'on
s'autorise à rajouter de nouveaux points - appelés «points de
Steiner», permettant le cas échéant de diminuer la somme des
distances des segments. Autrement dit:
Problème Euclidien de Steiner :
Étant donné un ensemble fini S de points du plan, trouver :
un ensemble fini T de points du plan (appelés points de Steiner)
un ensemble de segments E d'extrémité dans S ∪ T
tels que
(S ∪ T,E) forme un graphe connexe.
la somme des longueurs des segments de E soit minimale
Le cas à 3 points est parfaitement connu et résolu de façon
exacte: si le triangle formé par les 3 points a un angle supérieur
à 2π/3, il ne faut pas rajouter de point de Steiner pour
obtenir un arbre minimal. Sinon, il faut rajouter un point de
Steiner, qui est
le point
de Fermat du triangle (qui est constructible géométriquement
très simplement). Prouver la minimalité dans ce cas est un
exercice de géométrie accessible en Terminale S.
L'applet suivante permet de générer des triangles aléatoires, ou d'en construire à la main, et d'en calculer le point de Fermat (si celui-ci existe).
Click gauche: ajouter/déplacer un point
Click sur un point existant: supprimer un point
Longueur totale de l'arbre sans point de Fermat:
Longueur totale de l'arbre avec point de Fermat:
Le cas général à n points est un problème nettement plus
compliqué. Il s'agit en fait d'un problème NP-difficileMuni d'une
solution, on ne sait même pas déterminer par un algorithme
s'exécutant en temps polynomial si elle est optimale ou non..
On dispose cependant de résultats théoriques intéressants:
Si l'on a une configuration avec au moins un point de Steiner de degré 1 ou 2 (i.e. relié à 1 ou 2 autres points), on peut améliorer (au sens large) le score en supprimant ce point. (Facile à prouver.)
Les points de Steiner d'une configuration optimale sont - après suppression d'éventuels points inutiles de degré 1 ou 2 (cf le point précédent) - de degré 3. Les segments qui relient chacun de ces points à ces 3 voisins forment des angles de 2π/3 entre eux. (Un peu moins facile : voir cette page pour une preuve.)
Le problème admet un minimum global, pour lequel le nombre de points de Steiner est au plus n-2. (Le n-2 se prouve par un argument sur les degrés, l'existence d'un minimum global par un argument de compacité.)
L'applet suivante permet de se faire une intuition de ces
différentes propriétés. Les points de Steiner ajoutés sont
automatiquement optimisés localement (grace à une descente
de gradient sur la fonction qui à la position d'un point de
Steiner associe la somme des distances à ses voisins). Le dernier
bouton détecte les angles inférieurs 2π/3 dans l'ARPM, et
ajoute les points de Fermat correspondant.
Click gauche: ajouter/déplacer un point
Click droit: ajouter un point de Steiner
Click sur un point existant: supprimer un point
Points fixes:
Points de Steiner:
Longueur totale de l'arbre sans points de Steiner:
Longueur totale de l'arbre avec points de Steiner: