- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36312 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13854
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
定义+ V, p, R3 o! H) u1 m. u, i
若 M ⊂ E(G) ,∀ ∈ M , 与 无公共端点(i ≠ j ),则称 M 为图 G 中的一个对集;M 中的一条边的两个端点叫做在对集 M 中相配;M 中的端点称为 被 M 许配;G 中每个顶点皆被 M 许配时,M 称为完美对集;G 中已无使| M '|>| M | 的对集 M ' ,则 M 称为最大对集;若G 中有一轨,其边交替地在对集 M 内外出现,则 称此轨为 M 的交错轨,交错轨的起止顶点都未被许配时,此交错轨称为可增广轨。
3 Z3 g. y" P9 a! `9 }% D
0 R/ c5 j8 o; \+ J若把可增广轨上在 M 外的边纳入对集,把 M 内的边从对集中删除,则被许配的 顶点数增加 2,对集中的“对儿”增加一个。 1957 年,贝尔热(Berge)得到最大对集的充要条件:
; Y; E5 T5 ?. r$ u3 [
1 t- r$ w/ K/ {; ?" i【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
- b. B+ U( |; H: [% M( _( C% n& B" G D3 n* X6 H% F
1935 年,霍尔(Hall)得到下面的许配定理:, T/ u! q* s4 V& k; V; A# C
3 e) y2 n" Z v" V, e: ]& `. h【定理 3】 G 为二分图, X 与Y 是顶点集的划分,G 中存在把 X 中顶点皆许配的对集的充要条件是:
d& N0 J( P" P% Q
6 |1 {/ `* q4 z0 Y9 K∀S ⊂ X ,则| N(S) | ≥| S |,其中 N(S) 是 S 中顶点的邻集。
& P" C3 o* T+ [& d
0 L7 G) A& w" |由上述定理可以得出:
" |+ `2 a2 p/ X. O6 R- N8 Q
& K# {) C# r: \- I% x) O【推论 1】若G 是k 次(k > 0) 正则 2 分图,则G 有完美对集。 所谓k 次正则图,即每顶点皆k 度的图。
" s U5 b1 I u/ |" g2 H' l& Y. w: I% n+ U B6 u5 {# @/ e0 c9 X
由此推论得出下面的婚配定理:: J& Q' S0 S/ N+ E
+ r1 f ]' u4 T, A- S2 l【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子,每个小伙子都结识k 位姑娘,则每位 姑娘都能和她认识的一个小伙子结婚,并且每位小伙子也能和他认识的一个姑娘结婚。6 ^8 C: m& |, Y' i9 }; C' X- J* c
* M, B: Y* t! C7 r9 s5 s) z人员分派问题等实际问题可以化成对集来解决。# C% J( L( i3 e: K7 V- v; ^
- P! q& H( e) w- R) i![]()
# e8 o7 `+ |5 M- _. I& _0 [- x
$ Z! N3 [- W+ A4 Z解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。; t7 c$ w0 T2 n) A# z. `
1 l4 V: c. n* z/ v! \
匈牙利算法4 I& n8 P6 o' V0 Z
![]()
. @" ?) X3 Q/ D% s g ~* Y+ N: ]# h; p: n8 |2 ~
把以上算法稍加修改就能够用来求二分图的最大完美对集。8 k! c4 T# s p
9 E* u5 p! L, D* \7 _( T9 a3 I+ l7 q$ d最优分派问题
9 d6 q7 B. `/ H$ L在人员分派问题中,工作人员适合做的各项工作当中,效益未必一 致,我们需要制定一个分派方案,使公司总效益最大。 这个问题的数学模型是:在人员分派问题的模型中,图 G 的每边加了权 ≥ 0 ,表示 做 工作的效益,求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯(Kuhn-Munkres)算法。为此,我们要引入 可行顶点标号与相等子图的概念。; j0 V$ G9 K: ?* \. l7 S0 k0 F
- p6 J- I' q+ S2 N4 K" V. {& ^可行顶点标号、相等子图
" f$ [$ @; x! l+ }' A( `+ r8 g+ s/ z 8 u) V' u* u& z/ F/ o @
0 k5 L8 a1 Y: z; l& C
【定理 5】 的完美对集即为G 的权最大的完美对集。# b. t6 l; n& W. Y/ x
: {3 A: v- F4 A4 v
库恩—曼克莱斯 (Kuhn-Munkres) 算法* {3 m3 a4 @) |: B) J/ m) k6 Y5 T
![]()
3 Y5 o2 f2 N9 W! x; v, i5 {) d6 j A6 ?) a) y z3 _3 T
————————————————
* \9 E2 o5 M# ], e版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! L7 u" Y) A' D4 S4 A; w( Y E% J
原文链接:https://blog.csdn.net/qq_29831163/article/details/897859877 M3 G! U) R+ c; p7 z# T
6 E, f! v+ A; {
9 R$ n; Z, r- |+ X+ t5 } |
zan
|