最大流问题

最大流问题

以V为节点集,A为弧集,有向图G = ( V, A ).

L( i, j )是( i, j )的容量下界,U( i, j )是( i, j )的容量上界。节点 i 对应的权d(i)是顶点 i 的供需量。

二分图判定

二分图的判定问题比较少见,简单来说,就是对于给定的图,判断图是否为二分图。

可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同,不难发现,对于一个当且仅当每个连通分量都是二分图,因此我们只考虑无向连通图。

无向图 G 为二分图的充分必要条件:G 至少有两个顶点,且其所有回路的长度均为偶数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n;  //节点数
vector<int> G[N]; //G[i]表示i节点邻接的点
int color[N]; //color[i]=0,1,2 代表i节点不涂颜色、涂白色、涂黑色
//假设u是遍历时的第一个结点,则color[u]已经被初始化为1或2
bool bipartite(int u){ //判断无向图是否可二分
for(int i = 0; i < G[u].size(); i++){ //枚举结点
int v = G[u][i]; //相邻节点
if(color[v] == color[u]) //若两结点颜色相同,无法二分
return false;
if(!color[v]){ //若结点没涂颜色
color[v] = 3 - color[u]; //改变结点颜色,使v的颜色与u的颜色对立
if(!bipartite(v)) //若点v不满足二分图话,则无法二分
return false;
}
}
return true;
}

匈牙利算法

交替路

从一个未匹配点出发,依次经过 非匹配边、匹配边、非匹配边… 形成的路径。

增广路

定义:设 M 为二分图 G 已匹配边的集合,若 P 是图 G 中一条连通两个未匹配点的路径(起点在 X/Y 部,终点在 Y/X 部),且属 M 的边(匹配边)与不属 M 的边(非匹配边)在 P 上交替出现,则称 P 为相对 M 的一条增广路径。

由于增广路的第一条边是没有参与匹配的,第二条边参与了匹配,…,最后一条边没有参与匹配,并且起点和终点还没有被选择过,显然 P 有奇数条边。

简单来说,从一个未匹配点出发,走交替路,若途径另一未匹配点(除起点外),则这条交替路称为增广路。

如下图,左图中的一条增广路如右图所示,图中的匹配点均用红色标出:

avatar

增广路性质

  1. P 的长度必为奇数,第一条边和最后一条边都不属于 M,且两个端点分属两个集合,均未匹配。

  2. P 的非匹配边比匹配边多一条。

  3. P 经过取反操作可以得到一个更大的匹配 M’。

  4. M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。

增广路定理

由于增广路中间的匹配节点不存在其他相连的匹配边,因此交换增广路中的匹配边与非匹配边不会破坏匹配的性质。

由增广路性质可知,只要把增广路中的匹配边和非匹配边交换,交换后,图中的匹配边数目比原来多了 1 条。

故而,可以通过不停地找增广路来增加匹配中的匹配边和匹配点,找不到增广路时,即达到最大匹配,这就是增广路定理。

匈牙利树

匈牙利树一般由 DFS 构造(类似于 DFS 树),其是从一个未匹配点出发进行 DFS(必须走交替路),直到不能再扩展为止。

如下图,通过左侧的二分图,进行 DFS 可以得到右侧的树,但这棵树存在一叶结点为非匹配点(7号),而匈牙利树要求所有叶结点均为匹配点,故这棵树不是匈牙利树。

avatar

但若原图中不含 7 号结点,那么从 2 号结点出发就会得到一棵匈牙利树,如下图:

avatar

匈牙利算法流程

匈牙利算法是用增广路来求最大匹配的算法,在求最大匹配前,需要先用 DFS 或 BFS 找到增广路。

流程

  1. 从左边第 1 个点开始,挑选未匹配点进行搜索,寻找增广路
    1)若经过一个未匹配点,则寻找成功,更新路径信息,匹配边数 +1,停止搜索。
    2)若一直没有找到增广路,则不再从这个点开始搜索。事实上,此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去,而不影响结果。
  2. 由于找到增广路后需要沿着路径更新匹配,因此需要一个结构来记录路径上的点,DFS 版本通过函数调用隐式地使用一个栈,而 BFS 版本使用 pre 数组(前驱结点)。

性能比较

无论是使用 DFS 还是 BFS,两个版本的时间复杂度均为 O(V*E)。

DFS 的优点是思路清晰,代码量少,但性能不如 BFS;BFS 的优点是速度较快,但代码量大。

对于稀疏图,BFS 版本明显快于 DFS 版本,对于稠密图,两者不相上下,因而当图为稀疏图时,常选用 DFS 版本,当图为稠密图时,常选用 BFS 版本。

koning定理及推论

基本概念

k-正则图:各顶点的度均为 k 的无向简单图

最大匹配数:最大匹配的匹配边的数目

最大独立集数:选取最多的点集,使点集中任意两点均不相连

最小点覆盖数:选取最少的点集,使任意一条边都至少有一个端点在点集中

内容

  • 最大匹配数 = 最小点覆盖数
  • 最大独立集数 = 顶点数 - 最大匹配数

实现

1.最大匹配数/最小点覆盖数

DFS 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n, m;  //x、y中结点个数,下标从0开始
bool vis[N]; //vis[i]表示是否在交替路中
int link[N]; //存储连接点
vector<int> G[N]; //存边

bool dfs(int x){
for(int i = 0; i < G[x].size(); i++){ //对x的每个邻接点
int y = G[x][i];
if(!vis[y]){ //不在交替路中
vis[y] = true; //放入交替路
if(link[y] == -1 || dfs(link[y])){ //如果是未匹配点,说明交替路是增广路
link[y] = x; //交换路径
return true; //返回成功
}
}
}
return false; //不存在增广路,返回失败
}

int hungarian(){
int ans = 0; //记录最大匹配数
memset(vis, -1, sizeof(vis));
for(int i = 1; i <= n; i++){ //从左侧开始每个结点找一次增广路
memset(vis, false, sizeof(vis));
if(dfs(i)) //找到一条增广路,形成一个新匹配
ans++;
}
return ans;
}

int main(){
while(~scanf("%d%d", &n, &m)){
memset(link, -1, sizeof(link)); //全部初始化为未匹配点
for(int i = 0; i < N; i++)
G[i].clear();
while(m--){
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
printf("%d\n", hungarian()); //输出最大匹配数
}
return 0;
}

BFS 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int n,m;//左边点数,右边点数
int vis[N];//vis[i]表示是否在交替路中
int link[N];//存连接点
int pre[N];//存前驱结点
vector<int> G[N];//存边
queue<int> Q;
int hungarian(){
memset(vis,-1,sizeof(vis));
memset(pre,-1,sizeof(pre));
memset(link,-1,sizeof(link));

int ans=0;//记录最大匹配数
for(int i=1;i<=n;i++){
if(link[i]==-1){//若点未匹配
pre[i]=-1;//没有前驱
while(!Q.empty())//清空队列
Q.pop();

Q.push(i);
bool flag=false;
while(!Q.empty() && !flag){
int x=Q.front();
for(int j=0;j<G[x].size();j++){//对x的每个邻接点
if(!flag)//如果falg为真,则说明找到一未匹配点,不必继续下去
break;

int y=G[x][j];
if(vis[y]!=i){//不在交替路中
vis[y]=i;//存入交替路
Q.push(link[y]);//交换路径
if(link[y]>=0)//在已匹配点中
pre[link[y]]=x;
else {//找到未匹配点,交替路变增广路
flag=true;
int d=x;
int e=y;
while(d!=-1){//找到一个未匹配点,无法构成匈牙利树,让所有点不断的往回更新,重选下一个
int temp=link[d];
link[d]=e;
link[e]=d;
d=pre[d];
e=temp;
}
}
}
}
Q.pop();
}
if(link[i]!=-1)//统计最大匹配数
ans++;
}
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
while(m--){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
printf("%d\n", hungarian());//输出最大匹配数
}
return 0;
}

最大独立集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n,m;
bool vis[N];
int link[N];
bool G[N][N];
bool dfs(int x){
for(int y=1;y<=m;y++){
if(G[x][y]&&!vis[y]){
vis[y]=true;
if(link[y]==-1 || dfs(link[y])){
link[y]=x;
return true;
}
}
}
return false;
}
int hungarian(){
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){
memset(link,-1,sizeof(link));
memset(G,true,sizeof(G));

while(m--){
int x,y;
scanf("%d%d",&x,&y);
G[x][y]=false;//不满足条件则连一条边
}

int mate=hungarian();//最大匹配数
int res=n-mate;//最大独立集

printf("%d\n",res);
}
return 0;
}

经典应用——行列拆点建图

转载自:

https://blog.csdn.net/u011815404/article/details/87829705

图论-二分图

二分图

是图论中的一种特殊模型。若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集,并且任意边的两个端点都分属于两个集合,则称图G为一个为二分图。

其充要条件是:图中至少存在两个点,且图中所有回路的长度均为偶数。

avatar

当图中的顶点分为两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连时,此时是一特殊的二分图,称为完全二分图。

匹配

一个匹配即一个包含若干条边的集合,且其中任意两条边没有公共端点。如下图,图3的红边即为图2的一个匹配。

avatar

定义匹配点、匹配边、未匹配点、非匹配边,它们的含义非常显然。例如上图中 1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。

最大匹配

在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数。如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配(即一个图的某个匹配中,所有的顶点都是匹配点,就是一个完全匹配)。如果在左右两边加上源汇点后,图G等价于一个网络流,最大匹配问题可以转为最大流的问题。解决此问的匈牙利算法的本质就是寻找最大流的增广路径。

上图中,{1-7,2-5,3-6,4-8}就是一个最大匹配,也是一个完全匹配。

完全匹配一定是最大匹配,但是并非每个图都存在完全匹配。

简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,或者右点集中的每一个点都与左点集的一个点匹配。

完美匹配

对于一个二分图,左点集与右点集的点数相同,若存在一个匹配,包含左点集、右点集的所有顶点,则称为完美匹配。

简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,并且右点集中的每一个点都与左点集的一个点匹配。

{1-7,2-5,3-6,4-8}也是一个完美匹配。

最大匹配问题

举例来说,若存在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对,使得每对都互相喜欢?这就是完全匹配问题。而最多有多少互相喜欢的男孩/女孩可以配对?这就是最大匹配问题。

最优匹配

最优匹配又称为带权最大匹配,是指在带有权值边的二分图中,求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同,最优匹配也是一个完备匹配,即每个顶点都被匹配。如果个数不相等,可以通过补点加0边实现转化。一般使用KM算法解决该问题。

带权二分图的权值最大的完全匹配称为最佳匹配,要注意的是,二分图的最优匹配不一定是二分图的最大权匹配。

实质上最优匹配问题就是求边权和最大的最大匹配问题。

求解技巧:可以添加一些权值为 0 的边,使得最优匹配和最大权匹配统一起来。

最小覆盖

二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖:

①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联,二分图的最小顶点覆盖数=二分图的最大匹配数;

②最小路径覆盖也称为最小边覆盖,是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数;

最大独立集

最大独立集是指寻找一个点集,使得其中任意两点在图中无对应边。对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说 最大独立集=|V|-二分图的最大匹配数。

匈牙利算法—基本概念

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

最大匹配与最小点覆盖

最小点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖所有的边。

最小割定理:一个二分图中的最大匹配数等于这个图中的最小点覆盖数。

最小点集覆盖==最大匹配:在这里解释一下原因,首先,最小点集覆盖一定>=最大匹配,因为假设最大匹配为n,那么我们就得到了n条互不相邻的边,光覆盖这些边就要用到n个点。现在我们来思考为什么最小点集覆盖一定<=最大匹配。任何一种n个点的最小点集覆盖,一定可以转化成一个n的最大匹配。因为最小点集覆盖中的每个点都能找到至少一条只有一个端点在点集中的边(如果找不到则说明该点所有的边的另外一个端点都被覆盖,所以该点则没必要被覆盖,和它在最小点集覆盖中相矛盾),只要每个端点都选择一个这样的边,就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案。所以最大匹配至少为最小点集覆盖数,即最小点集覆盖一定<=最大匹配。综上,二者相等。

匈牙利算法

由增广路的性质,增广路中的匹配边总是比未匹配边多一条,所以如果我们放弃一条增广路中的匹配边,选取未匹配边作为匹配边,则匹配的数量就会增加。匈牙利算法就是在不断寻找增广路,如果找不到增广路,就说明达到了最大匹配。

参考资料:

https://www.cnblogs.com/shenben/p/5573788.html

https://blog.csdn.net/u011815404/article/details/84260940

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.