「最大マッチング最小被覆定理」の版間の差分

2008年11月9日 (日) 17:57時点における最新版

【さいだいまっちんぐさいしょうひふくていり (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)の定理とも呼ばれる.

@@ 3行目: / 3行目: @@
 部グラフ <math>G = (V, A) \,</math> において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
+<center>
+<table>
+<tr>
+<td>
+<math>
+\max\{|M| \mid M \subseteq A </math>は <math>G \,</math> のマッチング<math>\} \,</math>
+</td>
+</tr>
+<tr>
+<td align="right">
 <math>
-\max\{|M| \mid M \subseteq A </math>は <math>G \,</math> のマッチング <math>\} \,</math>
+= \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆<math> \}, \,</math></td>
+</tr></table>
+</center>
-<math>
+という定理. ケーニグ(K&ouml;nig)の定理, またはケーニグ・エゲルヴァーリ(K&ouml;nig-Egerv&aacute;ry)の定理とも呼ばれる.
- \ \ \ \ \  = \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆 <math> \} \,</math>
-という定理. ケーニグ(K\"onig)の定理, またはケーニグ・エゲルヴァーリ(K\"onig--Egerv\'ary)の定理とも呼ばれる.
+[[Category:グラフ･ネットワーク|さいだいまっちんぐさいしょうひふくていり]]