广义欧几里德Steiner问题的研究与进展  

Development of the Generalized Euclidean Steiner Problem

作　　者：张胜贵[1] 彭书英[2] 李美丽[3] 乔胜宁[1] 

机构地区：[1]西北工业大学应用数学系,西安710072 [2]天津工业大学理学院,天津300160 [3]西安石油大学数学系,西安710065

出　　处：《工程数学学报》2005年第4期571-578,共8页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(10101021).

摘　　要：广义欧几里德Steiner问题是指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了此问题的研究与进展,在建立了求给定平面点集的最短U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。The generalized Euclidean Steiner problem is to find the shortest network satisfying specified connectivity requirements, which connects a set of given points in the Euclidean plane. A survey up to now on this problem is given. A general 0\1 integer linear programming model is presented for finding the shortest U-connected (or edge-connected) spanning network for a set of given points in the plane, by which we show that the counter example in a paper of Hsu and Hu is false. Some problems for further research about Steiner problem are also proposed.

关 键 词：Steiner问题 (广义)欧几里德Steiner问题 k-Steiner比率 

分 类 号：O157.5[理学—数学]