坚持解决最小生成树问题

题

我已将问题简化为在图中找到最小生成树。但我想要还有一个限制，那就是 每个顶点的总度数不应超过某个常数因子. 。如何为我的问题建模？MST路径是否错误？你知道有什么算法可以帮助我吗？

还有一个问题：我的图有重复的边权重，那么有没有办法计算唯一 MST 的数量？有算法可以做到这一点吗？

谢谢。

编辑：我所说的度数是指连接顶点的边的总数。重复边权重是指两条边具有相同的权重。

解决方案

本文展示了如何在多项式时间内找到最大度为 d + 1 的生成树，该生成树至少与任何最大度 d 的生成树： http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

//编辑原链接当前无效，尝试一下 http://research.microsoft.com/pubs/80193/mbdst.pdf 反而。

其他提示

好，很容易证明，有可能不是一个解决方案：只要让你的输入图形，拥有比你的极限更高程度的顶点树..

加里·约翰逊（Garey Johnson）将这个问题简化为汉密尔顿:(所以这个有帮助。近似第一个： http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt然而，更好的工作模型值得赞赏......

数数： http://mathworld.wolfram.com/SpanningTree.html 。据此，mathematica 有一个函数。这方面有什么建议吗？

许可以下： CC-BY-SA 和归因