「被覆 (グラフ理論における)」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
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日 (金) 14:53時点における版

【ひふく (cover)】

 を無向グラフとする.  頂点集合  に対して, 任意の枝  の少なくとも一方の端点が  に含まれるとき,  の被覆と呼ぶ.  点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる.  2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.