Euclidean 2 - Connected Steiner Network Problems,

The Euclidean 2-connected Steiner network problem is to determine the minimum-weight 2-connected Steiner network on a given set of points in the Euclidean plane. This problem has vide applications in real areas, such as the design of water and electricity supply networks, and communication networks, etc. At the same time, the problem is also closely related with some classical combinatorial optimization problems, including the Steiner problem and the travelling salesman problem, which are well-known. So, it is of great importance to study it. In this thesis, we give a deep research on this problem in several aspects.In Chapter 1, after an introduction on the terminology and notations, we provide a survey on the Euclidean 2-connected Steiner network problem and a general introduction of the main results of the thesis.In Chapter 2, we first give a property for 2-connected networks. Then, with this property and the concept of block graph, we obtain four properties of shortest 2-connected Steiner networks.In Chapter 3, we are mainly concerned with the so-called basic shortest 2-connected Steiner networks, which was introduced by Hsu and Hu [16]. We give two new properties of basic shortest 2-connected Steiner networks and two sufficient conditions for shortest 2-connected Steiner networks to be basic.In Chapter 4, we give new proofs of three theorems of Hsu and Hu [16]. The proofs are much clearer than the original ones. At the same time, we show that one example of Hsu and Hu [16] is false. The example was used to show that when |P| = 8, the shortest 2-connected Steiner network on P is not always the shortest 2-connected spanning network.We conclude the thesis with Chapter 5 by proposing some problems for further research on the Euclidean 2-connected Steiner network problem and also other generalized Steiner problems.