算法概论 课后习题 8.12

8.12题目大意

输入：无向图

输出：G的一个生成树，其中所有节点度数都不超过k——如果该树存在。

请证明对任意k>=2：

(a) k-生成树问题是一个搜索问题。
(b) k-生成树问题是NP-完全的。（提示：由k=2开始，考虑该问题与Rudrata路径问题的关联）

证明

(a)

一个搜索问题的定义是：任何可能解的正确性都能快速地被验证，而快速指的是能够在多项式时间内被验证。

对于给定的一个可能解G’ = (V’, E’)，需要证明一下三点：
1. V′=V 点集跟原来一样
2. E′∈E  新的边集是原来的子集
3. V’ 中的任意一个顶点，其度数都小于等于k

这个三点都可以在多项式时间内完成，因此k-生成树问题是一个搜索问题。

(b)

由(a)可知，k-生成树问题是NP问题。

k = 2时，若2-生成树存在，则该生成树是图的一条最长链，该链包含图中的所有节点。取最长链的两端节点，则该链实际为一条Rudrata路径（一条经过每个顶点恰好一次的环路），因此2-生成树问题就是Rudrata路径问题。

k>2时，同理可证k-生成树问题就是Rudrata路径问题的一种情况。（事实上，当k大于等于图中最大点度时，这个问题退化为在图上找一棵任意生成树）

因为k-生成树问题可以归约为Rudrata路径问题，而Rudrata问题是NP-完全问题，所以k-生成树问题是NP-完全问题。