「最大マッチング最小被覆定理」の版間の差分
ナビゲーションに移動
検索に移動
| 15行目: | 15行目: | ||
<td align="right"> | <td align="right"> | ||
<math> | <math> | ||
| − | = \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆<math> \} \,</math></td> | + | = \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆<math> \}, \,</math></td> |
</tr></table> | </tr></table> | ||
</center> | </center> | ||
2007年7月17日 (火) 13:36時点における版
【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】
2部グラフ において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
|
は のマッチング |
| は の被覆 |
という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる.