我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分图 >

什么叫匹配特性?

归档日期:06-27       文本归类:二分图      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部匹配一词单独拿出来是可以解释的!!!但是 把“匹配特性”连在一起 首要 要了解条件 是什么样的东西或物品之间的匹配

  (3) [无线) [计算机]给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

  无向图:无向图G是指非空有限集合VG,和VG中某些元素的无序对的集合EG,构成的二元组(VG,EG)。VG称为G的顶点集,其中的元素称为G的顶点。EG称为G的边集,其中的元素称为G的边。在不混淆的情况下,有时记V=VG,E=EG。如果V={v1,…,vn},那么E中的元素e与V中某两个元素构成的无序对(vi,vj)相对应,记e=vivj,或e=vjvi。在分析问题时,我们通常可以用小圆圈表示顶点,用小圆圈之的连线表示边。

  二分图:设G是一个图。如果存在VG的一个划分X,Y,使得G的任何一条边的一个端点在X中,另一个端点在Y中,则称G为二分图,记作G=(X,Y,E)。如果G中X的每个顶点都与Y的每个顶点相邻,则称G为完全二分图。

  设G=(V,E)是一个图, ,如果M不含环且任意两边都不相邻,则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。

  对于图G=(V,E),在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义 ,并称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果对一切,e∈E,w(e)=1,则G的最大权匹配就是G的最大匹配。

  设M是图G=(V,E)的一个匹配,vi∈V。若vi与M中的边相关联,则称vi是M饱和点,否则称vi为M非饱和点。

  设M是G的一个匹配,P是G的一条链。如果P的边交替地一条是M中的边,一条不是M中的边,则称P为M交错链。类似地,我们可以定义G的交错圈。易知,G的交错圈一定是偶圈。

  容易看出,设M是G的匹配,P是G中的M增广链、则M⊕P也是G的匹配,而且 。

  设有M个工人x1, x2, …, xm,和N项工作y1, y2, …, yn,规定每个工人至多做一项工作,而每项工作至多分配一名工人去做。由于种种原因,每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。

  对于1≤i≤m,1≤j≤n,当且仅当工人xi胜任工作yi时,G中有一条边xiyi,于是人员分配问题就成为在G中求一个最大匹配的问题。

  求最大匹配常用匈牙利算法,它的基本思想是:对于已知的匹配M,从X中的任一选定的M非饱和点出发,用标号法寻找M增广链。如果找到M增广链,则M就可以得到增广;否则从X中另一个M非饱和点出发,继续寻找M增广链。重复这个过程直到G中不存在增广链结束,此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法,因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。

  理解了这个算法,就不难写出人员分配问题的解答了。在给出程序之前,先做一些假设:

  为了简单起见,假设工人数等于工作数,即N=M,且N≤100,这里,N也可以看作是二分图的X和Y。

  数据从文件input.txt中读入,首先是N和E,下面E行每行两个数(I, J),表示工人I可以胜任工作J,即二分图中的边xiyj。

  结果输出到文件output.txt,第一行是最大匹配数s,下面s行每行两个数(I, J),表示分配工人I做工作J,即匹配边xiyj。

  对于上面的人员分配问题,如果还考虑到工人做工的效率,就可以提出所谓的分派问题:应该怎样分配才能使总的效率最大?

  同上一节,我们可以构造一个二分图G,如果把工人xi做工作yi的效率wij看作是G中边xiyi的权,则分派问题就相当于在赋权二分图G中求一个最大全匹配。

  由线性规划的知识,求二分图G的最大权匹配,只需在匈牙利算法的基础上少许改进即可。它的基本思想是,对二分图的顶点编号,然后根据编号构造一个新的二分图G’,最后把求G的最大权匹配转换为求G’的完美匹配。

  定理:设 是赋权图(权非负)的完全二分图 的一个完美匹配,这里 。如果存在一组 ,满足 ,并且对一切 ,均有 ,则 是 的最大权匹配。

  下面,给出求最大权匹配的程序。输入文件中首先是N和E,下面E行每行三个数(I, J, W),表示工人I做工作J的效率是W。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算法的时间复杂度也是O(n3)。

  任意图的最大匹配算法也是建立在找增广链的基础上的,只是任意图的增广链要比二分图难找得多。这个算法比较复杂,竞赛中也很少用到,因此,这里就不做详细介绍了。

本文链接:http://pikeducation.com/erfentu/429.html