Some Results On The Constraints Of The Optimal Tree

The problem on the shortest connection in the plane is used widely, such as the transportations, the construction of road system, the design of VLSI, etc. What we consider on the problem is that there are given n vertices and a line, where the distance is Euclidean distance, the vertices and some edges constructing a spanning tree of a graph. Furthermore, we consider the spanning tree is related to the line. Then we called it the restricted spanning tree problem.The thesis focuses on some models about constrained optimal tree on a plane and their problems .There are n points out of the line L. We can make the total length of connection shortest by leading any lines which connect with n points to become a net from the line L. This is a new model bring forward. We can make the further discussion about the model that leads a point from line L, and present the related conditions and several results. In the second chapter, it introduces the constrained optimal tree A and presents the solution of this problem by exchanging a geometry model to a graph theory model, exchanging a connection problem to the minimum spanning tree problem. In the third chapter, it introduces the constrained optimal tree problem leading lines from a point of line L. It discusses when to connect with one line, two lines and three lines, and presents the solutions of combinatorial algorithms whichconnect with one line and two lines. It also presents several necessary conditions connecting with three lines and gives how to find the approximate solution on the basis of supposed connection with three lines. In the forth chapter, it introduces constrained Steiner tree and presents the further research.Main results: Theorem 2.1 Problem A is equivalent Problem B.We construct a complete graph G(V,E),V = {P0,P1,P2, ..., Pn) , Theorem 3.1 If a line is led from the line L, the constrained optimal tree T* satisfies,Theorem 3.2 If two lines are led from the line L, the constrained optimal tree T* satisfies,Theorem 3.3 If two lines are led from the line L, the constrained optimal tree T* satisfies,...