科尼格在1931年给出了结论:对于二分 图等式成立。 引理8.1:设M是一个匹配,C是一个点 覆盖,且M=C|,则M是最大匹配,C 是最小点覆盖。 证明:若M是最大匹配,C是最小点覆 盖, 则β1(G)=M*,a0(G)=C科尼格在 1931 年给出了结论：对于二分 图等式成立。 引理 8.1：设M是一个匹配，C是一个点 覆盖，且|M|=|C|，则M是最大匹配，C 是最小点覆盖。 证明：若M*是最大匹配，C'是最小点覆 盖， 则1(G)=|M*|，0(G)=|C'|