「ホールの定理」の版間の差分

2007年7月14日 (土) 15:13時点における版

【ほーるのていり (Hall's theorem)】

2部グラフ  $G=(V^{+},V^{-};A)\,$  において, 左側点集合  $V^{+}\,$  に関する完全マッチングが存在するための必要十分条件は次のように書ける:

  $|U^{+}|\leq |\{v\in V^{-}\mid \ u\in U^{+},(u,v)\in A\}|,\forall U^{+}\subseteq V^{+}.\,$

この不等式の右辺は,  $U^{+}\,$  中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ.  ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.

@@ 1行目: / 1行目: @@
 【ほーるのていり (Hall's theorem)】
-部グラフ $G = (V^+, V^-; A)$ において, 左側点集合 $V^+$ に関する完全マッチングが存在するための必要十分条件は次のように書ける:
+部グラフ <math>G = (V^+, V^-; A)\,</math> において, 左側点集合 <math>V^+\,</math> に関する完全マッチングが存在するための必要十分条件は次のように書ける:
+<br><br>
-\[
+<center>
-\begin{array}{l}
+  <math>|U^+| \leq |\{v \in V^- \mid \ u \in U^+, (u, v) \in A\}|, \forall U^+ \subseteq V^+ .\,</math>
-|U^+| \leq |\{v \in V^- \mid \ u \in U^+, (u, v) \in A\}|, \\
+</center>
-\hspace*{50mm} \forall U^+ \subseteq V^+ .
+<br>
-\end{array}
+  この不等式の右辺は, <math>U^+\,</math> 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ.  ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.
-\]
-  この不等式の右辺は, $U^+$ 中に左側点をもつ枝の右側点の数を表す.  この必要十分条件をホールの定理と呼ぶ.  ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.