我已经减少了我在图中找到最小生成树的问题 . 但我希望还有一个约束条件，即每个顶点的总度数不应超过某个常数因子 . 我如何模拟我的问题？ MST是错误的道路吗？你知道任何能帮助我的算法吗？
还有一个问题：我的图表有重复的边缘权重，那么有没有办法计算唯一的MST数量？有算法可以做到这一点吗？
谢谢 .
编辑：按度数，我的意思是连接顶点的边的总数 . 重复边缘重量是指两个边缘具有相同的重量 .
好吧，很容易证明可能没有解决方案：只需将输入图形设置为具有度数高于限制的顶点的树 .
Garey Johnson把这个问题减少到了汉密尔顿:(所以这一个帮了 . 接近第一个：http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt然而，更好的工作模型受到赞赏......
计数：http://mathworld.wolfram.com/SpanningTree.html . 据此，mathematica具有功能 . 这一个有什么建议吗？
本文展示了如何在多项式时间内找到最大度d 1的生成树，该生成树至少与最大度数d的任何生成树一样好：http://www.andrew.cmu.edu/user/mohits/mbdst.pdf
//编辑原始链接当前处于非活动状态，请尝试使用http://research.microsoft.com/pubs/80193/mbdst.pdf .
3 回答
好吧，很容易证明可能没有解决方案：只需将输入图形设置为具有度数高于限制的顶点的树 .
Garey Johnson把这个问题减少到了汉密尔顿:(所以这一个帮了 . 接近第一个：http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt然而，更好的工作模型受到赞赏......
计数：http://mathworld.wolfram.com/SpanningTree.html . 据此，mathematica具有功能 . 这一个有什么建议吗？
本文展示了如何在多项式时间内找到最大度d 1的生成树，该生成树至少与最大度数d的任何生成树一样好：http://www.andrew.cmu.edu/user/mohits/mbdst.pdf
//编辑原始链接当前处于非活动状态，请尝试使用http://research.microsoft.com/pubs/80193/mbdst.pdf .