VertexCoverQ

VertexCoverQ[g,vlist]
頂点のリスト vlist がグラフ g の頂点被覆の場合はTrueを,そうでなければFalseを返す.

詳細詳細

  • 頂点被覆とはすべての辺に接続している頂点の集合のことである.
  • VertexCoverQは,無向グラフ,有向グラフ,多重グラフ,混合グラフに使うことができる.

予備知識
予備知識

  • VertexCoverQは,指定された頂点集合が与えられたグラフの頂点被覆を形成するかどうかを調べる.頂点被覆とは,グラフの各辺が集合中のいずれかの頂点に接続しているという条件を満足する頂点集合のことである.VertexCoverQは,集合が頂点被覆の場合はTrueを返し,それ以外の場合はFalseを返す.
  • グラフ全体の頂点集合は常に(可能な限り最大サイズの)頂点被覆である.あるグラフの可能な限り最小の頂点被覆は最小頂点被覆として知られており,そのサイズは頂点被覆数として知られている.
  • 頂点被覆は独立頂点集合と密接な関係がある.独立頂点集合は,同じ辺の一部である頂点が存在しない頂点の集合である.頂点の集合は,その補集合が独立頂点集合を形成するときかつそのときに限り,頂点被覆である.結果として,グラフの頂点被覆の数と独立頂点集合の数は等しい.
  • FindVertexCoverを使って単一の最小頂点被覆あるいは任意の固定サイズの単一の頂点被覆を求めることができるが,すべての頂点被覆を求めることはできない.グラフのすべての頂点被覆を求める自明な実装は,VertexCoverQをグラフの頂点のすべての部分集合に適用することで構築することができる.EdgeCoverQはグラフの辺被覆についてVertexCoverQと同じような調べを行う.FindIndependentVertexSetを使って,1つあるいは複数の(その補集合のそれぞれが頂点被覆である)グラフの極大独立頂点集合を求めることができる.

例題例題すべて開くすべて閉じる

  (2)  (2)

グラフ中のある頂点集合が頂点被覆かどうか調べる:

In[1]:=
Click for copyable input
Out[1]=

グラフ中のすべての頂点集合が頂点被覆である訳ではない:

In[1]:=
Click for copyable input
Out[1]=
2010年に導入
(8.0)
| 2014年に修正
(10.0)