WolframのWebサイトのコンテンツとインタラクトしたりフォームを送信したりするためには，JavaScriptを有効にしてください．有効にする方法

FindVertexCover

FindVertexCover[g]

グラフ g の頂点数が最小の頂点被覆を求める．

FindVertexCover[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細

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)

頂点被覆を求める：

被覆を示す：

スコープ (7)

FindVertexCoverは無向グラフに使うことができる：

有向グラフ：

重み付きグラフ：

多重グラフ：

混合グラフ：

規則を使ってグラフを指定する：

FindVertexCoverは大きいグラフに使うことができる：

特性と関係 (6)

FindVertexCoverの結果はVertexCoverQで確かめることができる：

頂点集合はその補集合が独立集合である場合は頂点被覆である：

頂点の補集合が独立であることを確かめる：

頂点被覆と最大独立集合の合計サイズは頂点数と同じである：

GraphComplementの頂点被覆の補集合はもとのグラフのクリークである：

同じ埋込みを使って補集合を計算する：

その補集合はクリークである：

補集合二部グラフにはサイズがの頂点被覆がある：

二部グラフ内の最大独立辺集合のサイズは最小の頂点被覆と同じである：

トップへ