首页 > 代码库 > 二分图的性质

二分图的性质


二分图中,点覆盖数是匹配数。


    (1) 二分图的最大匹配数 = 最小点覆盖数

          即求最少的点使得每条边都至少和其中的一个点相关联,很显然直接取最大匹配的一段节点即可。

    (2) 二分图的独立数 = 顶点数 - 最大匹配数

         很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集,这是|V|-2*|M|,同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。

    (3) DAG的最小路径覆盖=顶点数 - 最大匹配数

         将每个点拆点后作最大匹配,结果为n-m,求具体路径的时候顺着匹配边走就可以,匹配边i→j‘,j→k‘,k→l‘....构成一条有向路径。

 (4)最大匹配数=左边匹配点+右边未匹配点。

            因为在最大匹配集中的任意一条边,如果他的左边没标记,右边被标记了,那么我们就可找到一条新的增广路,所以每一条边都至少被一个点覆盖。

 (5)最小边覆盖 = 图中点的个数 - 最大匹配数 = 最大独立集。