图9 总结交错链方法的计算步骤如下: 1、任选初始的匹配图 2、利用树生长法寻找增广链。如找到一条增广链则转步骤3,如所有交错树上都无增广链, 则步骤终止,已找到最大匹配。 3、(调整)替换增广链上的粗线和细线,得到一个新的匹配图,然后转步骤1。 交错链方法的计算量是0(n2)。 最优匹配问题(亦称分配(派)问题) 假如我们进一步还知道了每个工人干各项工作的效率或产值,而要求找出使总的产值最大的 匹配方式,这在图论中称为最优问题,即图中每条线都有权与其相对应,要求找出使权和最大(或 最小)的匹配。 对交错链S,我们定义 (s)=∑o(e)+∑(-o(e') e为S上的粗线e'为S上的细线 其中O(e)表示线段e的权,称O(S)为S的长度,让lk表示在所有含K条线段的匹配中,使权 的和达到最大的匹配,进一步假如存在关于的增广链,则用Sx表示最短增广链,即 (S)=mn((S)S是的增广链 下面的定理是组合最优化中最基本的性质。 定理2,对l,若存在S,则有如下递推关系: k+1=14dSk,k=0,1,2, 据此定理,可知求解最优匹配的关键是寻求最短增广链S,然而求S又可化为在一个定向图 中,求两点的最短定向路问题,如求图1012 A B C D E 1 2 3 4 5 1 5 4 3 2 图 9 总结交错链方法的计算步骤如下： 1、任选初始的匹配图。 2、利用树生长法寻找增广链。如找到一条增广链则转步骤 3，如所有交错树上都无增广链， 则步骤终止，已找到最大匹配。 3、（调整）替换增广链上的粗线和细线，得到一个新的匹配图，然后转步骤 1。 交错链方法的计算量是 O(n2 )。 最优匹配问题（亦称分配（派）问题） 假如我们进一步还知道了每个工人干各项工作的效率或产值，而要求找出使总的产值最大的 匹配方式，这在图论中称为最优问题，即图中每条线都有权与其相对应，要求找出使权和最大（或 最小）的匹配。 对交错链 S，我们定义    ( ) ( ) ( ( )) s e e =  +  −  e 为 S 上的粗线 e  为 S 上的细线 其中  （e）表示线段 e 的权，称  （S）为 S 的长度，让 k I 表示在所有含 K 条线段的匹配中，使权 的和达到最大的匹配，进一步假如存在关于 k I 的增广链，则用 SK 表示最短增广链，即 ( ) min{ ( ) }   S S S I k k = 是 的增广链 下面的定理是组合最优化中最基本的性质。 定理 2，对 k I ，若存在 SK，则有如下递推关系： k k k 1 I I S + =  ， k = 0,1,2, 据此定理，可知求解最优匹配的关键是寻求最短增广链 k S ，然而求 k S 又可化为在一个定向图 中，求两点的最短定向路问题，如求图 10