网站建设 东方网景网站整站优化推广方案

参考链接

定义

二分图就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

二分图判断方法

染色法：两种颜色给顶点逐个染色，相邻顶点具有不同的颜色。

引理

在最大匹配中，每条匹配边连接的两个顶点 (u, v) 最多只有一个与非匹配点有连边。

最小顶点覆盖

选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

上图中，最小顶点覆盖是： (2, 4, 6)

K ̈onig’s lemma：二分图的最大覆盖大小=最小点覆盖大小

证明：
对于二分图 G，以及匹配图 M，最大匹配数为 m；
1）我们可以构造一个点集，这个点集是从最大匹配 M 里面取出来的，对于每一条匹配边，选择那个与非匹配点有连边的点（根据引理1，这个点最多只有一个）加入点集 V；如果不存在，则随便选一个，总共选择 m 个点。
如图所示：三条匹配边 (1,6) (2,5) (4,7)；点集 V 构造的时候，(1,6) 这条边选择 6 这个点，(2,5) 这条边选择 2 这个点， (4,7) 这条边选择 4 这个点；这个点集至少可以覆盖 M，即最小顶点覆盖≥m；
2）如果 G 中的边除了 M 中匹配边以外没有其它非匹配边，那么最小顶点覆盖=m；
3）否则，还存在非匹配边，如果这条非匹配边的两个端点都在非匹配点上，那么可以构成一条新的匹配边，从而和最大匹配矛盾；所以这些非匹配边一定是其中一个端点在匹配点上，另一个端点在非匹配点上；
4）令一条非匹配边上的一个端点为 u ，且 u 在非匹配点上，那么如果存在一条边 (u, v)，点 v 必定是在我们构造出来的点集 V 中的，于是边 (u, v) 一定可以被这个点集覆盖，所以 最小顶点覆盖 = m；

最小顶点覆盖问题

给定一个n×n的棋盘，黑白格子组成，白色格子可以放置棋子，黑色格子不能放置棋子，如果一行或者一列上有其它棋子，并且中间没有任何黑色格子，那么这样的放置是非法的，求尽量放置最多的棋子（类似国际象棋中的 “车”）

按照行分块：

按照列分块：

每个格子属于一个行分块和列分块。
假设格子(r,c)，行分块为x，列分块为y。
把一个能够放置棋子的点看成二分图的边，选择最少的行列分块（对应二分图的点）覆盖所有格子，转换成最下顶点覆盖问题，求构造后的图的最大匹配即可。

最小边覆盖

选了一条边就相当于覆盖了它的两个端点。最小边覆盖就是选择最少的边集，覆盖所有的点集。

上图中，最小边覆盖 E = {(2,9), (3, 8), (5, 10), (4, 9), (3, 11)}，答案是5

二分图的最小边覆盖=顶点总数-孤立点数-最大匹配

最小独立集

选取最多的点，使任意两点都没有关系。

上图中，最大独立集V = {1, 3, 5, 7, 8}

二分图罪最大独立集=顶点总数-最小顶点覆盖

最大完全子图

选取最多的点使图中任意两点都有关系。

二分图的最大完全子图=补图的最大独立集

（不相交）有向无环图的最小路径覆盖

选择一些路径覆盖所有点集，各路径的点集之间没有交集，要求路径数最少。

上图中，最小路径覆盖：1-2-4-5、6-7、3，答案是3