NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 06/03/2024 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Topologie
Débutants Général	GRAPHES				Glossaire Topologie
INDEX Arbre Graphe Topologie Dénombrement Logique Jeux et énigmes	Ivrogne		Chemin le plus court	Arbre de distribution
	Trois maisons		Chemin eulérien	Voyageur de commerce
	Cinq pays		Graphe planaire	Petit monde
		Sommaire de cette page >>> ARBRE DE DISTRIBUTION ou de Steiner >>> Cas du triangle équilatéral >>> Cas du triangle quelconque >>> Cas de six villes >>> La méthode de l'algorithme glouton >>> Approche par les treillis triangulaires

Faites un double-clic pour un retour en haut de page

ARBRE DE DISTRIBUTION

Problème de l'arbre de Steiner

Problème d'optimisation combinatoire.
Comment connaitre et construire un réseau ou un arbre de longueur minimale ?

Applications: conception de réseaux, circuits électroniques, réseaux routiers, arbres phylogénétiques.

Ce problème est proche du problème de l'arbre couvrant minimal. Il est difficile de donner une solution exacte du problème de Steiner car il est NP-complet. Toutefois, il existe des algorithmes approximatifs très performants.

Anglais: Steiner tree problem, minimum Steiner tree problem

Historique

Les origines du problème de Steiner remontent au XVIIème siècle. Le mathématicien français Pierre de Fermat se demanda comment trouver un point P dans un triangle de manière à ce que la longueur totale des arêtes concourantes au point P soit la plus petite possible.

Le problème de Steiner, nommé en référence à Jakob Steiner (1796-1863, mathématicien suisse), est la généralisation de cette question. Étant donné un ensemble S de points, il s’agit de trouver l’arbre reliant tous les sommets de S tel que sa longueur soit minimale.

ARBRE DE DISTRIBUTION
Conjecture de Steiner Entre un arbre de distribution directe et l'arbre optimisé, le maximum de gain en longueur est 13,4%.	Rapport de Steiner = 0, 133 974 596 …
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.	cas de la distribution d'électricité, des lignes de bus, des conduites de gaz, du réseau câblé de TV, du routage des circuits imprimés... et même du code génétique du génome d'ADN, etc.

Voir Arbres en général – Introduction, types / Problème d'optimisation d'un réseau (de la voierie entre maisons)

Cas du triangle équilatéral
Une ville à chaque sommet du triangle équilatéral: quel est le réseau le plus court pour relier les trois villes? Le réseau ABC relie les trois villes et mesure 2c. Il n'est pas optimum. Le réseau OA, OC et OB, qui nécessite l'introduction du centre de gravité, mesure seulement = 1,732…c. Le réseau central est donc bénéfique de plus de 13%.

Cas du triangle quelconque – Point de Steiner
Pour le triangle quelconque ABC: dessinez le triangle équilatéral ACM et son cercle circonscrit. Le point S est le point de Steiner.

Voir Point de Torricelli et point de Fermat 

Cas de six villes en carrés
Les six villes sont disposées sur deux carrés adjacents. Optimisation pas évidente!

La méthode de l'algorithme glouton
Cette méthode permet de tracer un réseau optimum direct, c'est-à-dire sans point intermédiaire.  Les distances entre villes sont triées de la plus petites à la plus grande. Les chemins sont dessinés dans l'ordre: de la plus courte distance à la plus grande.

Voir Algorithme / Algorithme glouton pour la coloration de graphes

Approche par les treillis triangulaires
Résoudre le cas général est un problème géométrique difficile, car 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.

Suite	Trois maisons Autres sur ce thème Points, Cercle et triangle de Steiner Graphe – Index
Voir	Code Gray Croissance logistique Diagramme de Venn Dominos et graphe Échiquier et graphe Énigmes et paradoxes Intelligence artificielle	Jeux – Index Logique formelle Médaille Fields: Wendelin Werner Raisonnement Topologie – Glossaire Tour de Brahmâ Transformation du boulanger
Sites	Problème de l'arbre de Steiner – Wikipédia Le problème de Steiner – Élisabeth Abbas et Hassia Tamimou – pdf – 2014
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Logique/TreizArb.htm

Pour mémoire: copie de la page datant de la fin des années 1980 lorsque ce site n'existait que sous forme de document papier

Première mise en ligne Internet en 1998