算法入门练习 8.19 风筝图

题目：

若有一个图，其顶点数为偶数（比如2n），且其中的n个顶点构成一个团，其余的n个顶点则有一条称为“尾巴”的路径连接，尾巴的某个端点与团中一个顶点相连，这样的图称为“风筝图”。现给定一个图G和目标g，风筝图问题的目标是求出该图的一个包含2g个顶点的风筝子图。请证明该问题是NP-完全的。

证明：

我们可以将团问题归约到风筝图问题。团问题的目标是求出某图的一个包含g个顶点的完全子图。

现设无向图G = (V, E)，其中|V| ≥ 3。按以下方法构造图G’，在图G中新增|V|个新顶点，每个新顶点分别与原顶点相连，使得新顶点和原顶点形成一一映射的关系，边数共增加|V|。然后再新增|V| - 1个顶点，连成一条路径，将该路径的其中一个端点和最初新增的|V|个顶点相连，得到图G'。图示如下：

构建图G'后，即可将团问题归约到风筝图问题。

① 在图G'中，原属于图G的顶点都有一条长度为g的“尾巴”，若图G'中不存在包含2g个顶点的风筝子图，则意味着原属于图G中的顶点不能构成规模为g的团，即图G中不存在规模为g的团。

② 若图G'中存在包含2g个顶点的风筝子图，则G'中存在规模为g的团，而这个团必定由原属于G中的顶点和边构成，因此图G中存在规模为g的团。

综上所述，图G'中存在包含2g个顶点的风筝子图，当且仅当图G中存在规模为g的团。因为团问题是NP完全问题，所以风筝图问题也是NP完全问题，完成规约。