欧几里德2-连通Steiner网络问题研究

摘要

论文的第一章介绍了关于欧几里德2-连通Steiner网络问题的一些基本概念和最新研究进展,并且介绍了该论文的主要创新之处.在第二章中,我们首先给出了2-连通网络的一个性质.在此性质的基础上,我们以块图为工具,得到了最短2-连通Steiner网络的四个性质.Hsu和Hu在文献[16]中引入了基本最短2-连通Steiner网络的概念,并且给出了它的几个性质.在第三章中,我们对基本最短2-连通Steiner网络进行了进一步的研究,首先得到了基本最短2-连通Steiner网络的两个新的性质,然后给出了基本最短2-连通Steiner网络的两个充分条件.在第四章中,我们利用前面两章中所得到的结论,对Hsu和Hu在[16]中得到的三个定理给出了新的,简单而且清楚的证明.在[16]中,Hsu和Hu还给出了一个例子,用来说明当|P|=8时,P的最短2-连通Steiner网络不一定是P的最短2-连通生成网络.我们构造了求给定点集P的最短2-连通生成网络的整数规划模型,并利用Lingo软件,对Hsu和Hu的例子进行了计算,最后发现他们的例子是错误的.在第五章中,我们对欧几里德2-连通Steiner网络问题,广义欧几里德Steiner问题和其他广义Steiner问题提出了一些可以进一步研究的问题.

目录

文摘

英文文摘

第一章绪论

§1.1引言

§1.2基本概念与术语

§1.3 2-连通Steiner网络问题的研究现状

§1.4本文的主要结果

第二章最短2-连通Steiner网络的几个性质

§2.1引言

§2.2 2-连通网络的一个性质

§2.3最短2-连通Steiner网络的几个性质

第三章基本最短2-连通Steiner网络

§3.1引言

§3.2基本最短2-连通Steiner网络的一些性质

§3.3基本最短2-连通Steiner网络的几个充分条件

第四章几个已知定理的新证明和一个错误结论的改正

§4.1引言

§4.2定理4.1和4.2的证明

§4.3定理4.3的证明

§4.4结论4.1的改正

第五章进一步研究的一些问题

§5.1 2-连通Steiner网络问题中的一些研究问题

§5.2广义欧几里德Steiner问题

§5.3其他广义Steiner问题

参考文献

致谢

附录作者攻读硕士学位期间参加的科研项目

西北工业大学学位论文知识产权声明书及西北工业大学学位论文原创性声明