graph - 将独立集减少为派系？

Question

证明给定图 G 和数字 k，有某种方法可以将其转换为图 H，使得 G 具有大小至少为 k 的独立集合，当且仅当 H 具有大小为至少 k。

Answer 1

独立集是一组节点，其中对于该集中的任何一对节点，这些节点之间没有边。团是一组节点，其中对于集合中的任何一对节点，这些节点之间有一条边。因此，图G中的独立集是complement中的一个派系。 G，反之亦然。

鉴于此，对 G 和 k 进行简单的变换即可产生 G^c (G 的补集)和 k。那么，G 有一个大小为 k 的独立集合当且仅当 G^c 有一个大小为 k 的团伙。

希望这有帮助!