柯尼希定理的图论表述

发布网友发布时间：2022-05-13 13:59

共1个回答

热心网友时间：2023-10-11 14:27

在图论中，柯尼希定理是这样一个定理：二分图最小点覆盖的点数=最大匹配数。
证明：
假设已经找到二分图G的一个最大匹配M，A、B为由二分图定义所得的两个点集，现在从B点集（A点集也行，不影响）中非饱和点（往往不止一个）出发，循着”非匹配边->匹配边->非匹配边->匹配边……”的原则走下去，沿途标记所走过的点，最后得到的边显然是匹配边（这个不理解的，这里就废话了，要自己想。。。），且边数为偶数，终止点是B点集的点。取A点集中标记的点与B点集中未标记的点记为点集S，那么这个点集S即为图G的一个最小点覆盖，且点数等于最大匹配数。到这里有三个问题要解决：为啥S中的点能覆盖图G的所有边；为啥S中点的个数等于最大匹配数；为啥S是最小的点覆盖；第一，只要说明不存在这样的一条边，它的左端点未标记，右端点标记就ok了，假设存在这样的一条边，首先它只能是非匹配边，因为按照上述的原则会发现匹配边的标记只能从A点集中的点出发，所以匹配边如果有标记的必然是左右端点都标记，但是如果它是非匹配边的话，那么就可以继续走，走到它的未标记的左端点，这样一来便与前述矛盾。所以，S中的点能覆盖图G中的所有边。
第二，因为每个点都是匹配M某条边的一个端点。为什么呢？我们假设B点集中未标记的某个点没有对应某条匹配边，那么它早就被标记了。假设A点集中标记的点没有对应某条匹配边，那就走不到它那里，因为如果可以，那么就会形成一条增广轨了……这是最大匹配M所不允许的。又一条匹配边或者两端点都标记，或者都未标记，这保证了不会S中点对应的匹配边不会重、不会漏。所以，点集S中的点与匹配M中的边一一对应。
第三，这个就显而易见了，因为匹配M，我们知道，覆盖点集数至少为最大匹配数，所以点集S是最小点覆盖集。
综上，证明完毕。