「被覆 (グラフ理論における)」の版間の差分
ナビゲーションに移動
検索に移動
| 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部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている. | + | <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部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている. |
2007年7月13日 (金) 13:18時点における版
【ひふく (cover)】
を無向グラフとする. 頂点集合 に対して, 任意の枝 の少なくとも一方の端点が に含まれるとき, を の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.
