WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

VertexCoverQ[g,vlist]

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

詳細
Details and Options Details and Options
予備知識
例題  
例  
スコープ  
アプリケーション  
特性と関係  
関連項目
関連するガイド
履歴
引用書式

VertexCoverQ

VertexCoverQ[g,vlist]

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

詳細

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

予備知識

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

例題

すべて開く すべて閉じる

例  (2)

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

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

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

Wolfram Language code: VertexCoverQ[[image], {1, 4}]

スコープ  (6)

無向グラフを調べる：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

有向グラフ：

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

多重グラフ：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

混合グラフ：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

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

Wolfram Language code: VertexCoverQ[x, {1, 3}]

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

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: VertexCoverQ[g, {1, 2}]//Timing

アプリケーション  (2)

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

Wolfram Language code: g = CycleGraph[4, VertexSize -> Small]

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

Wolfram Language code: Subsets[VertexList[g]]
Wolfram Language code: vcl = Select[%, VertexCoverQ[g, #]&]

被覆をハイライトする：

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

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

Wolfram Language code: g = PetersenGraph[5, 2, VertexSize -> Medium]

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

Wolfram Language code: FindVertexCover[g]
Wolfram Language code: n = Length[%]

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

Wolfram Language code: vcl = Select[Subsets[VertexList[g], {6}], VertexCoverQ[g, #]&]

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

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

特性と関係  (7)

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

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, VertexList[%]]

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

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, FindVertexCover[%]]

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

Wolfram Language code: g = GridGraph[{2, 3}]
Wolfram Language code: vc = FindVertexCover[g]

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

Wolfram Language code: IndependentVertexSetQ[g, Complement[VertexList[g], vc]]

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

Wolfram Language code: g = WheelGraph[8]
Wolfram Language code: Length[FindVertexCover[g]] + Length[First[FindIndependentVertexSet[g]]] == VertexCount[g]

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

Wolfram Language code: g = GridGraph[{2, 3}]

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

Wolfram Language code: h = GraphComplement[g, VertexCoordinates -> GraphEmbedding[g]]
Wolfram Language code: FindVertexCover[h]

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

Wolfram Language code: Complement[VertexList[g], FindVertexCover[h]]
Wolfram Language code: Subgraph[g, %]
Wolfram Language code: CompleteGraphQ[%]

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

Wolfram Language code: CompleteGraph[{2, 4}]
Wolfram Language code: Length[FindVertexCover[%]] == Min[2, 4]

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

Wolfram Language code: g = CycleGraph[6]
Wolfram Language code: BipartiteGraphQ[g]
Wolfram Language code: Length[FindVertexCover[g]] == Length[FindIndependentEdgeSet[g]]
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_2026_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 06-November-2026]}

BibLaTeX

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