Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=U W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. 你能想到用数学归纳 ·奠基：U川=1，显然 法证明吗？ ·假设：U川<=|W|且1<=U川<k且满足Hall条件时均存在最大匹配 ·为什么这里需要采用“强”数学归纳法？ ·归纳：当U<=W|以及U|=k且满足Hall条件时 ·1,如果对U的任意子集S,IN(S)川>IS引。 ·2,如果有U的某个真子集S,IN(S)川=|S。 ·分别构造上述两种情况下的最大匹配 请注意：为什么我们 要区分这两种情形？• 奠基: |U|=1,显然 • 假设:|U|<=|W|且1<=|U|<k且满足Hall条件时均存在最大匹配 • 为什么这里需要采用“强”数学归纳法？ • 归纳：当|U|<=|W|以及|U|=k且满足Hall条件时 • 1，如果对U的任意子集S，|N(S)|>|S|。 • 2，如果有U的某个真子集S，|N(S)|=|S|。 • 分别构造上述两种情况下的最大匹配 你能想到用数学归纳 法证明吗？ 请注意：为什么我们 要区分这两种情形？