题号：8.14
题目描述：
中文释义：证明以下问题是NP完全问题：给出一个无向图 G = (V, E)和一个整数 k，返回一个大小为 k 的团和一个大小为 k 的独立集。
解题思路：
这道题是证明NP完全问题，所描述的问题有 independent set 独立集问题和 clique 团问题。
根据书上所提供的以下搜索问题分类表格，我们可以得知独立集问题属于NP完全问题。
所以我们只需证明团问题是NP完全问题即可。我选择的证明方法是利用归约A->B的第二种中途：已知A是NP完全的，证明B是NP完全的，算法的“困难性”从A流向B。因此只要证明独立集问题可以归约为团问题，就可得出团问题也为NP完全问题。
证明如下：
定义图 G = (V, E)的补图为~G = (V, ~E)，~E只包含那些不在E中的无序顶点对，即一个图G的补图是一个图有着跟G相同的点，而且这些点之间有边相连当且仅当在G里面他们没有边相连。则一个点集S是G的一个独立集，当且仅当S是~G的一个团，因为S在G中两两独立可以推出S在~G中两两相连。因此通过将独立集中的实例（G，g）映射到团中对应的实例（~G，g），我们可以将独立集归约到团。
