首页 > 代码库 > 二分图的性质
二分图的性质
二分图中,点覆盖数是匹配数。
(1) 二分图的最大匹配数 = 最小点覆盖数
即求最少的点使得每条边都至少和其中的一个点相关联,很显然直接取最大匹配的一段节点即可。
(2) 二分图的独立数 = 顶点数 - 最大匹配数
很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集,这是|V|-2*|M|,同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。
(3) DAG的最小路径覆盖=顶点数 - 最大匹配数
将每个点拆点后作最大匹配,结果为n-m,求具体路径的时候顺着匹配边走就可以,匹配边i→j‘,j→k‘,k→l‘....构成一条有向路径。
(4)最大匹配数=左边匹配点+右边未匹配点。
因为在最大匹配集中的任意一条边,如果他的左边没标记,右边被标记了,那么我们就可找到一条新的增广路,所以每一条边都至少被一个点覆盖。
(5)最小边覆盖 = 图中点的个数 - 最大匹配数 = 最大独立集。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。