引言

如果有4个申请读研的学生($s_i$)与4位导师($t_i$);假设每个导师最多只能招收一名学生,下图表示学生与所申请导师之间的关系;如何分配学生导师以尽可能满足学生的志愿

Demo

Demo

与此类问题类似的就是求二部图的最大匹配的问题

相关概念

匹配与最大匹配

设图G=<V,E>是一个无向图,如果存在边集M为E的子集,并且使得边集M中的所有边都没有公共结点,那么称边集M是无向图G的一个匹配;在一个无向图G中边数最多的匹配称为无向图的最大匹配

已经匹配过的边称为匹配边,未匹配的边叫自由边,匹配边的两个顶点叫饱和点,其他的点叫做自由点,如果V中所有的顶点都是饱和点,则称边集M是无向图的完美匹配

交错轨道,交错回路,增广路径

交错轨道:一条已匹配过的边和自由边组成的简单路径叫做交错轨道

交错回路:起点和终点相同的交错轨道

增广路径:起点和终点均自由的交错轨道

交错回路的边数一定为偶数

如果交错轨道p是边集M的增广路径,则p的边数一定为奇数,一定不会成为交错回路(因为起点和终点都要自由)

注意:如果边集M是无向图G的一个匹配,那么交错轨道p是边集M的一条增广路径,操作$M⊕p = (M \cup p)-(M \cap p)=(M-p) \cup (p-M)​$,(异或运算:相同的去掉,不同的加上;通过异或扩大匹配)说明$M⊕p​$是无向图的一个新匹配

两个定理

  1. 无向图G的匹配M是无向图G的最大匹配,当且仅当在G中不包含匹配M的增广路径
  2. 设M是无向图G的一个匹配,并且交错轨道p是匹配M的一条增广路径,那么$M⊕p$即是该无向图G的一个大小为$|M⊕p| = |M| + 1$的匹配

二部图

如果无向图G=<V,E>的结点集V可以分为两个子集X和Y,并且满足子集X与子集Y的交集为空集,子集X与子集Y的并集为结点集V,并且无向图G中任意一条边的两个端点,一个在X中,一个在Y中,那么就称图G是一个二部图或者偶图!

定理

(判定是否是二部图)无向图G是一个二部图,当且仅当该图没有长度为奇数的回路

注意:如果是二部图才可以利用下面所讲的匈牙利树算法来寻找这个二部图的最大匹配!

匈牙利算法

最大匹配的匈牙利算法步骤

  1. 从一个初始匹配M开始
  2. 每次找一条增广交错路径p
  3. 令M <- M⊕E(P),其中E(P)是p的边集
  4. 直到不存在增广交错路径为止

书上的描述:首先从一个空匹配M开始,在无向图G中寻找匹配M的一条增广路径p,然后执行M⊕p的操作,这实际上是反转增光路径p中边的作用,即将增广路径p中已经匹配过的边变成自由的边,同时将自由的边变成已经匹配过的边,从而可以得到一个新的匹配M,通过这样一种操作,可以使得这个新的匹配M比旧的匹配边数多1,重复以上操作,直到二部图G不包含匹配M的增广路径为止,此时宾士二部图G的最大匹配。

结论:如果在检索增广路径的过程中,检索到一颗匈牙利树,就可以永久地将其从二部图G中删去,而不会影响检索!

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*下面是构造二部图的最大匹配算法用到的数据类型和数据结构*/
NODE node[n]; /*结点的邻接表*/
int match[n]; /*与该元素对应结点匹配的结点编号*/
int path[n]; /*与该元素对应结点在交错轨道树上的父结点的编号*/
BOOL block[n]; /*该元素对应结点在交错轨道树上的阻塞标志*/
typedef struct qnode { /*广度优先搜索队列元素*/
int v; /*结点的编号*/
int tag; /*结点在交错轨道树上的作用标记*/
struct qnode *next; /*下一个待搜索的元素*/
} QNODE;
typedef struct { /*搜索队列*/
QNODE *head; /*队列的头指针*/
QNODE *tair; /*队列的尾指针*/
} QNODE;

bipartite_match(NODE node[], int match[], int n1, int n)
{
int root;
int i;
int j;
int t;
int path[n];
BOOL block[n], flag = TRUE;
for(i = 0; i < n; i++) /*匹配M初始化为空集*/
match[i] = -1;
while(flag)
{
for(root = 0; root < n1; root++) /*检索自由的xvertex结点*/
if(match[r] == -1)
break;
if(r >= n1)
break; /*如果不存在自由的xvertex结点,就退出循环*/
for(i = n1; i < n; i++)
if(match[r] == -1)
break;
if(r >= n)
break;
if(!(hungbfs(r, t, node, match, path, block, n)))
{
for(i = 0; i < n; i++) /*删除匈牙利树*/
{
if(block[i])
{
v = i;
delete_edge(v, path[v]);
while(path[v] != -1)
{
v = path[v];
delete_edge(v, path[v]);
}
}
}
}
else{ /*反转增广路径边的作用*/
while((t != 1) && (path[t] != -1))
{
match[t] = path[t];
match[path[t]] = t;
t = path[path[t]];
}
}
}
}

BOOL hungbfs(int r, int &t, NODE node[], int match[], int path[], BOOL block[], int n)
{
int i;
int j;
int v;
int w;
int tag;
BOOL flag1;
BOOL flag = FALSE, *a = new BOOL[n];
NODE *p = node[r].next;
QNODE *p1;
QUEUE queue;
initial_Q(queue); /*初始化广度优先搜索队列*/
for(i = 0; i < n; i++) /*初始化*/
{
/* code */
a[i] = FALSE;
block[i] = FALSE;
path[i] = -1;
}
a[root] = TRUE;
while(p != NULL) /*生成树的第一层结点*/
{
p1 = new NODE;
p1->v = p->v;
p1->tag = 0;
path[p->v] = root;
a[p->v] = TRUE;
append_Q[queue, p1];
p = p->next;
}
while(!empty(queue)){
/* code */
p1 = delete_Q(queue; /*取下搜索队列中的队首元素*/
w = p1->v; /*此元素的结点编号保存在变量w中*/
tag = p1->tag; /*此元素的结点标志保存在变量tag中*/
delete p1;
if(!flag)
{
if(tag == 0) /*tag等于0时的处理*/
{
if(match[w] == -1) /*如果结点w是自由的结点,那么存在着增广路径*/
{
flag = TRUE;
t = w; /*结点t为增广路径的端点*/
}
else
{
v = match[w];
p1 = new NODE;
p1->v = v;
p1->tag = 1;
a[v] = TRUE;
append_Q[queue, p1];
path[v] = w;
}
}
else /*tag等于1时的处理*/
{
p = node[w].next;
flag1 = FALSE;
while(p != NULL){
v = p->v;
if(!a[v])
{
p1 = new NODE;
P1->v = v;
a[v] = TRUE;
p1->tag = 0;
path[v] = w;
append_Q[queue, p1];
flag1 = TRUE;
}
p = p->next;
}
if(!flag1)
block[w] = TRUE;
}
}
}
return flag;
}