论文部分内容阅读
最小支撑树问题是一类经典的组合最优化问题，它已经有很好的解决方法．本文重点研究在支撑树上加点的相关最优化问题，这是对最小支撑树问题的推广．本论文详细讨论了这类在树上加点的相关最优化问题．给定一个连通图G=(V，E；w)和两个正整数d，B，这里边赋权函数为w：E→Z<+>，求G的一棵支撑树T，向T的一些特殊边上加入一些新点得到加细树T′，使T′中每一个边的长度不超过常数d，我们考虑以下四种形式的加点优化问题：(1)求一个支撑树T，满足w(T)≤B并且加入的新点数最少；(2)不要w(T)≤B的限制，但考虑加点费用时，目标是求一个支撑树，使树的权重与这个树的加点总费用之和达到最小；(3)在既有w(T)≤B的条件限制，又考虑加点费用时，求这样一个支撑树，使这个树的加点总费用之和达到最小；(4)在既有w(T)≤B的条件限制，又考虑加点费用时，求这样一个支撑树，使树的权重与这个树的加点总费用之和达到最小．我们在论文中得到如下结果(1)我们分别设计了多项式算法来解决前两种加点优化问题，(2)分别证明了后两种加点优化问题是N P-难的．(3)设计了多项式算法来解决后两种加点优化问题的特殊情形．
本文有以下四章构成：
第一章：回顾了问题的由来，理论的形成，给出了到目前为止的一些研究成果。
第二章：给出了文中所出现的定义、概念和符号．
第三章：讨论支撑树上加点的相关最优化问题．
第四章：给出了相关结论以及未来的研究方向．