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 语言. 2010. "EdgeCoverQ." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2014. https://reference.wolfram.com/language/ref/EdgeCoverQ.html.

APA

Wolfram 语言. (2010). EdgeCoverQ. Wolfram 语言与系统参考资料中心. 追溯自 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: 07-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: 07-September-2026]}