二分图匹配基于匈牙利算法和KM算法3页.doc

上传人:晟*** 文档编号:6266322 上传时间:2021-08-27 格式:DOC 页数:3 大小:18.50KB
下载 相关 举报
二分图匹配基于匈牙利算法和KM算法3页.doc_第1页
第1页 / 共3页
二分图匹配基于匈牙利算法和KM算法3页.doc_第2页
第2页 / 共3页
二分图匹配基于匈牙利算法和KM算法3页.doc_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述

二分图匹配-基于匈牙利算法和KM算法2007-09-19 16:54设G=(V,R)是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。 v给定一个二分图G,在G的一个子图M中,M的边集E中的任意两条边都不依附于同一个顶点,则称M是一个匹配。v选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)v如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。最大匹配在实际中有广泛的用处,求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。匈牙利算法是求解最大匹配的有效算法,该算法用到了增广路的定义(也称增广轨或交错轨):若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。由增广路径的定义可

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

当前位置:首页 > 实用文档资料库 > 公文范文

Copyright © 2018-2021 Wenke99.com All rights reserved

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

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

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