|
NOMBRES - Curiosités, théorie et usages Accueil / Dictionnaire / Rubriques / Index / Références / Nouveautés ORIENTATION GÉNÉRALE - M'écrire - Édition du: 01/03/2009 |
|
- Ý - GRAPHES Arbre de Distribution |
|
|
Sommaire de cette page >>> ARBRE DE DISTRIBUTION ou de Steiner |
Pages voisines § Triangle |
-Ý- 13,4 Géométrie ARBRE DE DISTRIBUTION
Rapport de Steiner
|
1-Ö 3/2 = 0, 133974596 … |
La conjecture de Steiner est la suivante:
|
Entre un arbre de distribution directe et l'arbre
optimisé, le maximum de gain en longueur est 13,4% § Compte tenu de la difficulté pour trouver l'optimum
en longueur de ce réseau § et du faible gain attendu, § les constructeurs de réseaux se contentent de l'arbre direct ou optimisé localement: |
|
|
· La conjecture du rapport de Steiner est importante pour l'économie de tout réseau. |
Cas du triangle équilatéral:
|
·
Une ville à
chaque sommet: quel est le réseau le plus court? ·
L'arbre AB, AC
(BC n'est pas nécessaire) mesure 2 unités de longueur. ·
L'arbre AO, OC,
OB qui nécessite l'introduction d'un point supplémentaire, mesure seulement Ö 3 = 1,73 unités. § Le rapport est: Ö 3/2 = 0,866 § Et le gain: 1-0,866 = 0,134 § Il vaut mieux utiliser le réseau central. |
Construction du point de Steiner pour un triangle
quelconque:
|
Pour le triangle ABC: dessinez le triangle équilatéral ACX et son cercle
circonscrit. Le point S est le point de Steiner. |
Voir Point de Torricelli et point de Fermat
Cas de 6 villes dans 2 carrés adjacents:
|
Déjà à ce stade, l'optimisation n'est pas évidente! |
La méthode de l'algorithme glouton:
|
§ Elle permet de tracer un réseau optimum direct,
c'est-à-dire sans point intermédiaire.
§ On relie les villes deux à deux par ordre de distances croissantes sans faire de boucles. |
Approche par les treillis triangulaires:
|
§ Résoudre le cas général est un problème géométrique
" difficile " § C'est-à-dire: l'exploration de la combinatoire est
longue et non généralisable. § Mais, on a montré (Ding Zhu Du et Frank Hwang) que, § si les villes sont aux sommets d'un treillis de
triangles rectangles, § seuls les points de Steiner de ces triangles § seront impliqués dans l'optimisation du réseau. § Ce qui réduit considérablement l'analyse.
|
|
Voir |