QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2392|回复: 0
打印 上一主题 下一主题

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

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-5-20 09:51 |只看该作者 |正序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    定义
    % r9 y. a# c, b若 M ⊂ E(G) ,∀  ∈ M ,   与  无公共端点(i ≠ j ),则称 M 为图 G 中的一个对集;M 中的一条边的两个端点叫做在对集 M 中相配;M 中的端点称为 被 M 许配;G 中每个顶点皆被 M 许配时,M 称为完美对集;G 中已无使| M '|>| M | 的对集 M ' ,则 M 称为最大对集;若G 中有一轨,其边交替地在对集 M 内外出现,则 称此轨为 M 的交错轨,交错轨的起止顶点都未被许配时,此交错轨称为可增广轨。! R0 a* p, B. ~, J, e9 I. f

    & k/ Y3 Y, v: }: B0 P- z1 p8 v- ~* `: _若把可增广轨上在 M 外的边纳入对集,把 M 内的边从对集中删除,则被许配的 顶点数增加 2,对集中的“对儿”增加一个。 1957 年,贝尔热(Berge)得到最大对集的充要条件:) W& R# P% {; a' ~0 Z' \; ?

    9 d" f, _3 G: |" u2 F【定理 2 】M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。
    4 i, t) D& t$ U: l/ b. u) `0 f* P7 s" E
    1935 年,霍尔(Hall)得到下面的许配定理:/ Z; ~- ^. Q7 F
    ( ]2 A0 f$ K2 W/ H+ E6 x5 Q0 r
    【定理 3】 G 为二分图, X 与Y 是顶点集的划分,G 中存在把 X 中顶点皆许配的对集的充要条件是:
    . H- x( `3 x! C- c7 U
    ; C0 J0 B' }1 {! R∀S ⊂ X ,则| N(S) | ≥| S |,其中 N(S) 是 S 中顶点的邻集。
    3 S3 X3 N9 a! j( I3 u" U7 M* T+ m+ t% G% l6 k3 z/ E
    由上述定理可以得出:, V; p; D$ s+ v5 U5 z8 v$ {

    4 S# I+ t, |) e( w" c1 Z【推论 1】若G 是k 次(k > 0) 正则 2 分图,则G 有完美对集。 所谓k 次正则图,即每顶点皆k 度的图。, s) L( k- Q$ `% n& ~2 q, g

    ) b. E7 p% I1 X" b! q, G- i由此推论得出下面的婚配定理:+ d4 c1 v5 A3 t8 |- L3 @

    , O1 ~# k5 A0 n/ L【定理 4 】每个姑娘都结识k (k ≥ 1) 位小伙子,每个小伙子都结识k 位姑娘,则每位 姑娘都能和她认识的一个小伙子结婚,并且每位小伙子也能和他认识的一个姑娘结婚。
    # ^2 L8 s5 ^( ]1 ?8 b3 C. a( I- P
    , h8 {8 e) p2 `* G. T" {1 r人员分派问题等实际问题可以化成对集来解决。
    0 f+ P0 F% [3 }8 |
    5 \( t4 H, E+ r* z5 K
    5 C: |* \$ n- ]
    / M, t" f1 R* ^' o; P/ q7 o解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。
    1 V( M$ G" r8 Q( N5 I& Z4 a( V) ^5 l# w* j' q- Z
    匈牙利算法
    8 y0 W; F0 a0 }# M# ]0 d- V+ t5 _8 K  W

    - X3 d8 ]# A8 f; o$ j把以上算法稍加修改就能够用来求二分图的最大完美对集。- f9 {3 ^1 z4 H! z

    3 N  k* M8 V0 V% s0 B. F最优分派问题7 B% @! ?8 M/ H' t+ p+ e
    在人员分派问题中,工作人员适合做的各项工作当中,效益未必一 致,我们需要制定一个分派方案,使公司总效益最大。 这个问题的数学模型是:在人员分派问题的模型中,图 G 的每边加了权   ≥ 0 ,表示  做  工作的效益,求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯(Kuhn-Munkres)算法。为此,我们要引入 可行顶点标号与相等子图的概念。
    . ]1 x. ]% Z$ T& N; `2 U9 Y
    , z: l5 [6 ?+ }' I" M可行顶点标号、相等子图
    0 s' b( V& G. x9 T
    6 h8 @7 a; i. U" U
    ! y# @) H+ B% S【定理 5】   的完美对集即为G 的权最大的完美对集。) |5 P! R0 L4 T2 r9 \* I( @4 V

    * s9 l4 ^+ g! P" C库恩—曼克莱斯 (Kuhn-Munkres) 算法
    + Q7 \! ?  p$ }. [+ v
    0 {8 X6 x; `2 g% O: |: D9 c7 Y' }
    ( M5 t! g) i) H————————————————# m; {  M) B  V4 X* A2 {  G
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! Z4 O$ u" B' D/ q6 W, R
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89785987: }: A( p7 P0 U. ^
    # b0 i  X) N7 E9 G6 |

    1 \0 j/ p% w2 f7 E4 r) F
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏1 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-21 11:22 , Processed in 0.375275 second(s), 52 queries .

    回顶部