数学建模社区-数学中国
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
[打印本页]
作者:
浅夏110
时间:
2020-5-20 09:51
标题:
匹配问题： 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法
定义
$ i+ o3 z1 w h4 a* I% @
若 M ⊂ E(G) ，∀ ∈ M ， 与 无公共端点（i ≠ j ），则称 M 为图 G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为 被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M '|>| M | 的对集 M ' ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则 称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。
" |, j- U+ |" p. y8 i
$ B; l; L$ G S- J* _2 {
若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的 顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件：
+ b* o/ }3 j; H7 V- i3 \
9 u1 g; X; D! a$ R/ d1 C, C
【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
/ I: l+ D+ E) s0 ^! p# r& D
9 q8 ?2 S' `9 u# g1 }7 m
1935 年，霍尔(Hall)得到下面的许配定理：
$ z) T) b" P3 x/ n8 \9 h3 ]
' `% H: U% r2 i) A2 V# `* L
【定理 3】 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是：
' ] k+ q% j @( U7 s) u5 W
/ H0 g1 i; ~0 L2 \6 S/ N
∀S ⊂ X ，则| N(S) | ≥| S |，其中 N(S) 是 S 中顶点的邻集。
; j# {8 u/ g5 N1 p) p
' [0 m! N& V3 c8 i
由上述定理可以得出：
& u9 Q5 _' `: U/ Q- f$ U
4 x- ~/ t" e. ]1 H3 B
【推论 1】若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。 所谓k 次正则图，即每顶点皆k 度的图。
x( Z+ D. K+ R3 m$ l0 Q, t7 [) N
2 B' Q. z! d7 m7 X4 `' Y
由此推论得出下面的婚配定理：
# x) `: T& h6 a" M
* [, I7 f3 P% u# N0 a0 x
【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。
2 z, \2 v: G0 J) y: _. S
% @$ Y1 m& y3 m1 s: G, L8 X
人员分派问题等实际问题可以化成对集来解决。
+ L' Z4 H( k: J) b
/ G! F2 v. p2 e' @ ? Z6 z
6 U4 M' K: L3 x. B: O- p8 ]* A; y
3 V# H" J* I t' a7 ?
解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
: j9 k. }4 _8 N! M$ K* U
6 [; Y& E' K. E4 {: w) L
匈牙利算法
/ G! K$ y- m6 t5 h
2 _& Z" A# M. R( e: K
1 R2 ]- m/ H: Z( p0 w& L0 c3 @, }
把以上算法稍加修改就能够用来求二分图的最大完美对集。
9 S4 n$ j* M3 P& L
2 r0 \9 A8 d0 `% O Z1 f
最优分派问题
" R2 s" ?% F0 T1 X1 {
在人员分派问题中，工作人员适合做的各项工作当中，效益未必一 致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权 ≥ 0 ，表示 做 工作的效益，求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。
4 \: A/ J+ `5 {1 T+ q: |$ h( `
' e( n0 ?+ W4 _% ?0 K) y
可行顶点标号、相等子图
& v! B* `8 [9 s) d* j$ {
! h$ v, K5 c( g. I
2 C/ j R( D7 p4 g k+ J
【定理 5】 的完美对集即为G 的权最大的完美对集。
4 s4 Z0 T+ c9 ?7 H) I
0 s6 o u8 h4 \3 Z# |/ S+ k2 C
库恩—曼克莱斯 (Kuhn-Munkres) 算法
- U# N! S0 A, f$ ^
( |/ i; o9 V" j
; v/ h$ _) S7 h+ C, H3 \! Z
————————————————
d0 e8 X, ?# B) I3 ^( y" Y7 w0 X( e
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ ~: [- F1 m% A/ v9 P8 K
原文链接：https://blog.csdn.net/qq_29831163/article/details/89785987
. F' S2 n/ T7 U5 y3 R8 I" L. {7 \
7 A8 K0 t3 N# s+ K" N6 L
2 ~' H( T. ~5 u! T
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
6 U4 M' K: L3 x. B: O- p8 ]* A; y
