我理解为什么有界度生成树被认为是 NP Complete 度数或 2(它是哈密顿路径问题的一个实例)，但我不明白为什么这适用于度数 > 2。如果有人可以解释为什么会这样度 > 2 的 NP Complete 问题，这将是最有帮助的
最佳答案
好吧，我认为您可以从以 2 为界的实例，简化为 General k 的实例。
直观地，我们将连接到原始图新 k-2 个节点的每个节点。因此，每棵生成树都必须包含从原始节点到我们连接到他的新节点的 k-2 条边，如果存在度最多为 2 的生成树，则存在度最多为 k 的生成树原始图。
正式的减少将是:
F(V,E)=(V',E')，当:V'={(v,i)|v 在原图中，0 < i < k+1)，E' = EU {(( v,0),(v,i))}，并且我不会为正确性写正式的证明，因为毕竟我们不在数学论坛中。
祝你好运，希望它有所帮助:)
关于graph - 有界度生成树中的 np 完备性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7848070/