坚持解决最小生成树问题
我已将问题简化为在图中找到最小生成树。 但我还想要一个约束，即每个顶点的总度数不应超过某个常数因子。 如何为我的问题建模？ MST 路径错误吗？ 你知道有什么算法可以帮助我吗？
还有一个问题：我的图有重复的边权重，那么有没有一种方法可以计算唯一 MST 的数量？ 有算法可以做到这一点吗？
谢谢。
编辑：按度数，我的意思是连接顶点的边总数。 重复边权重是指两条边具有相同的权重。
I have reduced my problem to finding the minimal spanning tree in the graph. But I want to have one more constraint which is that the total degree for each vertex shouldnt exceed a certain constant factor. How do I model my problem? Is MST the wrong path? Do you know any algorithms that will help me?
One more problem: My graph has duplicate edge weights so is there a way to count the number of unique MSTs? Are there algorithms that do this?
Thank You.
Edit: By degree, I mean the total number of edges connecting the vertex. By duplicate edge weight I mean that two edges have the same weight.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
好吧，很容易证明可能没有解决方案：只需将您的输入图设置为一棵树，该树的顶点度数高于您的极限。
Well, it's easy to prove that there may not be a solution: just make your input graph a tree that has a vertex with degree higher than your limit..
加里·约翰逊（Garey Johnson）将这个问题简化为汉密尔顿:(所以这个有帮助。近似第一个：http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt
然而，更好的工作模型值得赞赏......
计数：http://mathworld.wolfram.com/SpanningTree。 html 。 据此，mathematica 有一个函数。 这方面有什么建议吗？
Garey Johnson had this problem reduce to hamilton :( So this one helped. Approximating the first one: http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt
However, better working models are appreciated...
Counting: http://mathworld.wolfram.com/SpanningTree.html . According to this, mathematica has a function. Any suggestions in this one?
本文展示了如何在多项式时间内找到最大度数为 d + 1 的生成树，该生成树至少与任何最大度数为 d 的生成树一样好：http://www.andrew.cmu.edu/user/mohits/mbdst.pdf
//编辑原始链接当前无效，请尝试 http://research.microsoft.com/pubs/ 80193/mbdst.pdf 代替。
This paper shows how to find, in polynomial time, a spanning tree of maximum degree d + 1 that is at least as good as any spanning tree of maximum degree d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf
//Edit The original link is currently inactive, try http://research.microsoft.com/pubs/80193/mbdst.pdf instead.