O estudo das árvores de Steiner no Plano Euclidiano e algumas aplicações através do Algoritmo de Melzak

Abstract

Given a set of points on the plane, we call terminals or regular points, it proves that there is always a minimum tree that connects called "Steiner tree". The terminals may represent hubs to routes, circuit elements, or different networks. That is, the problem in question is to optimize to communication between terminals, if this is represented by a tree of shortest length possible. Not always the "shorter"is optimization. Steiner problem has variations, for example, the tree can only follow the edges of the horizontal and vertical directions, as in the case of electrical circuits. Another variation is when each Steiner point is very expensive, and it is intended to obtain such a tree with the lowest number of such points. It will be "local minimum"for length, but not necessarily globally. A physical and quite simple model for "Steiner tree"is that it can also be performed by soap films, and therefore share minimum surface properties. As an example, consider a soap solution. Getting closer and withdraw two parallel plates connected by pins, a film will connect them. This represents a minimum length graph that interconnects the pins. As is known, the soap films perform the Minimal Surfaces. To view a "Steiner tree"refers to Numerical Algorithms and Graphical Programming, methods are mainly based on the implementation of the algorithms. This present work is divided into three parts: a brief history of optimization problems, highlighted the Steiner problem; theory of the Minimum Tre or Steiner tree and algorithm Melzak; some examples of real cases.