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

出典: ORWiki

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

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


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

= \min\{|U| \mid U \subseteq V \, は G \, の被覆\}, \,


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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E6%9C%80%E5%A4%A7%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0%E6%9C%80%E5%B0%8F%E8%A2%AB%E8%A6%86%E5%AE%9A%E7%90%86" より作成