526互联

二分图相关结论

发布时间 2023-09-17 22:44:26作者: 灰鲭鲨

最小点覆盖：

定义：选择最少的点，使得每条边都有一端被选。

结论：二分图的最小点覆盖等于二分图最大匹配

构造方案：从所有左侧未匹配的点出发，先走一条未匹配边，然后走一条匹配边，把所有走过的点标记，选择左边所有未标记的点和右边所有标记的点。

最大独立集

定义：选择最多的点，使得他们之间两两没有边。

结论：二分图的最大独立集是最小点覆盖的补集。

证明：如果一条边中两个点都在最大独立集中，其补集这条边没有被覆盖，不符合定义。