「被覆 (グラフ理論における)」の版間の差分
(新しいページ: '【ひふく (cover)】 $G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ ...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (3人の利用者による、間の5版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【ひふく (cover)】 | + | '''【ひふく (cover)】''' |
| − | + | <math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている. | |
| + | |||
| + | [[Category:グラフ･ネットワーク|ひふく]] | ||
2008年11月13日 (木) 15:19時点における最新版
【ひふく (cover)】
を無向グラフとする. 頂点集合 に対して, 任意の枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a \in A\,} の少なくとも一方の端点が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\,} に含まれるとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\,} を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\,} の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.
