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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【ひふく (cover)】 $G = (V, A)$ を無向グラフとする. 頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ ...')
(相違点なし)

2007年7月13日 (金) 01:16時点における版

【ひふく (cover)】 

$G = (V, A)$ を無向グラフとする.  頂点集合 $U \subseteq V$ に対して, 任意の枝 $a \in A$ の少なくとも一方の端点が $U$ に含まれるとき, $U$ を $G$ の被覆と呼ぶ.  点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる.  2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.
「https://orsj-ml.org/orwiki/wiki/index.php?title=被覆_(グラフ理論における)&oldid=3773」から取得