Árvores de Steiner: Teoria, Geração Numérica e Aplicações / Steiner trees: Theory, Numerical Generation and Applications
AUTOR(ES)
Wendhel Raffa Coimbra
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
16/12/2009
RESUMO
Given a set of points in the plane, which we call terminals, one proves that they are always connected by a minimal graph called Steiner tree. The terminals may represent main connection route points, circuit elements or network computer servers. That is, the problem is to optimize traffic among the terminals whenever this is represented by a tree of shortest length. Not always the shortest length corresponds to an optimisation. The Steiner Problem has variations like moving only in horizontal and vertical directions, as happens to circuits (see [Fo]). Another variation is when each Steiner point has a high cost, so one seeks for such a tree with the smallest number of them. In this case, it will be a local minimum of length, but not necessarily a global minimum (see [Ch]). Steiner trees find application in Computer Networks, in video broadcast and conferences which use multicast communication for data transmission (see [Ji]). We develop this work by means of two main theories: Minimal Surfaces and Approximation Algorithms. Steiner trees may be physically realised through soap films, and these share many properties with Minimal Surfaces. As an example, consider a soap solution with two parallel plates connected by pins embedded therein. After on takes them out, a soap film will connect the pins, and it represents a minimal graph. Soap films realise Minimal Surfaces in practical experiments. In order to visualise the Steiner trees one makes use of Numerics and Graphic Programming. The methods used in this work are essentially based upon the algorithms from [GP] and we chose the software MatLab for this purpose. Most of the work consisted in programming the theoretical results from [GP]. The Steiner tree problem is largely known and a good example of interface between Minimal Surfaces and Numerics.
ASSUNTO(S)
algoritmos numéricos programação gráfica Árvore de steiner numerical algorithms graphical programming steiner tree geometria e topologia
