三、二分图中的匹配1求最大匹配的算法利用标号法求网络最.pptVIP

三、二分图中的匹配 1.求最大匹配的算法 利用标号法求网络最大流。 对于给定二分图G(V1,V2)，构造相应的网络N(G)。 设G(V1,V2)是二分图, 构造一个网络N(V,E,C)又记为N(G), 它是一个带权有向图, 其中V=V1∪V2∪{s,t}, E={(s,x)|x?V1}∪{(y,t)|y?V2}∪{(x,y)|x?V1,y?V2, (x,y)?E}。 对任意x?V1, y?V2, 令csx=cyt=1, 对任意弧(x,y),x?V1,y ?V2, 令cxy=1, 这个网络的发点是s, 收点是t。 2.霍尔(Hall)定理 霍尔于 1935 年证明了一个著名的定理,先给出定义如下: 定义 8.13:图G的任意一个顶点子集A?V, 所有与A中顶点相邻的顶点全体, 称为A的邻集, 记为?(A)。 定理: 对于二分图G(V1,V2),若|V1|=|V2|, 则从V1到V2的完全匹配就是G的完美匹配。 对于二分图G(V1,V2),若|V1|=|V2|,如能找到V1到V2的完全匹配,就得到G的完美匹配. 但二分图不一定存在完全匹配 定理8.10(霍尔定理):设二分图G(V1,V2),G含有从V1到V2的完全匹配当且仅当对于任何A?V1,有|?(A)|≥|A|。 证明:(1)G含有从V1到V2的完全匹配，则对任何A?V1,有|?(A)|≥|A|。 (2)对任何A?V1,若有|?(A)|≥|A|,则G含有从V1到V2的完全匹配 定理8.10(霍尔定理):设二分图G(V1,V2),G含有从V1到V2的完全匹配当且仅当对于任何A?V1,有|?(A)|≥|A|。 例：设G为k正则二分图，则G存在完美匹配(k0)。 作业:P188 17,18,19,20 * * 定义8.14:若M是二分图G(V1,V2)的一个匹配, 使V1中每个顶点关于M饱和, 则称M是从V1到V2的完全匹配。 * * * * *