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

2008年11月13日 (木) 21:51時点における最新版

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