「マッチング」の版間の差分
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【まっちんぐ (matching)】 | + | '''【まっちんぐ (matching)】''' |
無向グラフ <math>G = (V, E)\,</math> の枝部分集合 <math>M \subseteq A\,</math> で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 <math>M \subseteq A\,</math> がマッチングならば,<math>M\,</math> の枝に接続する点の数は <math>M\,</math> の要素数の2倍に等しく, またそのときに限って <math>M\,</math> はマッチングである. <math>k\,</math> 本の枝からなるマッチングを | 無向グラフ <math>G = (V, E)\,</math> の枝部分集合 <math>M \subseteq A\,</math> で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 <math>M \subseteq A\,</math> がマッチングならば,<math>M\,</math> の枝に接続する点の数は <math>M\,</math> の要素数の2倍に等しく, またそのときに限って <math>M\,</math> はマッチングである. <math>k\,</math> 本の枝からなるマッチングを | ||
<math>k\,</math>-マッチングと呼び, 特に <math>|V|/2\,</math> 本の枝からなるマッチングを完全マッチングと呼ぶ. | <math>k\,</math>-マッチングと呼び, 特に <math>|V|/2\,</math> 本の枝からなるマッチングを完全マッチングと呼ぶ. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|まっちんぐ]] | ||
| + | |||
| + | [[Category:計算幾何|まっちんぐ]] | ||
2008年11月13日 (木) 22:10時点における最新版
【まっちんぐ (matching)】
無向グラフ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G = (V, E)\,} の枝部分集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M \subseteq A\,} で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M \subseteq A\,} がマッチングならば,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\,} の枝に接続する点の数は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\,} の要素数の2倍に等しく, またそのときに限って 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\,} はマッチングである. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\,} 本の枝からなるマッチングを 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\,} -マッチングと呼び, 特に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle |V|/2\,} 本の枝からなるマッチングを完全マッチングと呼ぶ.