1). 二分图的最大匹配数等于其最小点覆盖数
点覆盖是指从图中找出一个点集 V,使得图中任意边与点集中某点相关,如果 V 集合中点数最小,称之为最小点覆盖集。
这个结论相信被很多人所知,然则如何去构造这个点覆盖集,这是一个值得思考的问题。
这个问题可以这样求解:
1. 对于在匹配中的点,随便选一个就行了。
2. 对于不在匹配中的点,我们用找类似找增广路径的方法找一条路径,路径中,非匹配边与匹配边交替出现。与增广路不同的是,该路径中有偶数条边,起点不在匹配中,终点在匹配中。然后取路径中第偶数个点为点覆盖集中的点,显然,所取的点能够覆盖这条路径中的所有边。
2). 二分图的最大独立集为顶点数减去最大匹配数
对于任何无向图有,最大独立数加上最大匹配数等于图的顶点数。
对于任何无向图有,最大团等于补图的最大独立集。