2019-10-05

二分图相关概念之一网打尽

缘起

最近开始研究二分图. 但是相关概念比较杂, 所以打算写篇文章好好整理一下. 找到了原先收集的【1】. 阅读并吸收之~

分析

什么是二分图

二分图是这样一个无向图：有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接.

严格的数学定义如下

1
2
3

设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2之并，
并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。
二分图也可记为G=(V1,V2,E)。

无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。所以易知：任何无回路的的无向图（例如树）均是二分图。

判断二分图的常见方法是交叉染色法：开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色，若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，bfs和dfs可以搞定！交叉染色法判定二分图见【2】

点集、边集的一些概念

点覆盖、极小点覆盖、最小点覆盖、点覆盖数

点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。

极小点覆盖：本身为点覆盖，其真子集都不是。

最小点覆盖：点最少的点覆盖。

点覆盖数：最小点覆盖的点数。

边覆盖、极小边覆盖、最小边覆盖、边覆盖数

边覆盖集即一个边集，使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。

极小边覆盖：本身是边覆盖，其真子集都不是。

最小边覆盖：边最少的边覆盖。

边覆盖数：最小边覆盖的边数。

独立集、极大独立集、最大独立集

独立集即一个点集，集合中任两个结点不相邻，则称V为独立集。

极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。

最大独立集(maximum independent set)：点最多的独立集。

独立数：最大独立集的点。

团

团即一个点集，集合中任两个结点相邻。

极大团：本身为团，再加入任何点都不是。

最大团：点最多的团。

团数：最大团的点数。

边独立集（又称匹配）

边独立集（又称匹配）即一个边集，满足边集中的任两边不邻接。

极大边独立集（又称极大匹配）：本身为边独立集，再加入任何边都不是。

最大边独立集（又称最大匹配）：边最多的边独立集。

边独立数（又称匹配数，或者最大匹配数）：最大边独立集的边数。

在匹配中的点称为匹配点或饱和点；反之，称为未匹配点或未饱和点。

交错轨是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。

增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。

完美匹配是匹配了所有点的匹配。

完备匹配是匹配了二分图较小集合（二分图X，Y中点的个数较小的那个）的所有点的匹配。

支配集

支配集即一个点集，使得所有其他点至少有一个相邻点在集合里。或者说是一部分的“点”支配了所有“点”。

极小支配集：本身为支配集，其真子集都不是。

最小支配集：点最少的支配集。

支配数：最小支配集的点数。

边支配集

边支配集即一个边集，使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边”。

极小边支配集：本身是边支配集，其真子集都不是。

最小边支配集：边最少的边支配集。

边支配数：最小边支配集的边数。

最小路径覆盖

最小路径覆盖(path covering)：是“路径” 覆盖“点”，即用尽量少的不相交简单路径覆盖DAG中的所有顶点，即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。

最小路径覆盖数定义为DAG图的点数 - 最小路径覆盖中的边数。所以最小路径覆盖中的边数越多, 最小路径覆盖数就越小.

二分图和上面的概念之间的关系

二分图的点覆盖数是匹配数（即Konig 定理）。因为只需要取匹配的边的1个顶点即可组成点覆盖。
二分图的独立数等于顶点数减去最大匹配数。因为只需要匹配中的每条边去掉其中一个顶点即可.
DAG的最小路径覆盖数问题. 解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i’,如果有边i->j，则在二分图中引入边i->j’，设二分图最大匹配为m,则结果就是n-m。因为匹配数就是最小路径覆盖的边数.
最小边覆盖 = 图中点的个数 - 最大匹配数（亦即点覆盖数） = 最大独立集。最大独立集与最小点覆盖集互为补集
所有匹配算法都是基于增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。这个定理适用于任意图。

很多题目都来源于二分图的最大匹配,其实很少有题目会单纯的要你求出最大匹配，而是往往做一些简单的变化, 二部图的最大匹配问题有以下三个变种

变种1：二分图的最小顶点覆盖

变种2：DAG图（无回路有向图）的最小路径覆盖

变种3: 二分图的最大独立集

这些变种的求法在上面的结论中聪明如你应该知道怎么做了^_^.

相关算法

二分图的最大匹配算法

匈牙利算法（bfs或者dfs实现）
Hopcroft-Karp算法（下简称HK算法）

二分图最小点覆盖与最大独立集的构造算法

二分图带权最优匹配求解

问题描述

二分图带权最优匹配：对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权之和最大，记做带权最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）

我们求二分图的带权最优完备匹配首先要回答的问题是该二分图是否存在完备匹配呢? 我们有Hall定理.

Hall定理：设二分图中G=<V1,V2,E>中|V1|=m<=|V2|=n，G中存在从V1到V2的完备匹配当且仅当V1中任意
k(k=1,2,...,m)个顶点至少与V2中k个顶点相邻（相异性条件）。

证明：

（必要性）显然成立。

（充分性）反证法。设G中不存在完备匹配，取G的一个最大匹配M，则V1中至少有一个点不在M上，且该点必至少
与一条不在M中的边相连（因为k=1时, 可知该点与V2中的一个顶点相邻,而此边一定不在M中, 否则,该点就在M中了, 与假设矛盾），该边的另一个顶点若也为M-非饱和点，则与M为最大匹配矛盾，若另一个顶点为M-饱和
点，则考察在M中与该顶点相邻的点，利用饱和点去考察在M中相邻的饱和点（交错地考察，即交错地通过M中的边
和非M中的边），直至考察完毕，由相异性条件知，最后必考察至非饱和点，此时出现一条增广路，又与假设矛
盾，故充分性成立。

Hall定理的一个推论：设二部图中G=<V1,V2,E>中|V1|=m<=|V2|=n，V1中每个顶点至少关联正整数t条边，V2中
每个顶点至多关联t条边（t条件），则G存在从V1到V2的完备匹配。

求二分图的带权最优匹配的算法是Kuhn-Munkers算法，可以实现 O(n^3)复杂度.

Kuhn-Munkers算法的几种变形应用

1.Kuhn-Munkers算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。

2.Kuhn-Munkers算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。

3.Kuhn-Munkers算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。

ps: 算法部分, 我并没有给出, 本文的目的仅仅是厘清二分图中的一些相关的概念以及要用到的算法, 至于算法的实现, 后面的文章我会继续写的. ^_^

参考

【1】https://www.iteye.com/blog/dsqiu-1689505

【2】https://yfsyfs.github.io/2019/08/21/%E7%89%9B%E5%AE%A2%E7%BD%91-%E4%BA%8C%E5%88%86%E5%9B%BE%E5%88%A4%E5%AE%9A%E4%B9%8B%E4%BA%A4%E5%8F%89%E6%9F%93%E8%89%B2%E6%B3%95/