论文部分内容阅读
在已知边带权的连通图中找一棵边权总和最小的生成树的问题很早就被提出和研究[15，14】，并且也得到了广泛的应用【15，14，23】。但是在日常生活中也会遇到这样一类类似的问题，抽象出来就是在一个结点和边都有权重的连通图中找一棵生成树，使得生成树的内点(非叶子结点)的权值和边的权值总和最小，称之为内点带权的最小生成树。此前并没有文献提到并研究过此问题。本文首次提出了内点带权的最小生成树问题，并对此问题进行了深入的分析和研究。主要有如下结论：
1．首先对此问题进行了计算复杂性分析。证明了内点带权最小生成树问题是NP-hard的；而且在Metric隋况下，即若图的边权之间满足三角不等式时，内点带权的最小生成树问题仍然是NP-hard的。它们对应的判定问题也都是NPC的。
2．在Metric隋况，即图的边权满足三角不等式时，本文给出了两个近似度分别为3．52和3．106的多项式时间近似算法。同时分析了其不可近似性：此问题在Metric情况下不可能有近似度小于1．463的多项式时间近似算法除非NP∩-DTIME[7／O(1oglogn]。
3．在一般情况下，即图中的边权不一定满足三角不等式，本文给出了两个近似度分别为2.35.1ogn和2．(Hn-1)的多项式时间近似算法，这里Hn是调和数(Harmonicnumber)，即：Hn=l+1/2+…+1/n，这里的n是原图中结点的个数。同时证明了其不可近似性：对任意的E>0，此问题不可能有近似度小于(1一E)．Hn，的多项式时间近似算法除非NP∩-DTIME[nO(10glogn)1。
4．本文最后给出了一个近似度为△一1的相对比较简单的多项式时间近似算法，这里△是原图的度，即图中结点的最大度数。不难看出，当原图的度数比较小时，此算法非常有效。
综上，本文证明了内点带权的最小生成树的计算困难性，并且就不同的情况分别设计了相应的近似算法以及分析了其不可近似性。由于计算内点带权的最小生成树问题在实际中应用比较广泛，因此，本文的思想和方法对以后这方面的工作不但具有重要的理论价值，而且在实际中也有重要的应用价值和指导意义。