|
|
Ce site est désormais accessible en http://diconombre.fr/index.html et pour
cette page voir le lien en fin de page For this page,
refer to the link at the bottom. |
|
22 Novembre 2025
|
Édition du: 14/04/2026 |
|
INDEX |
GRAPHES |
||
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
villes 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 >>> Trois villes –
Arbre couvrant et arbre de Steiner >>>
Quatre villes – Diverses possibilités >>>
Points de Steiner >>>
Voirie minimale pour cinq villes >>>
Arbre de Steiner d'ordre 6 >>>
English Corner |
Débutants Glossaire |
Anglais: Connect the towns, the motorway problem (Isenberg 1975)
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 (ici 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 du triangle et S = √3. |
|
|
|
Gain de longueur Le gain de longueur
entre un arbre de Steiner et un arbre couvrant d'ordre 3 est : |
|
|
|
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
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 (ici AC et CB). C'est l'arbre couvrant
qui minimise la longueur totale du graphe (D = 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, dit point de Steiner, se trouve au centre du triangle et L = √3. 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 (D = 3). 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. Notez que les
angles autour du point de Steiner valent tous 120°. |
|
|
|
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… Valeur trouvée en 1978:
|
|
|
Voirie minimale
pour cinq villes Arbre
de Steiner d'ordre 5 |
|||||||
|
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
|
Deux arbres couvrants et l'arbre
de Steiner minimal. Quatre points intermédiaires. Il est unique. |
|||
|
|
|
|
|
|
L = 6√3 Trajet le plus long: 3 |
L = 6√3 Trajet le plus long: 2 |
L = 6 Trajet le plus long: 4 |
|
Une des topologies pour arbre de Steiner d'ordre 7
Mais
l'heptagone n'est pas régulier
|
The motorway problem is an interesting one in optimisation. 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. |
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
