二元图的匹配与覆盖成为其最大匹配与最小覆盖的充要条件
设 $G=(X,Y,E)$ 是二元图, $M$ 是图 $G$ 的一个匹配, $K$ 是图 $G$ 的一个覆盖. 则 $M,K$ 分别是图 $G$ 的最大匹配、最小覆盖的充要条件是: $|M|=|K|$.
References:
赵静、但琦 主编《数学建模与数学实验》(第4版) P.102
设 $G=(X,Y,E)$ 是二元图, $M$ 是图 $G$ 的一个匹配, $K$ 是图 $G$ 的一个覆盖. 则 $M,K$ 分别是图 $G$ 的最大匹配、最小覆盖的充要条件是: $|M|=|K|$.
References:
赵静、但琦 主编《数学建模与数学实验》(第4版) P.102