NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 06/03/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Topologie

 

Débutants

Général

GRAPHES

 

Glossaire

Topologie

 

 

INDEX

 

Logique

 

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

 

 

 

 

 

 

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.

 

 Jacob Steiner (1796-1863) – Mathématicien suisse

 

 

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

Voir

*         Code Gray

*         Croissance logistique

*         Diagramme de Venn

*         Dominos et graphe

*         Échiquier et graphe

*         Énigmes et paradoxes

*         Intelligence artificielle

*         JeuxIndex

*         Logique formelle

*         Médaille Fields: Wendelin Werner

*         Raisonnement

*         TopologieGlossaire

*         Tour de Brahmâ

*         Transformation du boulanger

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