Konig 定理及其证明 杨欣然 171250630

总览 01 概念回顾 02 匈牙利算法 03 Konig定理及其证明 04 参考资料

概念回顾 二分图： 最大匹配： 最小顶点覆盖： 如果一张图的顶点可以划分为两个集合, 使得图中的每条边在每个集合中都有一个端点, 则该图是二分图(bipartite graph)。 最大匹配： 图中的匹配指是一组没有两个共享终结点的边集。如果没有其他匹配具有更多的边, 则称该匹配是最大匹配(maximum matching)。 最小顶点覆盖： 图中的顶点覆盖是一组顶点, 图中的每条边都至少有一个端点包含其中。如果没有其他顶点覆盖具有更少的顶点数, 则称该覆盖为最小顶点覆盖(minimum vertex cover)。

Statement of the theorem Konig定理 Statement of the theorem 在任何一个二分图中，最大匹配中的边数等于最小顶点覆盖中的顶点数。 （In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.） Example： 上图所示的二分图有14个顶点;与六个边的匹配以蓝色显示, 带有六个顶点的顶点盖以红色显示。不能有更小的顶点覆盖, 因为任何顶点覆盖必须包含每个匹配边 (以及每个其他边) 的至少一个端点, 因此这是最小的顶点覆盖。同样, 不能有更大的匹配, 因为任何匹配的边都必须在顶点覆盖中至少包含一个端点, 因此这是最大匹配。Kőnig 定理指出, 匹配和盖的大小之间的相等性 (在本例中, 两个数字都是 6) 更普遍地适用于任何二部图。

求解最大匹配问题的一个算法——匈牙利算法 增广路的定义： 若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。 Example： 左图的一条增广路径： 推论： 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2. 将M和P进行异或操作可以得到一个更大的匹配M’。 3. M为G的最大匹配当且仅当不存在M的增广路径。

求解最大匹配问题的一个算法——匈牙利算法 匈牙利算法框架： 置M为空。 找出一条增广路径P，通过异或操作获得更大的匹配 代替M。 重复（2）操作直到找不出增广路径为止。 复杂度：O（VE） 举例

Konig定理之证明 1. 假设已经通过匈牙利算法找到最大匹配，给所有这样的点打上记号√：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。 2. 下面证明这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。（即左图中圈出的点） 假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。 匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。看图，右图中展示了两条这样的路径，标记了一共6个点（用 “√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。

证明最小覆盖点集为：右边所有没有打上记号的点，加上左边已经有记号的点。 Konig定理之证明 证明最小覆盖点集为：右边所有没有打上记号的点，加上左边已经有记号的点。 3.因为每个点都是某个匹配边的其中一个端点，故此点集恰含M个点。（此点集中，若右边某点未被匹配，其必被标记，矛盾；若左边某点未被匹配，则必无标记，矛盾。故此点集中的点必与匹配边相连。而匹配边的两端必然同时有或没有记号，故必有且仅有一端在此点集中。） 4. 假设有一条边未被该点集覆盖，其必为非匹配边，则其左端必无标记。所以其右端必有标记（否则就被点集覆盖）。但此时到达右端的那条标记条路径就能通过这条边扩展到左端，所以左端也将有标记，矛盾。故假设不成立，即该点集能覆盖所有的边。 首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。 其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。 最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。 5. 因为想要覆盖M条匹配边就至少需要M个点，故此点集为最小覆盖点集。综上，Konig定理得证。

1. Kőnig's theorem (graph theory) ——Wikipedia 参考资料 1. Kőnig's theorem (graph theory) ——Wikipedia 2. Hungarian algorithm ——Wikipedia 3. A First Course in Graph Theory ——C.Z. 4. http://www.matrix67.com/blog/archives/116

Thank you！ 杨欣然171250630