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