graph - 有界度生成树中的 np 完整性

Question

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

Answer 1

好吧，我认为您可以从以 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))}，并且我没有为正确性写正式的证明，因为毕竟我们不在数学论坛中。

祝你好运，希望它有所帮助:)