图论 | 无向图 —— 二部图/二分图
123
·
目录
1.二部图概述
1.1.二部图概念
二部图又叫二分图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交子集 ，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分图，如下图所示的六个图全都是二分图：
1.2.二部图定理
【定理】
G=<V（顶点集合）,E（边集合）>为二部图的充要条件是G中的每一个圈的长度都是偶数
【证明】
2.匹配问题
【匹配定义】
设G=<V, E>是二分图，而且E是V1和V2的笛卡尔乘积子集。若M包含于E，而且M中任何两条边不相邻，则称M是G的一个匹配。匹配M中的边e称为杆。
- 最大匹配：具有边数量最多的匹配称为最大匹配（最大匹配不一定是完美匹配）
- 完美匹配：若|V1|=|V2|=|M|，则称M为完美匹配（完美匹配一定是最大匹配）
- 匹配点：Fig.3中的1,4,5和7（剩余的其它点即为未匹配点）
- 匹配边：Fig.3中的1-5和4-7
- 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路
- 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path），例如Fig.3中的一条增光路为Fig.5（图中匹配点用红色表示）
【匹配的特点】
- 增广路：非匹配边比匹配边多一条（因此，只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，Fig.3中的匹配边数目比原来多了 1 条）
- 增广路定理：通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配
2.1.匈牙利算法
2.1.1.匈牙利树
匈牙利树一般由 BFS （类似于BFS二叉树）构造。从一个未匹配点出发运行 BFS（必须走交替路），直到不能再扩展为止。例如，由Fig.6，可以得到如Fig.7的一棵 BFS 树。这棵树存在一个叶子节点为非匹配点（7 号），但是匈牙利树要求所有叶子节点均为匹配点，因此这不是一棵匈牙利树。如果原图中根本不含 7 号节点，那么从 2 号节点出发就会得到一棵匈牙利树。这种情况如Fig.8所示（顺便说一句，Fig.7 中根节点 2 到非匹配叶子节点 7 显然是一条增广路，沿这条增广路扩充后将得到一个完美匹配）
2.1.2.匈牙利算法
【算法步骤】
- 任取一匹配M (可以是空集或者只含有一条边的集合）
- 令S = {u|u∈V1∩u是M的未匹配点}，若S为空集，则M已经是最大匹配，退出
- 否则，S不为空，任取一非饱和点u0作为起点，从此起点走出几条交错路 Pil， Pi2,…
- 如果它们中有某条路P是增广路（即P的终点也是非饱和点），则令M=(M\P)U(P\M)(并且满足|M| (新)=|M| (旧)+1)，回到第3步
- 否则，如果它们中无一条是增广路（即终点全是饱和点），则令S=S\{u0}。如果S不为空，则回到第3步; 否则S为空，则M就是最大匹配，退出
【算法引例】：6位老师，6门课程 → 完美匹配，保证每个老师上的课是他会的
- 任取初始匹配M1={ (u2,v6) ，(u3,v1) } ，于是S1={u1，u4，u5，u6}，且S1≠∅，并非最大匹配
- 选择未匹配点u1作为起点，得到一条增广路为P1={(u1,v1)，(v1,u3)，(u3,v3)}（其中，红色节点为匹配点，粗黑边为匹配边）
- 得到新匹配M2=M1∪P1={(u1,v1)，(u2,v6)，(u3,v3)}，S2={u4，u5，u6}
- 选取非未匹配点u4作为起始点，得到增广路P2={(u4,v2)}，故M3=M2∪P2={(u1,v1)，(u2,v6)，(u3,v3)，(u4,v2)},S3={u5，u6}
- 选择未匹配点u5，增广路P3={(u5,v5)，(v3,u3)，(u3,v1)，(v1,u1)，(u1,v4)}，故M4={(u1,v4)，(u2,v6)，(u3,v3)，(u4,v2)}，S={u5，u6}
- 选择未匹配点u5，增广路P4={(u5,v5)}，故M5={(u1,v4)，(u2,v6)，(u3,v3)，(u4,v2)，(u5,v5)}，S={u6}
- 选择未匹配点u6，增广路P5={(u6，v1)} ，故M6={(u1,v4)，(u2,v6)，(u3,v3)，(u4,v2)，(u5,v5)，(u6,v1)}，S=∅
- 注意：最大匹配或完美匹配并不唯一
2.1.2.匈牙利算法代码
匈牙利算法有两种类型：基于DFS（深度有限搜索）和基于BFS（广度优先搜素）
import timeit
from collections import deque
#==============================================================================
# 匈牙利算法
# 参考博客：https://luzhijun.github.io/2016/10/10/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/
#==============================================================================
class HungarianAlgorithm(object):
def __init__(self,graph):
"""
@graph:图的矩阵表示
"""
self.graph=graph
self.n=len(graph)
def find(self,x):
for i in range(self.n):
if self.graph[x][i]==1 and not self.used[i]:
self.used[i]=1#放入交替路
if self.match[i]==-1 or self.find(self.match[i])==1:
self.match[i]=x
self.match[x]=i
print(x+1,'->',i+1)
return 1
return 0
def hungarian1(self):
"""递归形式
"""
self.match=[-1]*self.n#记录匹配情况
self.used=[False]*self.n#记录是否访问过
m=0
for i in range(self.n):
if self.match[i]==-1:
self.used=[False]*self.n
print('开始匹配:',i+1)
m+=self.find(i)
return m
def hungarian2(self):
"""循环形式
"""
match=[-1]*self.n#记录匹配情况
used=[-1]*self.n#记录是否访问过
Q=deque() #设置队列
ans=0
prev=[0]*self.n #代表上一节点
for i in range(self.n):
if match[i]==-1:
Q.clear()
Q.append(i)
prev[i]=-1#设i为出发点
flag=False #未找到增广路
while len(Q)>0 and not flag:
u=Q.popleft()
for j in range(self.n):
if not flag and self.graph[u][j]==1 and used[j]!=i:
used[j]=i
if match[j]!=-1:
Q.append(match[j])
prev[match[j]]=u#记录点的顺序
else:
flag=True
d=u
e=j
while(d!=-1):#将原匹配的边去掉加入原来不在匹配中的边
t=match[d]
match[d]=e
match[e]=d
d=prev[d]
e=t
print('mathch:',match)
print('prev:',prev)
print('deque',Q)
if match[i]!=-1:#新增匹配边
ans+=1
return ans
def do1():
graph=[(0,0,0,0,1,0,1,0),
(0,0,0,0,1,0,0,0),
(0,0,0,0,1,1,0,0),
(0,0,0,0,0,0,1,1),
(1,1,1,0,0,0,0,0),
(0,0,1,0,0,0,0,0),
(1,0,0,1,0,0,0,0),
(0,0,0,1,0,0,0,0)]
h=HungarianAlgorithm(graph)
print (h.hungarian1())
def do2():
graph=[(0,0,0,0,1,0,1,0),
(0,0,0,0,1,0,0,0),
(0,0,0,0,1,1,0,0),
(0,0,0,0,0,0,1,1),
(1,1,1,0,0,0,0,0),
(0,0,1,0,0,0,0,0),
(1,0,0,1,0,0,0,0),
(0,0,0,1,0,0,0,0)]
h=HungarianAlgorithm(graph)
print (h.hungarian2())2.2.KM算法
2.2.1.KM算法概念
二分图如果是没有权值的，求最大匹配，可以使用用匈牙利算法求最大匹配。如果带了权值，求最大或者最小权匹配（最佳匹配），则必须用KM算法。其实最大和最小权匹配都是一样的问题。只要会求最大匹配，如果要求最小权匹配，则将权值取相反数，再把结果取相反数，那么最小权匹配就求出来了。
KM算法 Kuhn-Munkras算法用来解决带权二分图最优匹配问题。基本思想是通过引入顶标，将最优权值匹配转化为最大匹配问题。
2.2.2.KM算法
【算法流程】
- 初始化可行顶标的值（各点的期望值）
- 用匈牙利算法寻找完备匹配
- 若未找到完备匹配则修改可行顶标的值
- 重复（2）（3）直到找到相等子图的完备匹配为止
【算法引例】：婚配问题
- 首先，每个女生会有一个期望值，就是与她有好感度的男生中最大的好感度，男生的期望值为0
- 接下来开始配对，从第一个女生开始，为她找对象：因为女1+男3=4+0=4，满足“男女两人的期望等于两人之间的好感度”规则。
- 给女2找对象，因为：女2+男3=3+0=3，满足要求，但是男3已经有对象了，因此给女2找对象失败。接下来需要修改期望值：将发生冲突的女1和女2的期望值降低1，而将冲突源男3的期望值增加1.如此一来女1和男3仍然满足匹配，与男1也满足匹配。女2与男1，男3均满足匹配。修改期望值之后，继续给女2找对象。此时女2-男1匹配，同时女1-男3也匹配。
- 接下来给女3匹配对象，因为女3+男3=6！=5，因此无法给女3找到匹配。所以让女3的权值减1，此时女3和男3匹配了，但是又和女1冲突了。便去寻找女1，但是对于女1而言可匹配的男1已经和女2 匹配了，于是再去寻找女2。
- 而此使对于女2而言，没有其他的边满足匹配规则了，因为现在的寻找路径为：女3->男3->女1->男1->女2，因此需要将左边的女1，2，3结点权值均减去1，将男1，3的权值均加1.
- 此时对于女1,2,3而言，男1,2,3均已经满足他们的期望值，也就是说现在已经将带权图转换为了无权图。因此接下来的男女匹配问题就可以使用匈牙利算法来实现，下图给出了解。
- 在这个问题中，冲突一共发生了三次，所以一共降低了3次效率值，但是每次降低的效率值都是最小的，所以完成的仍是最优匹配。这就是KM算法的整个过程。整体思路就是：每次都帮一个顶点匹配最大权重边，利用匈牙利算法完成最大匹配，最终完成的就是最优匹配。
2.2.3.KM算法代码
# 参考博客：https://blog.csdn.net/qq_37943488/article/details/78586048
# 并未转换成Python
# ==================================================================================
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
13
0- 0
已为社区贡献12条内容
所有评论(0)