数学建模社区-数学中国
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
[打印本页]
作者:
浅夏110
时间:
2020-5-20 09:51
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
定义
% H* l/ S# D1 }: }* I
若 M ⊂ E(G) ，∀ ∈ M ， 与 无公共端点（i ≠ j ），则称 M 为图 G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为 被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M '|>| M | 的对集 M ' ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则 称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。
/ M2 O) f5 G/ P, c
- M& p$ g2 W, E3 L. o
若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的 顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件：
/ E* ]$ E( b' w% r% ]' |- |
1 [4 Y) S3 @/ z a8 V
【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
: n5 `3 G: |* Z* P. P; u& v
/ S# l5 A1 K6 c" J$ t
1935 年，霍尔(Hall)得到下面的许配定理：
4 d& a- K3 f. Q+ G/ Y) D
6 p: z9 N! B- Q# K- y" Y0 Q
【定理 3】 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是：
# K# o# ~9 C4 N5 j9 e5 f1 N$ l$ y
) J; p9 M" ~8 ~( H7 h" m! f6 I
∀S ⊂ X ，则| N(S) | ≥| S |，其中 N(S) 是 S 中顶点的邻集。
/ u. G) w& ~9 P9 _& y0 G
. ?# c% A* n2 X! d" |; l- z
由上述定理可以得出：
2 d+ f& l* @( ?; g+ R
% _. K- b. g+ k. n3 N; v% V2 Y6 i
【推论 1】若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。 所谓k 次正则图，即每顶点皆k 度的图。
! ]0 e% k5 o; L, W. X! y
. @4 x6 o P8 D3 I6 F
由此推论得出下面的婚配定理：
% Q, ]" a! y. N6 }# }1 ^9 ]3 S4 k
- u- e, L7 |4 p4 Z) S0 m
【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。
8 h$ E* q# X" U) b/ W$ A. @
. p$ q* F" v, s4 r. Q( k' Q5 P( j
人员分派问题等实际问题可以化成对集来解决。
3 `6 m/ K2 O* s* K4 ^& X
6 `8 p( O8 z- U' p1 I
& e8 ?7 n( a* F* i3 J
! V) ^0 f5 d2 b" Y9 [
解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
. \. H! M6 o8 s4 r8 ^' o0 u* |% W
' V5 y/ ?3 C j( `5 e
匈牙利算法
3 Z% h Y* T. I- M
! k: h) b5 h6 t) D6 x6 ?
7 m; X- E8 \% O5 P
把以上算法稍加修改就能够用来求二分图的最大完美对集。
7 n [" L3 i- R! F' M0 B+ Y: E) v
3 i2 G% Q8 }* N8 C8 w" ]
最优分派问题
# D$ @/ x, C) b9 H
在人员分派问题中，工作人员适合做的各项工作当中，效益未必一 致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权 ≥ 0 ，表示 做 工作的效益，求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。
# u3 a* x" U# P7 }+ U& S/ O- ^3 |
+ L4 j4 E/ G2 [1 b
可行顶点标号、相等子图
1 G4 v; g% w# m/ W
, c+ \& K' @; j. y
% p8 @; t2 M; ~* y" S; H( ?- C
【定理 5】 的完美对集即为G 的权最大的完美对集。
# q9 k* u4 R2 x- _. e" I) {
2 k! N' V$ L+ H3 T9 x/ @4 Z d8 q2 @
库恩—曼克莱斯 (Kuhn-Munkres) 算法
3 g+ f, Y# n8 k
3 D/ n2 F. O: H. L- E! X
+ R1 y& B9 t* f; O! Z9 V9 ~
————————————————
; U- v! n# b6 U8 N0 _& e5 y
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" x; H* J/ @# u
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785987
. q; o9 X. C. F4 m2 g" G! d0 Y2 ^
/ g: G0 K$ o; `
: ^) e. M4 Y5 B9 A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
& e8 ?7 n( a* F* i3 J
, c+ \& K' @; j. y