我理解为什么有界度生成树被认为是具有度或2的np完全（它是哈密顿路径问题的一个实例），但我不理解为什么这适用于度>2。如果有人能解释一下为什么这是一个NP完全问题，对于学位>2，这将是非常有用的
最佳答案
好吧，我想你可以做一个简单的简化，从2的有界实例，到一般的k的实例。
直观地，我们将连接到原始图的每个节点新的k-2节点因此，每个生成树必须包含从原始节点到连接到他的新节点的K-2边缘，并且如果存在原始图的最大生成树的2度，则存在从最大k处的生成树。
正式的削减将是：
f（v，e）=（v'，e'），当：v'={（v，i）v在原始图中时，0祝你好运，希望它能帮上忙：）