算法合集之《偶图的算法及应用》.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,偶图的算法及应用,南京师范大学附属中学孙方成,目录,匹配的概念,偶图的定义和判定,偶,图的最大匹配,偶图的最小覆盖问题,偶图的最佳匹配问题,小结,匹配的概念(1),匹配的概念(2),偶图的定义,偶图的判定,偶图的最大匹配,Edmonds,于,1965,年提出了解决偶图的最大匹配的匈牙利算法：,偶图的最小覆盖问题,一般图的最小覆盖问题是一个已被证明的,NPC,问题。换一句话说，一般图的最小覆盖问题，是没有有效算法的图论模型。所以，将一个实际问题抽象成最小覆盖问题，是没有任何意义和价值的。,但是，如果问题可以抽象成偶图的最小覆盖问题，结局就不一样了。由于偶图的特殊性，偶图的最小覆盖问题存在多项式算法。,最大匹配与最小覆盖的关系,在证明这个定理的过程中，要用到,Hall,婚姻定理,：,1931年,Knig,给出最大匹配与最小覆盖的关系定理如下：,偶图的最佳匹配问题,由于引入了权，所以最佳匹配不能直接套用最大匹配算法进行求解。同时，由于对最佳匹配的定义是建立在完全加权偶图的基础上的，对于不完全图，可以通过引入权为0（或是其他不影响最终结果的值），使得偶图称为完全偶图，从而使用最佳匹配算法来解决。,KM,算法前的准备,在介绍求最佳匹配的,KM,算法前，首先介绍一些相关的概念：,可以证明，,G,l,的完备匹配即为,G,的最佳匹配。,以此为基础，,1955年,Kuhn，1957,年,Munkres,给出修改顶标的方法，使新的相等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。,这就是,KM,算法。,KM,算法,一个例题,某公司有工作人员,x,1,x,2,x,n,，,他们去做工作,y,1,y,2,y,n,，,每个人都能做其中的几项工作，并且对每一项工作都有一个固定的效率。问能否找到一种合适的工作分配方案，使得总的效率最高。要求一个人只能参与一项工作，同时一项工作也必须由一个人独立完成。不要求所有的人都有工作。,一个实例,Y,1,Y,2,Y,3,Y,4,Y,5,X,1,3,5,5,4,1,X,2,2,2,0,2,2,X,3,2,4,4,1,0,X,4,0,1,1,0,0,X,5,1,2,1,3,3,若工人,x,完全不能参与工作,y，,则,w(x,y)=0,流程(1),首先，选取可行顶标,l(v),如下：,构造,G,l,，,并求其最大匹配：（其流程过长，此处略）,流程(2),其最终得到的最大匹配如图所示：,图中粗点划线构成最大匹配。,流程(3),G,l,中无完备匹配，故修改顶标。,流程(4),根据新的顶标构造,G,l,，,并求其上的一个完全匹配如图所示：,图中粗点划线给出了一个最佳匹配，其最大权为4241314。题目完成。,小结,偶图是一种特殊的图，所以它不但具备了信息量丰富这个图模型共有的优点，同时它也具备了大量一般图所不具备的内涵和算法优势。,偶图的结点分成两个部分，这就是它和自然界、数学界的对应关系，或者说匹配关系有着深刻的联系。因此，匹配的算法是所有偶图算法的核心。,如果能将实际问题，通过合理的抽象，变成两种事物之间的矛盾，则这种问题就可以抽象成偶图的模型。所以，偶图的模型有着广泛的应用。同时，偶图的算法有着高效实用的特点，所以也使通过偶图模型解决问题成为可能。,综上所述，我认为，偶图是一种高效的，有着广泛使用价值的模型。合理、有效的使用偶图模型，将大大提高编程及解决现实生活中实际问题的能力。,谢谢！,