我已将问题简化为在图中找到最小生成树。但我想再有一个约束，即每个顶点的总度数不应超过某个常数因子。如何建模我的问题？MST是错误的路径吗？你知道任何可以帮助我的算法吗？
还有一个问题：我的图有重复的边权重，所以有没有办法计算唯一 MST 的数量？有没有算法可以做到这一点？
谢谢你。
编辑：按度数，我的意思是连接顶点的边的总数。重复边权重是指两条边具有相同的权重。
问问题
1158 次
3 回答
2
好吧，很容易证明可能没有解决方案：只需使您的输入图成为一棵树，其顶点的度数高于您的限制..
于 2009-05-20T22:43:42.827 回答
2
加里约翰逊把这个问题简化为汉密尔顿:(所以这个有帮助。近似第一个：http ://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt 但是，更好工作模型受到赞赏...
计数： http: //mathworld.wolfram.com/SpanningTree.html。据此，mathematica 有一个功能。这个有什么建议吗？
于 2009-05-21T14:55:02.097 回答
1
本文展示了如何在多项式时间内找到最大度数为 d + 1 的生成树，该生成树至少与任何最大度数为 d 的生成树一样好：http ://www.andrew.cmu.edu/user/mohits /mbdst.pdf
//Edit 原始链接当前处于非活动状态，请尝试http://research.microsoft.com/pubs/80193/mbdst.pdf。
于 2009-06-09T04:33:03.353 回答