信息学竞赛算法分析与设计.PPT

上传人:国*** 文档编号:777443 上传时间:2018-10-31 格式:PPT 页数:54 大小:543.50KB
下载 相关 举报
信息学竞赛算法分析与设计.PPT_第1页
第1页 / 共54页
信息学竞赛算法分析与设计.PPT_第2页
第2页 / 共54页
信息学竞赛算法分析与设计.PPT_第3页
第3页 / 共54页
信息学竞赛算法分析与设计.PPT_第4页
第4页 / 共54页
信息学竞赛算法分析与设计.PPT_第5页
第5页 / 共54页
点击查看更多>>
资源描述

1、信息学竞赛 算法分析与设计1本节课程内容二分图、匹配二分图、匹配(bipartite graph、 matching)l 匈 牙 利 算 法 l Kuhn-Munkras算法2二分图的概念l 二分图又称作二部图,是图论中的一种特殊模型。l 设 G=(V,R)是一个无向图。如顶点集 V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G为二分图。1122334453最大匹配l 给定一个二分图 G,在 G的一个子图 M中,M的边集 E中的任意两条边都不依附于同一个顶点,则称 M是一个匹配。l 选择这样的边数最大的子集称为图的最大匹配问题 (maximal mat

2、ching problem)l 如果一个匹配子图中,图中的每个顶点都和匹配子图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。4匈牙利算法l 求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。l 增广路的定义 (也称增广轨或交错轨 ):若 P是图 G中一条连通两个未匹配顶点的路径,并且属 M的边和不属 M的边 (即已匹配和待匹配的边 )在 P上交替出现,则称 P为相对于 M的一条增广路径。5匈牙利算法l 由增广路的定义可以推出下述三个结论: 1. P的路径长度必定为奇数,第一条边和最后一条边都

3、不属于 M。 2. P经过取反操作可以得到一个更大的匹配 M。 3. M为 G的最大匹配当且仅当不存在相对于 M的增广路径。6匈牙利算法l 用增广路求最大匹配 (称作匈牙利算法,匈牙利数学家 Edmonds于 1965年提出 )l 算法轮廓:l (1)置 M为空l (2)找出一条增广路径 P,通过取反操作获得更大的匹配 M代替 Ml (3)重复 (2)操作直到找不出增广路径为止7任给初始匹配找 xV1为非饱和点S=x,T=取 yN(s)-T存在一条从 x到 y的 M可增广路 P, M: =MP无法继续匹配,停止存在边 y,u MS: =SuT: =T yM饱和 V1N(s)=T?YNYNY已经

4、饱和 YN停止, M为最大匹配8设 G是具有二部划分 (V1,V2)的二分图 .(1)任给初始匹配 M;(2)若 M饱和 V1则结束 .否则转 (3);(3)在 V1中找一非 M饱和点 x,置 S=x,T=;(4)若 N(S)=T,则停止 ,否则任选一点 yN(S)-T;(5)若 y为 M饱和点转 (6),否则作求一条从 x到 y的 M可增广路 P,置 M=MP,转 (2)(6)由于 y是 M饱和点 ,故 M中有一边 y,u,置S=Su,T=Ty,转 (4).匈牙利算法步骤9匈牙利算法程序清单:#include#includebool g201201;int n,m,ans;bool b201;int link201;10

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。