二分图性质

二分图独立集定义：在二分图 \(G\) 中选出点集 \(S\) 使得点集 \(S\) 中的点两两之间没有边相连。

二分图最大独立集定义：在 二分图 \(G\) 中选出点集 \(S\) 使得点集 \(S\) 中的点两两之间没有边相连，且使得不存在另一个二分图独立集 \(S'\) 使得 \(|S'|>|S|\)。

二分图最大独立集 \(S\) 满足 \(|S|=n-|\underline{S}|\)，其中 \(\underline{S}\) 是一组二分图最大匹配的点集。

补二分图团定义：在补二分图 \(G\) 中选出点集 \(S\) 使得点集 \(S\) 中的点两两之间都有边相连。

补二分图最大团定义：在 补二分图 \(G\) 中选出点集 \(S\) 使得点集 \(S\) 中的点两两之间都有边相连，且使得不存在另一个二分图团 \(S'\) 使得 \(|S'|>|S|\)。

补二分图最大团性质：在 补二分图 \(G\) 上找到这个补二分图的补图 \(G'\)，其中 \(G'\) 是一个二分图。则 \(G\) 的最大团的大小恰好等于 \(G'\) 的最大独立集的大小。