有界度生成树中的 np 完整性
我理解为什么有界度生成树被认为是具有 1 或 2 度的 NP 完全（它是哈密顿路径问题的一个实例），但我不明白为什么这适用于度数 > 的情况。 2. 如果有人可以解释一下为什么这是一个 NP 完全问题，学位 > 2、这将是最有帮助的
I understand why the Bounded Degree Spanning Tree is considered NP Complete with a degree or 2 (it is an instance of the Hamiltonian Path Problem), but I do not understand why this applies to degrees > 2. If someone could please explain why this is an NP Complete problem for degree > 2, It would be most helpful
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
好吧，我认为你可以从有界 2 的实例简单归约到 General k 的实例。
直观地说，我们将连接到原始图的每个节点新的 k-2 个节点。因此，每个生成树都必须包含从原始节点到我们连接到它的新节点的 k-2 条边，并且如果存在度数最多为 2 的生成树，则存在度数最多为 k 的生成树。原始图表。
形式化简为：
F(V,E)=(V',E')，当：V'={(v,i)|v 在原图中，0 <<我< k+1), E' = EU {((v,0),(v,i))}，我没有为正确性写出正式的证明，因为毕竟我们不是在数学论坛中。
祝你好运并希望它有所帮助:)
Well, I think that you can make a simple reduction from the instance of bounded by 2, to the instance of General k.
Intuitivly, we will connect to each node of the original graph new k-2 nodes. Therefore every spanning tree will have to contain the k-2 edges from the original node to the new nodes that we connected to him, and a spanning tree from degree at most k exists if there is a spanning tree of degree at most 2 for the original graph.
The formal reduction will be:
F(V,E)=(V',E'), when : V'={(v,i)|v is in the original graph, 0 < i < k+1), E' = E U {((v,0),(v,i))}, and I don't write a formal proof for the correctness because after all we are not in a math forum.
Good luck and hope that it helped :)