二分图的最大独立集问题

最大独立集和最大团

• 一个图中包含尽可能多个互相没有边的点组成的集合就称为这个图的最大独立集。

• 一个图中包含尽可能多个彼此都有边相连的点组成的集合称为这个图的最大团。

在一个图中的最大独立集等于在这个图的补图中的最大团。

与二分图的关系

不幸的是，在一般的图中，求解最大独立集是一个NP完全问题，但是幸运的是，在二分图中，这是一个可以解的问题，在二分图中，最大独立集中的点数等于所有点数减去匹配的数量，假设这个二分图一共有 $n$ 个结点，并且形成了 $k$ 个匹配，即说明其中至少 $k$ 个形成匹配的结点被删掉之后，这个图中剩下的所有点就彼此都没有边相连了，所以最大独立集的数量为 $n - k$ 。

而如果存在一个图，两边所有的节点都有边相连，并且两边有有几条边彼此相连，这显然是一个二分图的补图，如果要求这个图的最大团，即可以将该问题转化为对补图求最大独立集。

而同理，如果一个题目中涉及最大独立集或者最大团，就可以将该问图与二分图联想。