最大マッチング最小被覆定理

【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】

2部グラフ $G=(V,A)\,$ において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち

$\max\{|M|\mid M\subseteq A$は $G\,$ のマッチング$\}\,$

$=\min\{|U|\mid U\subseteq V\,$ は $G\,$ の被覆構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \},\,}

という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる.