首页 > 代码库 > 二分图的一些定理

二分图的一些定理

最小点覆盖:用最少的点(X集合或Y集合都的都行)让每条边都至少和其中一个点关联。

结论:最小点覆盖数 = 最大匹配数M

因为只需要让它们覆盖最大匹配的M条边,则其它边一定被覆盖,而每一条边只需选择一个节点。

 

DAG图的最小路径覆盖:用尽量少的不相交的简单路径覆盖有向无环图所有顶点。

二分图模型:把所有顶点 i 拆成两个:X集合中的 i 和Y集合中的 i‘。若有边 i->j,则在二分图中引入边 i->j‘。

结论:DAG图的最小路径覆盖数 = 节点数N - 最大匹配数M

 

最大独立集:在一个二分图中,选择最多的顶点(可以是左集合中的也可以是右集合中的),使得所选择的点集中任意两点之间没有连边。

结论:最大独立集 = 节点数N - 最大匹配数M。

可以这样理解,在总的点集中,去掉最少的点,使得剩下的点相互之间没有边。即用最少的点去覆盖所有的边。这样就转化成了最小点覆盖。

二分图的一些定理