大匹配算法匈牙利算法ppt课件_第1页
大匹配算法匈牙利算法ppt课件_第2页
大匹配算法匈牙利算法ppt课件_第3页
大匹配算法匈牙利算法ppt课件_第4页
大匹配算法匈牙利算法ppt课件_第5页
已阅读5页，还剩12页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、二分图的最大匹配RCA二分图n二分图是一种特殊的图n对于无向图G=(V,E)，假设V可以分为两个互不相交的子集，并且图中的每条边所依托的两点都属于不同的子集，那么图G那么称为一个二分图544332211最大匹配n给定一个二分图G，在G的一个子图的边集中的恣意两条边都不依托于同一个顶点，那么称此子图是一个匹配。n选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)n假设一个匹配中，图中的每个顶点都和图中某条边相关联，那么称此匹配为完全匹配，也称作完备匹配。增广路n对于右图的边，假设我们一开场仅有曾经完成的匹配1-1，4-3。n那么当我们对于2，可以让曾

2、经有的匹配做下修正，即4-4，1-3，空出来1和2进展匹配，这样沿着已有匹配去寻觅到的新匹配叫增广路。544332211匈牙利算法n1.对于左边的每个点，看看右边有没有增广路，假设有，那么进展增广，没有就不添加新的匹配。n2.当对最后一个点做完增广路以后，整个图就构成了一个最大匹配。二分图的最小覆盖数n棋盘上有N个点，每次可以拿走一行或者一列。n问最少多少次可以把棋盘上的一切点都拿走npoj3041二分图的最小覆盖数n将行作为左边的点，列作为右边的点，原图中的每个点构成一条边，将代表其行和列的点衔接起来。n对曾经建好的图求最大匹配Konig定理n最大匹配数=最小覆盖数二分图的最大独立数n一张残

3、缺的棋盘，用1*2的矩形去覆盖它，要求矩形不相互重叠。n求矩形最多可以放多少个。二分图的最大独立数n将棋盘染成黑白相间，黑色方格作为左边的点，白色方格作为右边的点，相邻的黑白方格中间连一条边。n对曾经建好的图求最大匹配二分图的最大独立数n最大独立数=最大匹配数最小途径覆盖n一张图n个点，给定某些点之间可以用线连起来。n问最少画多少笔才干将一切的点全部盖住npoj1422最小途径覆盖n将n个点拆成2n个点，如1号变为1和1，1代表出边，1代表进边。对于每个结点，将与其相临的边连出来。n对曾经连好的图求最大匹配数最小途径覆盖n最小途径覆盖数=顶点数n-最大匹配数nNkoj n1684 coursesn1465 Taxi Cab Schemen1681 Girls and boysn1070 信和信封的问题npojn2239 Selecting Coursesn1422 Air Raid 最小途径覆盖n1325 Machine Schedulen1719 Shooting Contestn2594 Treasure Explorationn2195 Going Home带权二分图(km算法)n2446 Chessboardn1904 Kings Questn3342 Party at H

人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论