WOLFRAM

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

EdgeCoverQ[g,elist]

辺のリスト elist がグラフ g の辺被覆である場合にはTrueを，それ以外の場合にはFalseを返す．

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

EdgeCoverQ

EdgeCoverQ[g,elist]

辺のリスト elist がグラフ g の辺被覆である場合にはTrueを，それ以外の場合にはFalseを返す．

詳細

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

予備知識

  • EdgeCoverQは，指定された辺のリストが指定されたグラフの辺被覆かどうかを調べる．辺被覆とは，グラフのすべての頂点に接続している（つまり，辺の端点がグラフの頂点を「被っている」）グラフの辺の集合である．辺被覆の応用分野としては，ソーシャルネットワーク，生物学，社会科学等がある．
  • 指定されたグラフの可能な最小数の辺を持つ辺被覆は，最小辺被覆として知られ，FindEdgeCoverを使って求めることができる．EdgeCoverQを可能なすべての辺の部分集合に適用すると，すべての辺被覆を列挙することができ，最小辺被覆と同じサイズの部分集合に適用すると，すべての最小辺被覆を列挙することができる．
  • VertexCoverQは，同じ概念を頂点に対して適用する．

例題

すべて開く すべて閉じる

例  (2)

ある辺の集合が完全グラフの辺被覆かどうかを調べる：

Wolfram Language code: EdgeCoverQ[[image], {12, 35, 45}]

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

Wolfram Language code: EdgeCoverQ[[image], {13, 14}]

スコープ  (6)

無向グラフを調べる：

Wolfram Language code: EdgeCoverQ[[image], {12, 36, 54}]

有向グラフ：

Wolfram Language code: EdgeCoverQ[[image], {21, 36, 54}]

多重グラフ：

Wolfram Language code: EdgeCoverQ[[image], {12, 36, 54}]

混合グラフ：

Wolfram Language code: EdgeCoverQ[[image], {21, 36, 54}]

EdgeCoverQはグラフではない式に対してはFalseを与える：

Wolfram Language code: EdgeCoverQ[x, {12, 34}]

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

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: EdgeCoverQ[g, {12, 56}]//Timing

アプリケーション  (2)

すべての辺被覆を列挙する：

Wolfram Language code: g = CycleGraph[4]

辺のすべての部分集合を列挙し被覆を選ぶ：

Wolfram Language code: Subsets[EdgeList[g]]
Wolfram Language code: ecl = Select[%, EdgeCoverQ[g, #]&]

被覆をハイライトする：

Wolfram Language code: Table[HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], {h, ecl}]

すべての最小辺被覆を列挙する：

Wolfram Language code: g = WheelGraph[5]

最小辺被覆の長さを求める：

Wolfram Language code: Length[FindEdgeCover[g]]

長さが3の辺の部分集合すべてを求め被覆を選ぶ：

Wolfram Language code: ecl = Select[Subsets[EdgeList[g], {3}], EdgeCoverQ[g, #]&]

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

Wolfram Language code: Table[HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], {h, ecl}]

特性と関係  (4)

孤立した頂点がないグラフの場合，EdgeListは辺被覆である：

Wolfram Language code: Graph[{1, 2, 3, 4, 5}, {12, 23, 31, 45}]
Wolfram Language code: EdgeCoverQ[%, EdgeList[%]]

最小の辺被覆はFindEdgeCoverで求められる：

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: EdgeCoverQ[%, FindEdgeCover[%]]

完全二部グラフ にはサイズ の辺被覆がある：

Wolfram Language code: CompleteGraph[{2, 4}]
Wolfram Language code: Length[FindEdgeCover[%]] == Max[2, 4]

連結グラフの場合，独立辺集合と辺被覆の合計のサイズは頂点数に等しい：

Wolfram Language code: g = PetersenGraph[5, 2]
Wolfram Language code: Length[FindEdgeCover[g]] + Length[FindIndependentEdgeSet[g]] == VertexCount[g]
Wolfram Research (2010), EdgeCoverQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/EdgeCoverQ.html （2014年に更新）.

テキスト

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

CMS

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

APA

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

BibTeX

@misc{reference.wolfram_2026_edgecoverq, author="Wolfram Research", title="{EdgeCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/EdgeCoverQ.html}", note=[Accessed: 10-September-2026]}

BibLaTeX

@online{reference.wolfram_2026_edgecoverq, organization={Wolfram Research}, title={EdgeCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/EdgeCoverQ.html}, note=[Accessed: 10-September-2026]}