首页 > 代码库 > 二分图的一些定理
二分图的一些定理
最小点覆盖:用最少的点(X集合或Y集合都的都行)让每条边都至少和其中一个点关联。
结论:最小点覆盖数 = 最大匹配数M
因为只需要让它们覆盖最大匹配的M条边,则其它边一定被覆盖,而每一条边只需选择一个节点。
DAG图的最小路径覆盖:用尽量少的不相交的简单路径覆盖有向无环图所有顶点。
二分图模型:把所有顶点 i 拆成两个:X集合中的 i 和Y集合中的 i‘。若有边 i->j,则在二分图中引入边 i->j‘。
结论:DAG图的最小路径覆盖数 = 节点数N - 最大匹配数M
最大独立集:在一个二分图中,选择最多的顶点(可以是左集合中的也可以是右集合中的),使得所选择的点集中任意两点之间没有连边。
结论:最大独立集 = 节点数N - 最大匹配数M。
可以这样理解,在总的点集中,去掉最少的点,使得剩下的点相互之间没有边。即用最少的点去覆盖所有的边。这样就转化成了最小点覆盖。
二分图的一些定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。