Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us 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条件时均存在取八心e ·为什么这里需要采用“强”数学归纳法？ ·归纳：当IU<=|WI以及U川=k且满足Hal条件时 ·从U任取一个u,从N(u)中任取一个w,构造H:G-{u,w:H满足Hal条件吗？ ·需要分两种情况来讨论： ·1,如果对U的任意真子集S,IN(S)川>ISl。H是否满足Hall条件 ·2,如果有U的某个真子集s,IN(S)川=|Sl。H是否满足Hall条件 ·如果满足Ha条件，找到这个最大匹配'，加上uw,就是归纳结论• 奠基: |U|=1,显然 • 假设:|U|<=|W|且1<=|U|<k且满足Hall条件时均存在最大匹配 • 为什么这里需要采用“强”数学归纳法？ • 归纳：当|U|<=|W|以及|U|=k且满足Hall条件时 • 从U任取一个u，从N(u)中任取一个w，构造H:G-{u,w}：H满足Hall条件吗? • 需要分两种情况来讨论： • 1，如果对U的任意真子集S，|N(S)|>|S|。H是否满足Hall条件 • 2，如果有U的某个真子集S，|N(S)|=|S|。H是否满足Hall条件 • 如果满足Hall条件，找到这个最大匹配M’，加上uw，就是归纳结论 你能想到用数学归纳 法证明吗？