8.14 证明如下问题是NP完全的

8.14 证明如下问题是NP完全的

8.14 给定一个无向图G =(V,E)和整数k，求G中一个规模为k的团以及一个规模为k的独立集。假定它们都是存在的。

解析：

在这个问题中，我们所要求的G中一个规模为k的团就是求图G中k的顶点，使得这些顶点之间两两都存在相连的边。

我们首先假设要求任意图G(V,E)中大小为k的团，以此为基础的情况下，可以在此图G中添加k个相互独立的顶点，得到的一个新的图G'。

在G'中 ，这k个相互独立的顶点，可以保证图G‘中存在大小为K的独立集，而且我们是在图G中的团的基础上添加的这个独立集，所以不影响图G的团

因此我们现在就把证明求G中一个规模为k的团以及一个规模为k的独立集是一个NP-完全问题转化成为了先求出G规模为k的团，在添加k的顶点的独立集

这个问题上。而我们知道，求G中规模为k的团这个团问题是一个NP-完全问题。所以我们可以把最大团问题规约到这个问题上来。

因此给定一个无向图G =(V,E)和整数k，求G中一个规模为k的团以及一个规模为k的独立集。这是一个NP-完全问题。