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

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

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

\[ \begin{array}{l} \max\{|M| \mid M \subseteq A\mbox{は} G\mbox{ のマッチング}\} \\

\hspace*{15mm} = \min\{|U| \mid U \subseteq V\mbox{は} G \mbox{ の被覆}\},

\end{array} \]

という定理. ケーニグ(K\"onig)の定理, またはケーニグ・エゲルヴァーリ(K\"onig--Egerv\'ary)の定理とも呼ばれる.