二分图的性质¶
by nalemy
最小点覆盖¶
定义¶
最小集合 使得 都有 且 。
即所有的边中最少有一个端点在 中。
性质¶
设二分图 的最小点覆盖为 ，最大匹配为 ，有 。
即 （König 定理）。
证明¶
对于二分图 中的最大匹配 （ 为一边集）。
Lemma 1¶
对于每一个最大匹配中没有匹配的点 ， 必然有匹配。
否则，如果 无匹配，那么 可以形成另一组匹配，和最大匹配的定义不符。
从右侧每一个没有匹配的点 出发，经过每一条边到达左边的一个点 。根据 Lemma 1， 必然有匹配，我们再经过这条匹配边到达 的匹配……像这样交替通过非匹配边和匹配边形成一条路径，直到右边的点无路可走。（如图）
我们在左边找出这些路径经过的点，右边找出没有经过的点，它们组成集合 。下面我们分三部分证明此定理。
Lemma 2¶
没有一条边 使得 且 ，也没有一条边 使得 且 。
说明 能够被至少一条路径到达，此时 也应该能被到达，所以 ，与假设矛盾。后半部分同理。
- 为图 的一个点覆盖集。我们假设有一条边 没有被覆盖，即 且 。根据 Lemma 2，这样的边是不存在的。
- 。我们尝试证明 和 存在双射。首先，对于 中位于左边的，它一定是某个匹配的左端点；对于 中位于右边的点，它肯定是某个匹配的右端点，否则就被选为路径起点了。这说明存在从 到 的单射。并且，根据 Lemma 2，对于 中的每对匹配，都有且只有一个端点在 中。这说明存在从 到 的满射。综上， 间存在双射 。
- 为最小的点覆盖集。覆盖所有的匹配边就至少需要 个点，少于 个点的点集一定不是点覆盖集。
证毕。
最大独立集¶
定义¶
最大集合 使得 都有 或 。
即所有边中最多有一个端点在 中，也就是 中的任意两点无连边。
点覆盖是涵盖所有边，而独立集则是避开所有边。
性质¶
设二分图的最大独立集为 ，最大匹配为 ，有 。
即 。
证明¶
对于二分图 的最小点覆盖 （ 为一点集）。
Lemma 1¶
删去 中的点与其相连边后，图不存在边。
根据点覆盖的定义显然。
分两部分来证明。令 。
- 为一个独立集。根据 Lemma 1 可知， 的导出子图中没有边，得证。
- 最大。如果存在模大于 的独立集 ，那么 一定为一个比 更小的点覆盖集。这与 为最小点覆盖矛盾。
综上， 为最大独立集，根据 的定义可导出其性质。
最大团¶
定义¶
最大集合 使得 都有 。
即最大点集使得其导出子图为完全图（此处要求二分图中每个左边顶点和每个右边顶点两两有边）。
性质¶
一张图的最大团为其补图的最大独立集。
补图的定义为，。
证明¶
对于图 ，其最大团中的点左右两两连边，也就对应反图 中两两不连边的集合，即最大独立集。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：AFOI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用