「最大マッチング最小被覆定理」の版間の差分
| 3行目: | 3行目: | ||
2部グラフ <math>G = (V, A) \,</math> において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち | 2部グラフ <math>G = (V, A) \,</math> において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち | ||
| + | |||
| + | <center> | ||
| + | <table> | ||
| + | <tr> | ||
| + | <td> | ||
<math> | <math> | ||
| − | \max\{|M| \mid M \subseteq A </math>は <math>G \,</math> のマッチング <math>\} \,</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 | + | という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる. |
2007年7月17日 (火) 13:35時点における版
【さいだいまっちんぐさいしょうひふくていり (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 \,} の被覆 |
という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる.