Page 221 - 数学建模算法与应用

第八章 图与网络模型及方法应用

1957 年，贝尔热得到最大对集的充要条件：
定理 2 M 是图 G 中的最大对集当且仅当 G 中无 M 可增广轨。
1935 年，霍尔 (Hall) 得到下面的许配定理：

定理 3 G 为二分图， X 与 Y 是顶点集的划分，G 中存在把 X 中顶点皆许配
的对集的充要条件是， ，则 其中 N(S) 是 S 中顶点的邻集。
由上述定理可以得出：
推论 1：若 G 是 k 次（k>0) 正则 2 分图，则 G 有完美对集。

所谓 k 次正则图，即每顶点皆 k 度的图。
由此推论得出下面的婚配定理：
定理 4 每个姑娘都结识 k(k ≥1) 位小伙子，每个小伙子都结识 k 位姑娘，则

每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个
姑娘结婚。
人员分派问题等实际问题可以化成对集来解决。
人员分派问题：工作人员 x1， x2 ，…， xn 去做 n 件工作 y1， y2 ，…，
yn ，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，

最多几人可以有适合的工作？
这个问题的数学模型是： G 是二分图，顶点集划分为 V(G)= XÈY ，

当且仅当 xi 适合做工作 y j 时
求 G 中的最大对集。
解决这个问题可以利用 1965 年埃德门兹 (Edmonds) 出的匈牙利算法。
匈牙利算法：
1. 从 G 中任意取定一个初始对集 M 。
2. 若 M 把 X 中的顶点皆许配，停止，M 即完美对集；否则取 X 中未被 M

许配的一顶点 u ，记 S={u}，T = F
3. 若 N(S)=T ，停止，无完美对集；否则取 yÎN(S) － T 。
4. 若 y 是被 M 许配的，设 ，转 3.。否则，取

可增广轨 P(u， y) ，令 转 2.。把以上算法稍加修改
就能够用来求二分图的最大完美对集。
最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益
未必一致，我们需要制定一个分派方案，使公司总效益最大。这个问题的数学模

211