詳細

FindVertexCoverは頂点のリストを返す．
頂点被覆が見付からない場合，FindVertexCoverは空のリストを返す．
頂点被覆はすべての辺に接続している頂点集合である．

FindVertexCoverは，無向グラフ，有向グラフ，重み付きグラフ，多重グラフ，混合グラフに使うことができる．

予備知識

FindVertexCoverはグラフの単一の頂点被覆を求める．ただし，頂点被覆は，各辺がいずれかの頂点に接続しているという条件を満足する頂点の部分集合でなければならない．
FindVertexCover[g]は，グラフ g の最小頂点被覆（可能な限り小さい頂点被覆）を求める．一方，FindVertexCover[g,k]は，サイズが k の頂点被覆を求める．グラフ g の最小頂点被覆のサイズはその頂点被覆数として知られる．一般グラフの最小頂点被覆（したがって頂点被覆数）を求める問題はNP完全である（つまり計算が指数的に遅い）．しかし，最小頂点被覆は，二部グラフ（頂点集合が独立する2つの集合に分割できるグラフ）については，多項式時間で求めることができる．
頂点被覆は独立頂点集合（同じ辺に接続している頂点がない頂点の集合）と密接な関係がある．頂点集合は，その補集合が独立頂点集合を形成するときかつそのときに限り，頂点被覆である．したがって，グラフ中の頂点被覆と独立頂点集合の数は等しい．さらに，無向グラフの独立数（最大独立頂点集合のサイズ）と頂点被覆数（最小頂点被覆のサイズ）の和は頂点数に一致する．
グラフの頂点集合は，極大独立辺集合の各辺の端点を取って形成することができる．（ここで，独立辺集合とは，同じ頂点を共有する辺がない辺の集合である，極大独立辺集合とは，独立性を損なわずにグラフの他の辺を加えることができない独立辺集合のことであり，最大独立辺集合とは与えられたグラフで可能な限り最大の独立辺集合のことである）．結果として，最小頂点被覆のサイズは，常に，最大でも最大独立辺集合の2倍にしかならない．König–Egerváryの定理は，二部グラフの最大独立辺集合のサイズ（マッチする数）がその頂点被覆数と等しいと述べている．
VertexCoverQを使って，与えられた頂点集合が指定されたグラフの頂点被覆を形成するかどうかを調べることができる．複数の頂点被覆を求める自明な実装は，したがって，VertexCoverQをグラフ頂点の希望する任意の部分集合に適用することで書くことができる．同様に，FindIndependentVertexSetを使って，グラフ内の1つあるいは複数の（それぞれの補集合が頂点被覆である）極大独立頂点集合を求めることができる．FindEdgeCoverはグラフの辺被覆についてFindVertexCoverと同じように使うことができる．

例題

すべて開くすべて閉じる

例 (1)

頂点被覆を求める：

Wolfram Language code: g = GraphData["OctahedralGraph"];

Wolfram Language code: FindVertexCover[g]

被覆を示す：

Wolfram Language code: HighlightGraph[g, %, VertexSize -> 0.2]