被覆 (グラフ理論における)

出典: ORWiki

【ひふく (cover)】

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