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