笔记汇总

König 定理

前言

最小点覆盖： 无向图中 任意一条边 的两个端点都 至少 有一个被标记时 标记过的点数 的 最小值。

最大匹配数： 二分图中 任意两条边 没有公共端点时边数量的 最大值。

最大独立集： 没有线段相连的最大点集

增广路： 交替连接 二分图左右两个集合 的路径。

结论

一个二分图中的 最大匹配数 等于这个图中的 最小点覆盖数。

证明

最小点覆盖数 >= 最大匹配数

因为最大匹配数 没有公共交点，所以 等于 没有公共交点的匹配边 的端点数，

显然 不大于 有公共交点的匹配边 的端点数。

最大匹配数可以 = 最小点覆盖数

这里有两种方式证明，第一种为独创。

证明 1

因为 有公共交点 的所有匹配边的 其中一个端点，一定会被 最大匹配中的匹配边 包含。

我们可以运用 反证法，

先定义 准匹配边 为除 最大匹配中的匹配边 以外的匹配边，且必定连接的是匹配点

如果没法找到一种标记 最大匹配中的点 的方式，可以让所有 准匹配边 的两个端点 至少 有一个被标记，则 结论不成立。

第一步，我们标记 所有边 的两端点在 最大匹配中的点 只有一个的。

第二步，剔除 最大匹配中的匹配边 有端点被标记过的。

第三步，重复第一步

第四步，重复第二步，知道所有匹配边被剔完

以上步骤不成立当且仅当以下假设成立：

第一，有 最大匹配中的匹配边 在第一步中 两个端点都被标记。

但是这个假设不可能成立，因为如果存在 两个端点都被标记，

则存在几组准匹配边，分别连接 最大匹配中的匹配边 的两个端点，准匹配边数必然多于其 连接端点了的匹配边

若取代原匹配边，则 新匹配数 优于 原匹配数，并 不满足 最大匹配的定义。

第二，剔除后，有 未标记端点的准匹配边 没有与 最大匹配中的匹配点 的 公共点。

也不满足，因为 准匹配边 连接的两个点属于不同的 最大匹配中的匹配边，在剔除一次后，还有至少一个公共点。

其连接的匹配边若都剔除，则其至少也会有点被标记，此处见 第一条

所以不存在。

反证完毕，结论满足