二分图-白红宇

二分图

阅读量：5328 次

发布时间：2019-06-14

本文共 3627 字，大约阅读时间需要 12 分钟。

1. 二分图

二分图是指在一个图中，将点集分为X和Y两个集合，使得图的边的两个端点总是分别落在X和Y上，不会有X中的点连向X中的点，也不会有Y中的点连接到Y中的点。

图1

如上图所示，顶点2,3,4构成集合X，顶点5,6,7构成集合Y。只存在X连接到Y的边或者Y连接到X的边。

2. 匹配

匹配是图中一些没有公共顶点的边的集合，如图1中的边2->5, 3->6, 4->7 这些边没有公共的顶点。边数最大的匹配为最大匹配，匹配中的边覆盖图中所有的点的匹配为完美匹配。

3. 求二分图的最大匹配

3.1 最大流算法

二分图最大匹配的边集合中每个X中的点只能连接一个Y中的点，这可以视为从每个X中的点流出的流量最大为1，即每个X中的点流入的流量最大为1（根据网络流守恒）；同理，每个Y中的点流出的流量最大为1。于是，可以添加源点s和汇点t，从s向每个X中的点引一条容量为1的边，从Y中的每个点向t引一条容量为1的边。

图2

那么，网络流图的最大流就恰好等于原二分图的最大匹配数。

3.2 匈牙利算法

3.2.1 算法思想

二分图求最大匹配的另一种算法是匈牙利算法，由Edmonds发明。其核心思想和求最大流的增广路算法一致，即不断求原图剩余网络的增广路，然后增广使得匹配数增加，直到无法找到增广路为止。

从当前二分图的一个未匹配的顶点出发，沿着未匹配路--匹配路--未匹配路--匹配路....的顺序一直走，得到的路径为交替路。

若交替路的最后一个顶点为未匹配顶点（也即最后一段路径为未匹配路径），则该交替路上的未匹配边比匹配边数多1，那么，可以通过沿着该交替路，将原来的匹配边变为不匹配，原来的不匹配边变为匹配，就可以使得匹配的边数增加1，匹配的顶点数加2，同时原来的匹配的顶点仍然为匹配顶点。这种交替路（未匹配的边数比匹配的边数多1）称为增广路。

增广路经的性质

（1）有奇数条边；

（2）起点在二分图的左半边，终点在二分图的右半边；

（3）路径上的点一个在左半边，一个在右半边，交替出现；

（4）把增广路径上的所有第奇数条边加入到原匹配中，将所有第偶数条边从原匹配中删除（称为增广路径的取反），则新的匹配比原匹配加1

每次找到一个增广路，就可以使得匹配数加1，匈牙利算法就是不断的寻找增广路，不断将匹配数加1，直到无法找到增广路为止。

3.2.2 算法实现

考虑通过DFS从X集合中的每个未匹配点开始，寻找增广路：

对于X中的顶点a（开始为未匹配顶点），若从a开始寻找了一条增广路，增广之后，a顶点就变为匹配顶点，则之后从其他顶点开始的增广操作是否会经过点a，a仍然都是匹配顶点，那么之后的增广操作就无法再从a开始（因为寻找交替路的操作从一个未匹配的顶点开始）。

因此，可以通过对X集合中的每个点进行一次寻找增广操作来实现匈牙利算法。

（1）DFS以一个位于X集合中的点u为参数，若u没有可以继续连接的边（向Y集合中连接），则最终无法使得交替路的终点位于Y集合中，则肯定无法构成一条增广路（参见增广路性质第2条），返回失败；

（2）若DFS的当前点u（位于集合X）可以找到一条边连接到顶点v（位于集合Y），若v没有被本次的DFS增广访问过，且v没有被一条匹配边连接（说明无法从v沿着一个匹配边继续向下走），则v可以作为此次增广路的终点，那么就将u和v作为一个匹配边，增广返回；

（3）若DFS的当前点u（位于集合X）可以找到一条边连接到顶点v（位于集合Y），若v已经有一条匹配边连接，那么v连接到的点t肯定位于集合X，于是继续对点t进行DFS找交替路。

#include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define MAX_NODE 1000#define MAX_EDGE_NUM 100000struct Edge{	int to;	int w;	int next;};Edge gEdges[MAX_EDGE_NUM];int gHead[MAX_NODE];int gMatch[MAX_NODE];bool gVisited[MAX_NODE];bool gVertexInLeft[MAX_NODE];bool Dfs(int u){	for (int e = gHead[u]; e != -1; e = gEdges[e].next){		int v = gEdges[e].to;		if (!gVisited[v]){			gVisited[v] = true;			if (gMatch[v] == -1){ //点v（位于右侧点集合）没有与之匹配的点，找到一条增广路				gMatch[u] = v;	//增广的取反操作（其实就是添加匹配）				gMatch[v] = u;				return true;			}			else if (Dfs(gMatch[v])){	//点v（位于右侧点集合），存在与之匹配的点gMatch[v]位于集合X中，								//则从gMatch[v]点继续向下增广				gMatch[u] = v;	//这里是增广的取反操作				gMatch[v] = u;				return true;			}		}	}	return false;}int Hungarian(int n){	int ans = 0;	memset(gMatch, -1, sizeof(gMatch));	for (int u = 0; u < n; u++){		if (gVertexInLeft[u] && gMatch[u] == -1){ //位于集合X中的，未匹配的点			memset(gVisited, false, sizeof(gVisited));			if (Dfs(u)){				ans++;			}		}	}	return ans;}

算法复杂度

可以看出匈牙利算法的时间复杂度为O(E*V)，对于稠密图使用DFS进行增广的匈牙利算法，对于稀疏图，采用BFS进行增广的匈牙利算法。

4. 最小点覆盖

点覆盖是图G中的一个点集合S，满足图G中的任意一条边e，都至少有一个顶点在集合S中。

二分图的最小覆盖是要求用最少的点（X集合和Y集合中的都可以），让每条边至少和其中一个点关联，需要的最少的点数。

二分图的最小点覆盖 = 二分图的最大匹配

首先，最小点覆盖集合S要求和每条边发生关联，那么就必须和最大匹配中的每条边发生关联，匹配中的边没有相交的顶点，因此S的大小至少要大于等于最大匹配数M， S >= M。

显然未匹配的每条边Bi都有且只有一个顶点和匹配中的某条边的某个顶点重合（反证法，若Bk的两个顶点都不和最大匹配的某个边的一个顶点重合，则边Bk必然可以加入到最大匹配中，这与最大匹配矛盾）；

图3

最大匹配中的一条边Ai，其至多只有一个顶点和未匹配的边的某顶点重合，如上图所示。若E1为最大匹配中的一条边，E2、E3为为匹配的边，且E1，E2相交于顶点5，E1，E3相交于顶点2，那么可以通过将E1从最大匹配中去除，加入E2，E3到最大匹配，可以使得最大匹配的边数增加，与最大匹配矛盾！

那么最大匹配中的任意一条边a，至多一个顶点和未匹配边相交，对于最大匹配的每条边Ai，选择Ai的一个和未匹配边有公共点的顶点加入到S，若Ai中没有顶点和未匹配边有公共点，随便选择一个顶点加入S，那么集合S的大小就等于最大匹配M的大小。

5. 最小边覆盖

是图G的边E的一个子集S，该集合S中的边能够覆盖G中所有顶点，最小边覆盖就是满足这个要求的所有边集中边数最少的一个。

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

设图G的顶点数为n，最大匹配为m，未匹配的点数为b，那么有 n = 2*m + b;

用最少的边覆盖所有点，每个边最多覆盖两个与之前不重复的顶点，贪心的思想，首先通过最少的边覆盖尽可能多的点，于是选择用最大匹配中的m个边，覆盖2*m个顶点，然后剩余顶点数为 n - 2*m，再通过未匹配边覆盖之，且每个未匹配边只能覆盖一个与之前不重复的点，于是最少的边数为 m + n - 2*m = n - m.

6. 最大独立点集

从顶点V集合中选取出最大的子集U, 使得U中的所有顶点之间没有边相连。可以证明，二分图的最大独立点集个数 = 顶点数 - 二分图最大匹配数

转载于:https://www.cnblogs.com/gtarcoder/p/4900171.html

你可能感兴趣的文章