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

2007年7月12日 (木) 23:47時点における版

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

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

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

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

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

@@ 1行目: / 1行目: @@
 '''【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】'''
-部グラフ $G = (V, A)$ において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
+部グラフ <math>G = (V, A) \,</math> において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
-\[
+<math>
-\begin{array}{l}
+\max\{|M| \mid M \subseteq A </math>は <math>G \,</math> のマッチング <math>\} \,</math>
-\max\{|M| \mid M \subseteq A\mbox{は} G\mbox{ のマッチング}\} \\
-  \hspace*{15mm} = \min\{|U| \mid U \subseteq V\mbox{は} G \mbox{ の被覆}\},
+<math>
-\end{array}
+  \ \ \ \ \  = \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆 <math> \} \,</math>
-\]
 という定理. ケーニグ(K\"onig)の定理, またはケーニグ・エゲルヴァーリ(K\"onig--Egerv\'ary)の定理とも呼ばれる.