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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】''' 2部グラフ $G = (V, A)$ において, 最大マッチン...')
 
 
(3人の利用者による、間の4版が非表示)
1行目: 1行目:
 
'''【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】'''
 
'''【さいだいまっちんぐさいしょうひふくていり (maximum-matching minimum-cover theorem)】'''
  
−
2部グラフ $G = (V, A)$ において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
+
2部グラフ <math>G = (V, A) \,</math> において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち
  
−
\[
 
−
\begin{array}{l}
 
−
\max\{|M| \mid M \subseteq A\mbox{は} G\mbox{ のマッチング}\} \\
 
−
\hspace*{15mm} = \min\{|U| \mid U \subseteq V\mbox{は} G \mbox{ の被覆}\},
 
−
\end{array}
 
−
\]
 
  
−
という定理. ケーニグ(K\"onig)の定理, またはケーニグ・エゲルヴァーリ(K\"onig--Egerv\'ary)の定理とも呼ばれる.
+
<center>
 +
<table>
 +
<tr>
 +
<td>
 +
<math>
 +
\max\{|M| \mid M \subseteq A </math>は <math>G \,</math> のマッチング<math>\} \,</math>
 +
</td>
 +
</tr>
 +
<tr>
 +
<td align="right">
 +
<math>
 +
= \min\{|U| \mid U \subseteq V \,</math> は <math> G \,</math> の被覆<math> \}, \,</math></td>
 +
</tr></table>
 +
</center>
 +
 
 +
 
 +
という定理. ケーニグ(K&ouml;nig)の定理, またはケーニグ・エゲルヴァーリ(K&ouml;nig-Egerv&aacute;ry)の定理とも呼ばれる.
 +
 
 +
[[Category:グラフ･ネットワーク|さいだいまっちんぐさいしょうひふくていり]]

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

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

2部グラフ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G = (V, A) \,} において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \max\{|M| \mid M \subseteq A } は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G \,} のマッチング構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \} \,}

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle = \min\{|U| \mid U \subseteq V \,} は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G \,} の被覆構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \}, \,}


という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる.

「https://orsj-ml.org/orwiki/wiki/index.php?title=最大マッチング最小被覆定理&oldid=10461」から取得