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