VertexCoverQ

VertexCoverQ[g,vlist]

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

詳細

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

予備知識

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

例題

すべて開くすべて閉じる

例  (2)

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

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

スコープ  (6)

無向グラフを調べる：

有向グラフ：

多重グラフ：

混合グラフ：

グラフではない式に対しては，VertexCoverQはFalseを返す：

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

アプリケーション  (2)

巡回グラフのすべての頂点被覆を列挙する：

頂点の部分集合をすべて列挙し，被覆されているものを選ぶ：

被覆をハイライトする：

ペテルセン(Petersen)グラフの最小頂点被覆をすべて列挙する：

最小頂点被覆の大きさを求める：

最小頂点被覆をすべて列挙する：

最小被覆をハイライトする：

特性と関係  (7)

グラフのVertexListは頂点（通常最小ではない）被覆である：

FindVertexCoverを使って最小頂点被覆を求めることができる：

頂点集合はその補集合が独立集合である場合かつその場合に限り頂点被覆である：

頂点の補集合が独立かどうか調べる：

頂点被覆サイズと最大独立辺集合の合計サイズは頂点数に等しい：

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

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

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

完全二部グラフ には大きさが の頂点被覆がある：

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

Wolfram Research (2010), VertexCoverQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/VertexCoverQ.html （2014年に更新）.

テキスト

Wolfram Research (2010), VertexCoverQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/VertexCoverQ.html （2014年に更新）.

CMS

Wolfram Language. 2010. "VertexCoverQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/VertexCoverQ.html.

APA

Wolfram Language. (2010). VertexCoverQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/VertexCoverQ.html

BibTeX

@misc{reference.wolfram_2024_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 21-November-2024 ]}