Comment relier des puits de pétrole à une raffinerie par un réseau d'oléoducs de longueur minimum ? Comment concevoir un réseau routier le plus écomique possible reliant des villes données ?

Ces questions sont mathématiquement équivalentes (on remarque que la position précise de la raffinerie n'a pas d'influence sur la longueur du réseau cherché : il suffit de la placer quelque part sur le réseau).

Faisons quelques essais.

(a)

(b)

(c)

(d)

(e)

Pour 4 points en carré, le réseau (b) est plus court que le réseau (a).

Par contre pour les 6 sommets d'un hexagone régulier, (c) s'avère meilleur que (d).

Pour (e), on a placé deux bifurcations au centre des triangles équilatéraux. A vous de voir si on peut faire mieux.

Le problème général, dans le plan ou dans l'espace, fut proposé par le géomètre Steiner dès le début du XX^ème siècle et porte son nom.

Entrées possibles

Entrée 1 - Une solution pour 3, 4 ou 5 points nous aide-t-elle pour plusieurs points ?

Entrée 2 - Même pour des points disposés en quadrillage, personne ne connaît actuellement les meilleurs réseaux possibles.

Entrée 3 - Le problème a été peu étudié dans l'espace : cas des tétraèdres, des pyramides, du cube...? Commentaire Entrée 4 - On peut se demander si la (ou les) solution(s) est (sont) constructible(s) à la règles et au compas.

A quoi cela sert-il ?

Ce type de problème est courant en Recherche Opérationnelle (étude des réseaux de communications et de transports, planification et optimisation de production). La question "de l'arbre minimum" relève de ce qui est appelé la théorie des graphes (un graphe est un système de chemins entre différents points) ; elle apparaît par exemple si on souhaite réaliser à moindre coût des itinéraires de livraison ou de communication entre des sites donnés en utilisant des routes déjà existantes.

Documentation sur ce sujet

échos de la recherche sur ce sujet