复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）28/30

V 1 1 2 4 4 y4 y. 图8.13 E’={(s,x)x∈Vn3U{(y,t)yeV23U{(x2y)xeV12y∈ V2,(x2y)∈E} 对任意xeV1,y∈V2,令c3x=c=1,对任意弧 (x,y),x∈V12yev2,令c3y=1,这个网络的发点是 收点是to

三、二分图中的匹配 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

U1 的定理,先给出 集AcV所有 3 u2 A的邻集,记 U2 定义8.14:若M是二分图 G(V1,V2)的一个匹配,使V1中 每个顶点关于M饱和,则称M 是从V到V2的完全匹配。 v5

2.霍尔(Hall)定理 霍尔于 1935 年证明了一个著名的定理,先给出 定义如下: 定义 8.13:图G的任意一个顶点子集AV, 所有 与A中顶点相邻的顶点全体, 称为A的邻集, 记 为(A)。 定 义 8 . 1 4 : 若 M 是二分图 G(V1 ,V2 )的一个匹配, 使V1中 每个顶点关于M饱和, 则称M 是从V1到V2的完全匹配

定理:对于二分图G1,V2若V=V2,则 从V到V2的完全匹配就是G的完美匹配。 对于二分图G1,V2若V=V2,如能找到 V到V2的完全匹配就得到G的完美匹配 但二分图不一定存在完全匹配

定理: 对于二分图G(V1 ,V2 ),若|V1 |=|V2 |, 则 从V1到V2的完全匹配就是G的完美匹配。 对于二分图G(V1 ,V2 ),若|V1 |=|V2 |,如能找到 V1到V2的完全匹配,就得到G的完美匹配. 但二分图不一定存在完全匹配

定理810(霍尔定理设二分图G(V1V2),G 含有从V到V2的完全匹配当且仅当对于 任何AcV1,有(A)≥A 证明:1)G含有从v1到V2的完全匹配,则 对任何AcV1,有r(A)A (2)对任何AcV1,若有(A)A,则G含有 从1到V2的完全匹配

定理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的完全匹配

定理810(霍尔定理设二分图G(V1V2),G 含有从V到V2的完全匹配当且仅当对于 任何AcV1,有(A)≥A 例:设G为k正则二分图,则G存在完美 匹配(k>0)

定理8.10(霍尔定理):设二分图G(V1 ,V2 ),G 含有从V1到V2的完全匹配当且仅当对于 任何AV1 ,有|(A)|≥|A|。 例：设G为k正则二分图，则G存在完美 匹配(k>0)

作业:P18817,18,19,20

作业:P188 17,18,19,20