Présentation:
| Un arbre de
Steiner est un graphe qui
recouvre un ensemble donné de points de l'espace métrique tel que la
distance totale sur ses bords soit minimale. En
théorie: Soit
G = (V,E,d) un graphe symétrique dans un espace métrique où V est un
ensemble de points de G, E est un ensemble d'arêtes de G et d une
distance métrique. Soit
S un sous-ensemble de V. Soit
D(g) = somme d(ei) où g est un graphe possédant un nombre ei d'arêtes. Soit
X un ensemble d'arbres de G étendu sur S. La
construction d'un arbre de Steiner T répond à la définition suivante: T
= (V',E', d) élément de X tel que D(T) = inf{ D(x) : x élément of X} Histoire Au
cours du 17ième siècle, le mathématicien français Pierre de Fermat
chercha comment on pouvait 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. Ce problème fut résolu plus tard par Torricelli. Le
problème de Steiner est la généralisation de cette question permettant
d'ajouter pour un nombre arbitraire d'arêtes et de points. Ce problème a
trouvé de multiples applications dans
un panel de disciplines très étendu. Malheureusement, il a été démontré
que ce problème fait partie de la classe des problèmes NP-complets. De
par l'importance de ses travaux qui constituent des défis mathématiques,
Jacob Steiner contribua à la recherche de solutions à ce problème. Bien
que ce problème soit de classe NP-complet, Il existe des algorithmes
heuristiques qui ont été conçus pour approcher la solution exacte dans
un temps polynomial. |
A Steiner tree is a tree in a distance
graph which spans a given subset of vertices (Steiner points) with the
minimal total distance on its edges. Formally: Let G = (V,E,d) be an undirected graph in
metric space where V is the set of vertices in G, E is the set of edges in
G and d is the metric distance method. Let S be a subset of V. Let D(g) = sum d(ei) where g is a graph with
indexed edges ei. Let X be the set of trees in G which span S. Find T = (V',E',d) element of X such that D(T)
= inf{ D(x) : x element of X}
History In the 17th century, the ubiquitous French
mathematician Pierre Fermat asked how we could find a point P in a
triangle with the distances from P to the vertices being as small as
possible. This problem was later solved by Torricelli. The Steiner Problem is a generalisation of
this question allowing for an arbitrary number of initial vertices and an
arbitrary number of vertices to be added. This problem has found uses
across a wide array of disciplins. Unfortunately, it has been shown to be
NP-complete. Though the importance of his contributions to
mathematics goes unchalanged, it is unclear what Jacob Steiner contributed
to this problem.
An
algorithm. Though this problem is NP-complete, certain
heuristic algorithms have been designed to approximate the result within
polynomial time. This is such an algorithm taken from Kou et al.
|
Pour télécharger le document pdf qui présente les bases topologiques du problème de Steiner, cliquer ici. (format zip)
|
|
|
