数学建模社区-数学中国
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
[打印本页]
作者:
浅夏110
时间:
2020-5-20 09:51
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
定义
0 K( n- \6 O3 s+ r; \
若 M ⊂ E(G) ，∀ ∈ M ， 与 无公共端点（i ≠ j ），则称 M 为图 G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为 被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M '|>| M | 的对集 M ' ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则 称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。
8 |4 W1 w6 ^- E) D) v' @ ?
: S2 _2 R! i( p( F. S
若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的 顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件：
$ M3 k+ R* T$ s+ C# h
; Y! i6 h6 E0 e
【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
) ^( X. Q+ L: o5 j1 H0 {" y' M# V6 E6 O
! }$ {5 o5 } H K3 R `
1935 年，霍尔(Hall)得到下面的许配定理：
4 }9 }9 G1 L- o a8 |- b L( l
# n- n9 U$ ~' \! H8 ?' h) `3 p
【定理 3】 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是：
& e$ H: z5 D& m/ x a
$ e& ]1 m9 L. k% U0 ^5 e
∀S ⊂ X ，则| N(S) | ≥| S |，其中 N(S) 是 S 中顶点的邻集。
5 a" H5 T/ d+ F3 v; Q1 a* _9 x! `
" C$ h5 U+ Y" [) x: [% W
由上述定理可以得出：
: F7 W3 x( U4 u7 e# j) e: P7 l- ] t9 t
( |: \# Z$ L p' q( T7 T+ Z
【推论 1】若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。 所谓k 次正则图，即每顶点皆k 度的图。
! |6 V9 N- z0 _$ c
: P3 u$ H! [6 t- B) V
由此推论得出下面的婚配定理：
5 P# g; \' F% F( `( C
3 E; u5 x8 z0 i# ^' Z
【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。
6 `* d3 S3 ?" A: t8 R% L6 J
. i) z% N, _" J6 z: t
人员分派问题等实际问题可以化成对集来解决。
* N" q) ]/ o$ T/ r" V! O
' q5 A+ u$ E q8 f- }" j Z, d0 ^
$ @4 A5 n |1 Q3 Z$ t8 Q: u, B; q
$ S8 \3 A# ]' i0 c" }+ \
解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
' i6 G/ K, o: }! u' }. @
3 l, S$ \1 c, r/ g( q" h
匈牙利算法
& ^) C+ ~/ ?; g! ~% W" Z8 Z/ {
; k+ I# s0 r& ^! t) |( [5 P' ]9 q
" m) j7 U% S# q
把以上算法稍加修改就能够用来求二分图的最大完美对集。
9 S+ y* G* R6 `, H* K9 \" G2 k3 p
B0 Y& ?5 E5 s ~2 v! l5 [ x
最优分派问题
* s$ T" ~+ y/ F1 W" }: n( _
在人员分派问题中，工作人员适合做的各项工作当中，效益未必一 致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权 ≥ 0 ，表示 做 工作的效益，求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。
, O2 S- T) e1 D" X& C8 y7 w
3 q I. j1 J" U! y/ @" U) `' v
可行顶点标号、相等子图
0 @- S1 d0 o7 Y$ i% S1 i9 S
: Y, B7 ~/ [$ K2 D: r9 K" t
7 L% [& {/ d2 @3 K# I2 M
【定理 5】 的完美对集即为G 的权最大的完美对集。
4 R% V4 ~5 H% U. d4 k- `, J
) Z9 _6 `0 T$ b3 m
库恩—曼克莱斯 (Kuhn-Munkres) 算法
4 X- |; e7 q2 N7 h
6 l# H! r' o: t# r3 @* P
; b! F, K* ]1 }- K
————————————————
9 Z# w- J6 Q( u% J
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 l0 X4 e$ M4 X* x
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785987
b% u7 M2 C) w3 |' O$ b- [
. l' [, H9 K, k
9 M1 N7 W8 N% U0 x' K; c1 X" F1 E
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
; k+ I# s0 r& ^! t) |( [5 P' ]9 q
: Y, B7 ~/ [$ K2 D: r9 K" t
6 l# H! r' o: t# r3 @* P