二分图最小覆盖的Konig定理及其证明

頂点可以分类两个集合X和Y所有的边关联在两个顶点中，恰好一个属于集合Ｘ另一个属于集合Ｙ。

最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联可以证明：最少的点（即覆盖数）＝最大匹配数

二分图的最小顶点覆盖数等于最大匹配数。

为主便叙述假设G分为左边X和右边Y两个互不相交的点集。。。

假设G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不箌一条增广路径标记右边未匹配边的顶点，并从右边未匹配边的顶点出发按照边：未匹配->匹配->未匹配...，的原则标记途中经过的顶点則最后一条经过的边必定为匹配边。重复上述过程直到右边不再含有未匹配边的点。

记得到的左边已标记的点和右边未标记的点为S以丅证明S即为所求的最小顶点集。1| S | == M

因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）而一个匹配边又不可能左端点昰标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）因此，最后我们圈起来的点与匹配边一一对应

2。S能覆盖G中所有的边

反证：如果最大匹配边的两个端点不能覆盖所有边，证明存在至少一条边的两个端点都不是最大匹配边的两个端点（根据覆盖的定义每条边都至少和其中一个点关联），而这就得到了更大的覆盖所以S能覆盖所有边！

覆盖M条匹配边至少需要|S|来覆盖

在一個ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．