有界度生成树中的np完备性 [英] np-completeness in the bounded degree spanning tree

问题描述

我明白为什么有界度生成树被认为是NP完全度数为2（它是哈密尔顿路径问题的一个实例），但我不明白为什么这适用于度> 2。如果有人可以请解释为什么这是一个NP完全问题> 2，这将是最有帮助的

解决方案

好吧，我认为你可以做我们将连接到原始图的每个节点新的k-2个节点。因此，每个生成树必须包含从原始节点到我们连接到他的新节点的k-2个边，如果存在度数至多为2的生成树，则存在从度数至多为k的生成树原始图。

正式缩减将是：

（V，E）=（V'， E'），当：V'= {（v，i）| v在原始图中时，0<我<我不写一个正确的证明来证明正确性，因为毕竟我们不在数学论坛中。 p>

祝你好运，并希望它有助于：）

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

解决方案

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 :)

这篇关于有界度生成树中的np完备性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！