欧几里德距离下的最短2-连通Steiner网络

论文摘要

设P是一个有限点集,N=（V,E）是一个顶点集为V,边集为E的网络。如果V（?）P,则称N为P的Steiner网络。特别地,如果V=P,则称N为P的生成网络。称P中的点为正则点,称VP中的点为Steiner点。网络N的长度定义为它的各条边的长度的和。欧几里德2-连通Steiner网络问题可以描述为:给定欧几里德平面上的一个有限点集P,确定P的最短2-连通Steiner网络。这里,任意两点之间的长度定义为它们之间的欧几里德距离,该网络允许添加欧几里德平面上给定点集以外的点。该问题在构造可靠经济的通讯网络方面有重要的应用价值。 Luebke和Provan证明了欧几里德2-连通Steiner网络问题是NP-困难的。这意味着对一般的平面有限点集而言,不大可能存在求解这个问题的多项式时间算法。1998年,Hsu和Hu引入基本2-连通Steiner网络的概念,给出了（基本）最短2-连通Steiner网络的一些结构性质和两种特殊的多项式可解情形。李美丽在她的硕士论文中,以块图为工具,给出了（基本）最短2-连通Steiner网络的进一步的一些性质,对Hsu和Hu的一个已有结论进行了清楚的证明。本论文对该问题进行进一步的研究。 论文第一章介绍了论文中涉及的一些基本概念和术语,欧几里德2-连通Steiner网络问题的研究现状以及论文中所得到的主要结果。 利用Monma等人给出的2-连通网络的一个性质,在论文的第二章中,我们给出了（基本）最短2-连通Steiner（或生成）网络的一些新的结构性质,对李美丽给出的（基本）最短2-连通Steiner网络的三个性质给出了新的、简单的证明。 第三章主要讨论了一类特殊点集|P|=6或7时的最短2-连通Steiner网络与其最短2-连通生成网络和最短Hamilton圈之间的关系。 欧几里德2-连通Steiner网络问题是度量空间上的2-连通Steiner网络问题的特殊情况。第四章将关于最短2-连通Steiner网络的几个结论推广到一般的度量空间上。 在第五章中,我们给出了广义欧几里德steiner问题的描述,提出了该问题的进一步研究的一些问题。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• §1.1 引言
• §1.2 基本概念与术语
• §1.3 欧几里德2-连通Steiner网络问题的研究现状
• §1.4 本论文的主要结果
• 第二章 最短2-连通Steiner网络
• §2.1 引言
• §2.2 最短2-连通Steiner网络的结构性质
• §2.3 基本最短2-连通Steiner网络的两个相关结果
• 第三章 |P|=6或7时的最短2-连通Steiner网络
• §3.1 引言
• §3.2 几类特殊点集的最短2-连通Steiner网络
• §3.3 |P|=6或7时的最短2-连通Steiner网络的性质
• 第四章 度量空间上的2-连通Steiner网络问题
• §4.1 引言
• §4.2 SMN的结构性质
• 第五章 进一步研究的一些问题
• §5.1 广义欧几里德Steiner问题
• §5.2 进一步研究的一些问题
• 参考文献
• 致谢
• 附录一 作者攻读硕士学位期间参加的科研项目
• 附录二 作者攻读硕士学位期间完成和发表的论文