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

浅夏110

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

' @) X+ J" R: k, N1 B- t  T若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的 顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件：

0 R+ v, M) y9 v, u0 h: c2 Y【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
' O0 o5 u2 b% v8 z  i
1935 年，霍尔(Hall)得到下面的许配定理：

# D" D0 t8 L0 t( j+ ^" W【定理 3】 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是：
8 I& d8 Y! `' ]: f/ {, C" ^+ s$ K# G
∀S ⊂ X ，则| N(S) | ≥| S |，其中 N(S) 是 S 中顶点的邻集。
% O' v2 i# s) O4 R  l1 V
( O0 ?3 I/ \, X2 N% u# c2 N# g' B由上述定理可以得出：
" u+ d4 r% C& v3 I# ~# {1 Z8 C
【推论 1】若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。 所谓k 次正则图，即每顶点皆k 度的图。
: Z0 n7 [5 T7 M* U: h% g
% H4 V; S/ F: h- g7 V4 A3 f9 f由此推论得出下面的婚配定理：

【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。
& v. F8 ]0 E% k6 a+ V
1 g2 |+ V2 o2 R# [5 N人员分派问题等实际问题可以化成对集来解决。
& K* K. X' ~, k* w3 o4 ^5 i# c
$ f$ G. H/ }# N

1 F* a/ C) b! A* j6 p' m2 S解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
6 V4 n. ^7 ^$ R  h8 Y! Q+ D
2 H9 }6 T3 L; x# f4 [9 ]匈牙利算法

" A& D* b% d$ n- I
把以上算法稍加修改就能够用来求二分图的最大完美对集。

) i' T1 @! y, r& V2 `最优分派问题
) d5 u' s4 Q) h0 x/ e% H在人员分派问题中，工作人员适合做的各项工作当中，效益未必一 致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权   ≥ 0 ，表示  做  工作的效益，求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。

可行顶点标号、相等子图
- Q& t# ^7 y4 c3 r# ~" K8 [. `! C: Q9 \2 _
  X& ^( m6 J( V! q- }0 s
9 {* X' |% D; B# @【定理 5】   的完美对集即为G 的权最大的完美对集。
8 o& y: V$ p& y$ N
库恩—曼克莱斯 (Kuhn-Munkres) 算法
% q1 A$ X' P3 I1 n

* W- t& x3 M( v( N  K————————————————
: ?/ r1 i3 E  \# @% i& S版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785987

  M  R$ @; J8 A& I