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

【ひふく (cover)】

$G=(V,A)\,$ を無向グラフとする.  頂点集合 $U\subseteq V\,$ に対して, 任意の枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a \in A\,<math> の少なくとも一方の端点が <math>U\,}
 に含まれるとき, $U\,$ を $G\,$ の被覆と呼ぶ.  点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる.  2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.