|
Édition du: 15/02/2026 |
|
INDEX |
GRAPHES |
||
|
Minimiser la voirie (Steiner) |
|||
Faites
un double-clic pour un retour en haut de
page
|
Minimiser la voirie (le réseau) Arbres de Steiner Étant donné n villes (ou maisons), il s'agit de trouver le réseau de
voirie qui comptera le minimum de kilomètres.
Toutes les villes doivent être desservies même si le chemin doit passer par
d'autres points intermédiaires. Deux types de solutions:
Les solutions avec croisements sont les plus performantes. S'il est
facile de trouver les solutions pour trois, quatre ou cinq villes, le
problème devient vite incroyablement difficile à résoudre (NP-Complet). Problème d'optimisation d'un réseau selon
le facteur coût. |
||
|
|
Sommaire de cette page >>> Approche >>> L’arbre
couvrant: relier sans inventer >>> L’arbre de
Steiner : optimiser en inventant >>> Cas des
polygones réguliers >>> Bilan Revue de détail >>> Trois villes –
Arbre couvrant et arbre de Steiner >>>
Quatre villes – Diverses possibilités >>>
Points de Steiner >>>
Voirie minimale pour cinq villes >>>
Arbre minimal pour l'hexagone >>>
Cas de l'heptagone >>>
English Corner |
Débutants Glossaire |
Anglais: Connect the
towns, the motorway problem (Isenberg
1975)
|
Relier le monde : des arbres
couvrants aux arbres de Steiner Dans bien des
situations de la vie réelle, relier plusieurs points n’est pas seulement une
question de géométrie
: c’est une affaire de coût, d’efficacité, parfois même de survie. Imaginez un
ingénieur chargé de déployer un réseau électrique dans une région
montagneuse. Les villages sont dispersés, les reliefs compliqués, et chaque
mètre de câble coûte cher. Comment relier tout le monde sans gaspiller de
ressources ? Ou encore un
urbaniste qui doit concevoir un réseau d’eau potable pour un nouveau
quartier. Les habitations sont déjà implantées, mais les jonctions, elles,
restent à inventer. Derrière ces
questions très concrètes se cache une idée mathématique simple et puissante :
comment relier un ensemble de points en minimisant la longueur totale du
réseau ? Deux réponses
existent, deux philosophies presque opposées, et pourtant complémentaires : l’arbre couvrant minimal et l’arbre de Steiner minimal. |
|
|
|
Cette première
approche est la plus intuitive. On dispose d’un
ensemble de points — des villes, des capteurs, des stations — et l’on
souhaite les relier sans ajouter de nouveaux lieux de jonction. On ne peut
utiliser que ce qui existe déjà. Le résultat
s’appelle l’arbre couvrant minimal, ou MST
(Minimum Spanning Tree). C’est un réseau qui :
Dans un paysage
réel, cela revient à dire : « Je relie
les villages entre eux en choisissant les routes les plus courtes possibles,
mais je n’ai pas le droit de construire de nouveaux carrefours. » Cette contrainte
peut sembler restrictive, mais elle a un avantage immense : le MST se calcule
rapidement, même pour des milliers de
points. C’est pourquoi il est omniprésent dans les algorithmes
modernes, du routage Internet à la conception de réseaux de transport. |
Graphe de base avec coûts par segment
Sélection de l'arbre couvrant
minimal
|
|
Voir Nomenclature des problèmes de réseaux et chemins
|
Mais parfois, la
réalité offre plus de liberté. Dans un réseau électrique, rien n’empêche
d’installer un transformateur supplémentaire. Dans un réseau d’irrigation, on
peut creuser un puits intermédiaire. Dès lors, une
nouvelle question apparaît : et si l’on autorisait l’ajout de points
intermédiaires pour réduire encore la longueur totale ? C’est le
principe de l’arbre de Steiner minimal, ou SMT (Steiner Minimal Tree). Ici, les
mathématiques deviennent plus subtiles : les points ajoutés — les points de
Steiner — ne sont pas choisis au hasard. Ils apparaissent exactement là où
ils permettent un gain maximal, et les segments qui s’y rencontrent forment
toujours des angles
de 120°. Une signature géométrique élégante, presque organique. Dans la nature,
on retrouve des structures proches dans les réseaux vasculaires, les
ramifications des arbres, ou les systèmes racinaires : la géométrie de
Steiner semble être une stratégie spontanée d’économie de matière. Dans
l’industrie, les arbres de Steiner apparaissent dans :
|
Arbre de Steiner créé par un film
savonneux autour de cinq points
Propriété Les segments se
rencontrent toujours avec un angle de 120° autour
du point de Steiner. Intérêt Le gain typique est d’environ 13 % par rapport au
MST pour des configurations irrégulières. Mais ce gain a un prix : le problème devient
extrêmement difficile à résoudre dès que le nombre de points augmente. Là où
le MST se calcule en un clin d’œil, le SMT exige souvent des heuristiques,
des approximations, ou des algorithmes spécialisés. |
||
|
Méthodes de résolution des arbres
de Steiner Trouver un arbre de Steiner minimal est un
problème difficile : dès que le nombre de points augmente, le nombre de
configurations possibles explose. Contrairement au MST, qui se calcule en temps
polynomial, le problème de Steiner est NP‑difficile. On utilise donc plusieurs familles d’algorithmes
selon la taille et la précision recherchée. |
Résoudre un arbre de Steiner : le procédé général
Trouver un arbre de Steiner consiste
à construire un réseau aussi court que possible en reliant un ensemble de
points, tout en ayant le droit d’ajouter des jonctions intermédiaires. Le
procédé suit toujours la même logique, quelle que soit la méthode utilisée. On commence par relier les points existants de la
manière la plus simple possible, souvent en construisant un réseau sans
cycles. Ce réseau sert de point de départ. Ensuite, on cherche à repérer les zones où l’on pourrait
raccourcir le réseau en ajoutant un point intermédiaire. On teste
alors différentes positions possibles pour ces points, en vérifiant si
l’ajout permet de réduire la longueur totale. Chaque fois qu’un point intermédiaire
est ajouté, on réorganise localement
le réseau pour que les segments se rencontrent selon des angles
proches de 120°, ce qui est la configuration la plus efficace. On compare
ensuite la longueur obtenue avec celle du réseau précédent. Si le réseau est
plus court, on le conserve ; sinon, on revient en arrière. Ce processus se répète :
À grande échelle, on explore ainsi de
nombreuses configurations possibles, en éliminant progressivement celles qui
ne peuvent pas être optimales. Le résultat final est un réseau qui relie tous
les points avec une longueur totale aussi faible que possible, même si la
solution exacte n’est pas toujours garantie pour les très grands ensembles. |
||
Jakob Steiner (1796‑1863) était
un mathématicien suisse, célèbre pour ses travaux en géométrie.
|
Quand la symétrie change tout : le cas des polygones réguliers |
|||
|
Les polygones
réguliers sont de bons exemples pour comprendre la différence entre MST et
SMT. On pourrait croire que plus la figure est régulière, plus les points de
Steiner devraient être efficaces. C’est l’inverse qui se produit. Pour 3, 4 ou 5 sommets Les points de
Steiner apportent un gain réel. Les réseaux obtenus sont élégants,
symétriques, et plus courts que le MST. À partir de 6 sommets Un phénomène
surprenant apparaît : le réseau de Steiner optimal n’utilise plus aucun point
de Steiner. Pourquoi ? Ainsi, pour un hexagone, un heptagone, un octogone… MST
= SMT = périmètre moins un côté. Dans
ces cas, les points de Steiner ne servent plus à rien. Si l’on exclut volontairement le
cas du périmètre moins une arête Alors d’autres
réseaux apparaissent : des étoiles centrées, des réseaux en Y, des structures
plus symétriques. Ils sont intéressants d’un point de vue esthétique ou
théorique, mais ils ne sont pas optimaux au sens strict. Ils ne deviennent
pertinents que si l’on impose des contraintes supplémentaires : |
3 – 1,732… Trois sommets Longueur de
l'arbre: 1,732… |
|
|
|
4 – 2,732… |
|
||
|
5 – 3,891… |
|
||
|
6 – 5 |
|
||
|
7 = 6 |
|
||
|
8 = 7 |
|
||
|
Deux philosophies, |
L’arbre couvrant minimal et l’arbre de
Steiner minimal ne s’opposent pas : ils se complètent.
Dans la vie réelle, les ingénieurs
naviguent souvent entre les deux : parfois on ne peut pas ajouter de nœuds,
parfois on le peut. Parfois la géométrie est irrégulière et le
gain de Steiner est précieux, parfois la symétrie rend le MST naturellement
optimal. |
Revue de détail
Arbre couvrant (spanning tree) D'une manière générale, un arbre couvrant d'un
graphe est un arbre inclus dans le graphe qui connecte tous les sommets du
graphe. Avec trois sommets, un arbre couvrant nécessite
deux arêtes (par exemple: AC et CB). C'est l'arbre couvrant qui minimise la longueur
totale du graphe (L = 2). |
|
|
|
Arbre de Steiner (Steiner tree) Il est possible de réduire la longueur totale de l'arbre
en ajoutant des points intermédiaires. Avec trois sommets, un point central (vert)
réduit la longueur du totale du réseau. Avec un triangle
équilatéral, le point optimum se trouve au centre O du triangle et : |
|
|
|
Gain de longueur Le gain de longueur entre un arbre de Steiner et un
arbre couvrant d'ordre 3 est => Avantage supplémentaire: le trajet maximum entre
deux villes passe de 2 = 2√3 / 3 = 1,154 … |
|
|
Voir Cas du triangle équilatéral
|
Relier quatre villes Les quatre villes sont situées aux sommets d'un carré. Elles doivent
être accessibles les unes par les autres. Il existe un chemin qui permet de rejoindre une
ville aux trois autres. Deux questions Quelle est la configuration de la voirie qui
minimise le trajet le plus long parmi tous ? Quelle est la configuration qui minimise la
quantité d'asphalte. Autrement-dit: quelle est la configuration dont la
longueur totale de la voire est la plus courte ? Piste Toutes les villes sont reliées par une route
(configuration du haut):
Les essais suivants réduisent ces valeurs jusqu'à
aboutir aux minimums possibles. Solutions (en
jaune) Les routes limitées aux diagonales offre le plus
petit trajet "le plus long" avec 1, 41 km pour chacun. Pour la voirie minimum, la solution passe par des
routes posées sur deux triangles équilatéraux opposés. La longueur totale des
routes est alors:
2,73 km Il a fallut poser deux points de croisement
intermédiaires. |
|
|
Voir Explications et calculs
/ Énigme du raccordement des cinq
maisons
|
Avec trois sommets Il est possible de réduire la longueur totale de
l'arbre en ajoutant un point intermédiaire, dit point
de Steiner. Avec un triangle
équilatéral, le point optimum se trouve au centre du triangle. Notez que les angles
autour du point de Steiner valent 120°. |
|
|
|
Avec quatre sommets L'arbre couvrant les quatre points, sommets d'un
carré, compte trois arêtes au minimum. Il est possible de réduire la longueur totale du
réseau en introduisant un ou deux points intermédiaires. La longueur est alors diminuée de 6% pour un
point et de 9% pour deux points. Ajouter d'autres points ne réduit pas la
longueur. |
|
|
|
Propriétés Tous les points de Steiner sont entourés de trois
angles de 120° (prouvé). Un arbre de Steiner minimal possède au plus n – 2
points de Steiner. |
Rapport de longueurs entre un arbre
de Steiner minimal et un arbre couvrant minimum: On a longtemps pensé qu'il ne pouvait pas être
inférieur à √3 / 2 = 0,866… Or, valeurs trouvées en 1978:
|
|
Voir Point
de Fermat d'un triangle quelconque et sa construction avec des triangles
équilatéraux
|
Pour cinq villes ou cinq points L'arbre de Steiner minimum pour cinq points
disposés aux sommets d'un pentagone
régulier est montré sur cette figure. Pour sa construction (en suivant la
figure):
|
|
||||||
|
Angles de l'arbre de Steiner 5 Comme tous ces arbres, les points de Steiner sont
entourés d'angles de 120°. L'angle interne du pentagone
vaut 108°. Dans le triangle AGE, l'angle en A vaut: 108 – 90
= 18°. Le troisième angle de ce triangle vaut: 180 – 120
– 18 = 42°. Dimensions de l'arbre de Steiner 5 Toujours dans le triangle AGE, avec la loi des
sinus:
Hauteur
du pentagone:
Hauteur du triangle isocèle GHI: |
Dimensions du réseau d'ordre 5 Ce réseau comporte trois
points de Steiner: G, H et I.
Longueur totale du réseau L = 2(0,772… + 0,365… + 0,577…) L = 3,891… |
||||||
|
Côté du triangle isocèle GHI: Arête DH: Longueur du réseau pour pentagone
régulier unité
Valeur
calculée avec Maple et
vérifiée avec GeoGebra Pour information Valeur des sinus
avec radicaux
|
|||||||
Voir Brève 58-1149
|
Références Graphe (bleu) & Ses dimensions Construction sur un hexagone de côté √3. Ainsi, les arêtes du graphe
valent 1. |
|
||
|
Longueur du graphe |
Trajet le plus long |
Graphe |
|
|
9 |
3 |
|
|
|
6√3 = 10,392… |
3√3 = 5,196… |
|
|
|
5√3 =
8,660… |
5√3 |
|
|
|
6√3 = 10,392… |
4√3 = 6,928… |
|
|
|
9 |
4 |
|
|
Voir Cas de six
villes en carrés
|
Il s'agit bien de l'heptagone
régulier. Notez que le réseau n'est pas symétrique et que le réseau rose (Steiner) est 10% plus long
que le réseau vert de périphérie. |
Une des topologies pour arbre de
Steiner d'ordre 7
|
|
English Corner
|
The motorway
problem is an interesting one in optimization. Suppose that
there are four cities, A, B, C, and D, located at the four corners of a square
with sides of length 1. A network of motorways is to connect all four cities
in the shortest distance possible in order to optimise construction costs. What
configuration of motorways will yield the minimum total distance? Suppose a
finite set of points are randomly scattered about in the plane. How can they
be joined by a network of straight lines with the shortest possible total
length? It is easy
to see that the shortest network must be a tree that is a connected network
containing no cycle. If no new
points can be added to the original set of points, the shortest network
connecting them is called a minimum spanning tree. |
Merci
à Emmanuel Moreau
pour ses précieuses contributions
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
