匹配问题：匈牙利算法、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法

2023-05-16

图&网络系列博文：

【1】图与网络模型及方法：图与网络的基本概念

【2】图&网络模型应用—最短路径问题

【3】树：基本概念与最小生成树

【4】匹配问题：匈牙利算法、最优指派、相等子图

【5】Euler 图和 Hamilton 图

【6】计划评审方法和关键路线法【统筹方法】：广泛地用于系统分析和项目管理

【7】最小费用流及其求法：

【8】最大流问题

【9】钢管订购和运输问题

定义匈牙利算法最优分派问题

可行顶点标号、相等子图库恩—曼克莱斯 (Kuhn-Munkres) 算法

定义

若 M ⊂ E(G) ，∀ $\large e_i ,e_ j$ ∈ M ， $\large e_i$ 与 $\large e_ j$ 无公共端点（i ≠ j ），则称 M 为图 G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为 被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M '|>| M | 的对集 M ' ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。

若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件：

【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。

1935 年，霍尔(Hall)得到下面的许配定理：

【定理 3】 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是：

∀S ⊂ X ，则| N(S) | ≥| S |，其中 N(S) 是 S 中顶点的邻集。

由上述定理可以得出：

【推论 1】若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。所谓k 次正则图，即每顶点皆k 度的图。

由此推论得出下面的婚配定理：

【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。

人员分派问题等实际问题可以化成对集来解决。

解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。

匈牙利算法

把以上算法稍加修改就能够用来求二分图的最大完美对集。

最优分派问题

在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权 $\large w(x_i,y_ j)$ ≥ 0 ，表示 $\large x_{i}$ 做 $\large y_{j}$ 工作的效益，求加权图G 上的权最大的完美对集。解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。

可行顶点标号、相等子图

【定理 5】 $\large G_{l}$ 的完美对集即为G 的权最大的完美对集。

库恩—曼克莱斯 (Kuhn-Munkres) 算法