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