能多的人分配到适应的工作岗位上。 例如有5个工人:A、B、C、D、E:5项工作1,2,3,4,5,各工人与各工作之间的适应关系 如图5所示。图中有线段相连表示适应。例如A适应于1和2,问最多能同时安排几个人的工作? 图5 图6 图7 从图上看,是要求利用线段来将图中的端点一一配对,且希望配得对数越多越好。这就是图论 中最大匹配问题。可见,所谓匹配就是无公共顶点的边所成集合。 首先,通过直觉观察,求出一个较好的初始匹配方案。在图中我们用粗线段表出,如图6所示。 这时已连上粗线段的点称为已盖点,尚未连粗线的点称为未盖点,图上的一条路,若路上的线段粗 细交错,则称其为交错链,如图7所示。称连接两个未盖点的交错链为增广链。对于增广链,细线 段比粗线段多一条。对给定的匹配方案I,假若存在一增广链S,那么只要把路S上的细线和粗线交 换一下,便可得到多安排一个人的新匹配方案I。通常用下述符号表示上述调整运算 T=lS=lUS/InS) 图论中有下列基本事实 定理1,一个匹配为最大匹配的充要条件是不存在关于它的增广链 如何寻找增广链?采用“树生长法”(或称标号法),以图6为例,开始任取一未盖点为树根, 如D,从树根沿着细线生长,接着从树梢岀发沿着粗线往外生长,这样交错的沿着细线粗线继续从 树梢往外延伸,直到不能再生长(如图8) 图8 我们称图(8)是以D为根的交错树,在树的生长过程中,一旦发现除树根外,另一未盖点被 长到树上,过程就可中止。这时树上连结两个未盖点的那条路,便是一条增广链。图8中D与⑤之 间就是一条增广链,沿着它们调整后,可得匹配如图911 能多的人分配到适应的工作岗位上。 例如有 5 个工人：A、B、C、D、E；5 项工作 1，2，3，4，5，各工人与各工作之间的适应关系 如图 5 所示。图中有线段相连表示适应。例如 A 适应于 1 和 2，问最多能同时安排几个人的工作？ A B C D E 1 2 3 4 5 A B C D E 1 2 3 4 5 图 5 图 6 图 7 从图上看，是要求利用线段来将图中的端点一一配对，且希望配得对数越多越好。这就是图论 中最大匹配问题。可见，所谓匹配就是无公共顶点的边所成集合。 首先，通过直觉观察，求出一个较好的初始匹配方案。在图中我们用粗线段表出，如图 6 所示。 这时已连上粗线段的点称为已盖点，尚未连粗线的点称为未盖点，图上的一条路，若路上的线段粗 细交错，则称其为交错链，如图 7 所示。称连接两个未盖点的交错链为增广链。对于增广链，细线 段比粗线段多一条。对给定的匹配方案 I，假若存在一增广链 S，那么只要把路 S 上的细线和粗线交 换一下，便可得到多安排一个人的新匹配方案 I 。通常用下述符号表示上述调整运算： I I S I S I S  =  =   /( ) 图论中有下列基本事实： 定理 1，一个匹配为最大匹配的充要条件是不存在关于它的增广链。 如何寻找增广链？采用“树生长法”（或称标号法），以图 6 为例，开始任取一未盖点为树根， 如 D，从树根沿着细线生长，接着从树梢出发沿着粗线往外生长，这样交错的沿着细线粗线继续从 树梢往外延伸，直到不能再生长（如图 8） D 1 2 A B 3 4 C E 5 1 5 4 3 2 图 8 我们称图（8）是以 D 为根的交错树，在树的生长过程中，一旦发现除树根外，另一未盖点被 长到树上，过程就可中止。这时树上连结两个未盖点的那条路，便是一条增广链。图 8 中 D 与⑤之 间就是一条增广链，沿着它们调整后，可得匹配如图 9