The Distributing Of Terminals And The Property Of Steiner Vertices On The Steiner Tree Problem

Steiner tree problem, being a historic mathematical pullze, can be widly applied in many aspects such as network design, VLSI design and so on. This paper studies some problems on it in the the plane and in the weighted graph.Firstly, the case in the plane is discussed. By G-P conjecture we can see that the Steiner ratio is3^1/2/2, which is achievable. This paper proposes the concept of the max-min ratio of terminals, which is taken as the parameter to describe the uniformity of the distributing of terminals, then discusses theSteiner ratio in the given distributing of terminals, which can be greater than 3^1/2 / 2 ,and so it is an amelioration in some specific instance.The paper then discusses the case in the weighted graph. In the Steiner tree problem, all the targets are vertices (i.e. terminals). But in praxis, an edge even a subgraph can be a target. So it aims to find the minimum connected subgraph including the given subgraph. This problem is proved to be NP-complete, and essentially equal to the Steiner tree problem in the graph.At last, it is studied that how to bound the degree of a Steiner vertex and the number of total Steiner vertices, which can make it easier to find a Steiner in some given graph. Firstly discusses the case that the induced subgraph of the terminals is connected, then give the two above-mentioned achievable boundaries respectively. So with these results and those in chapter 3,we give the upper boundary of the number of total Steiner vertices in the case that the induced subgraph of the terminals is not connected.