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条件时均存在取八心e ·归纳：当k=U川以及U|<=WI且满足Hall条件时 ·从U任取一个u,从N(u)中任取一个w,构造H:G-{u,w:H满足Ha条件吗？ ·如果对U的任意真子集S,IN(S川>ISL,是成立的。否则？ W ·Case1:对所有U的真子集S,均有|N(S)川>SI ·取U中某个元素u,取u的相邻元素w(u至少和两个元素相邻) ·构造H:G-u,w,任取S子集，N(S)数量最多减少一个 ·均有H中的IN(S)川>=|S ·按照归纳假设存在H中的最大匹配 现在你能理解为什么在归纳证明中，需要分 情形证明了吗？U W S u S W • 奠基: |U|=1,显然 • 假设:|U|<=|W|且1<=|U|<k且满足Hall条件时均存在最大匹配 • 归纳：当k=|U|以及|U|<=|W|且满足Hall条件时 • 从U任取一个u，从N(u)中任取一个w，构造H:G-{u,w}：H满足Hall条件吗? • 如果对U的任意真子集S，|N(S)|>|S|, 是成立的。否则？ • Case1：对所有U的真子集S，均有|N(S)|>|S| • 取U中某个元素u，取u的相邻元素w(u至少和两个元素相邻) • 构造H:G-{u,w}, 任取S子集，N(S)数量最多减少一个 • 均有H中的|N(S)|>=|S| • 按照归纳假设存在H中的最大匹配 你能想到用数学归纳 法证明吗？ 现在你能理解为什么在归纳证明中，需要分 情形证明了吗？