将独立集减少为派系？

Question

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

Answer 1

独立集是一组节点，其中对于该集中的任何一对节点，这些节点之间不存在边。团是一组节点，其中对于集合中的任何一对节点，这些节点之间都有一条边。因此，图 G 中的独立集是 G 的补集中的团，反之亦然。

鉴于此，将给出 G 和 k 进行简单变换以产生 G ^c（G 的补集）和 k。那么，G 有一个大小为 k 的独立集当且仅当 G ^c有一个大小为 k 的团。

希望这可以帮助！