论文部分内容阅读
网络构建问题是组合优化问题中的一类经典问题，而连通性则是网络设计问题中的一个重要问题。本文研究的重点是无向连通网络的构建问题及有向强连通网络的构建问题。因在无向图G中，图G是连通图的充分而且必要条件是图G有支撑树，所以研究无向连通网络的构建问题等同于研究无向图中支撑树的构建问题。在支撑树及强连通支撑子图问题的基础上，结合经典的一维装箱问题提出了如下所述的两个组合优化问题:
(1)给定一个无向图G=（V, E;ω），长度函数ω:E→R+及一种长度为L的材料，在这里，允许边e的长度ω(e)＞L，要寻找图G的一棵支撑树T，并用所给材料连接T中的所有边，使得所用材料根数达到最小。
(2)给定一个有向图D=（V, A;ω），长度函数ω:A→ R+及一种长度为L的材料，这里，允许弧e的长度ω(e)＞L，要寻找图D一个强连通支撑子图D，并用所给材料连接D中的所有弧，使得所用材料根数达到最小。
以上两个问题均是装箱问题的推广，因此都是NP-完备的，所以它不存在求解这两个问题的多项式时间算法，除非P=NP。本文对上述两个问题分别设计了2-近似算法、3/2-近似算法和4-近似算法、渐近7/2-近似算法，且给出了详细的证明过程及程序设计。
论文由以下五章构成:
在第一章中，介绍问题，给出了到目前为止的一些研究成果。
在第二章中，介绍了本文所涉及到的有关图论、组合最优化及近似算法的基本定义及符号。
在第三章中，给出一些基本问题及求解算法。
在第四章中，研究无向连通网络的构建问题。
在第五章中，研究有向强连通网络的构建问题。