Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

EdgeCoverQ

EdgeCoverQ[g,elist]

如果边列表 elist 是图 g 的一个边覆盖，则产生 True；否则，产生 False.

更多信息

一个边覆盖是与每个顶点相关联的边集合.

EdgeCoverQ 作用于无向图、有向图、多重图和混合图.

背景

EdgeCoverQ 检查给定的边列表是否是给定图的边覆盖. 一个边覆盖是与图的每个顶点相关联的边的集合（即它们的端点“覆盖”了图的顶点）. 边覆盖在社交网络、生物学和社会科学中都有应用.
对给定的图，具有最小可能边数的边覆盖被称为最小边覆盖并可用 FindEdgeCover 求得. 把 EdgeCoverQ 应用于图全部可能的边子集可列举全部的边覆盖，应用于大小等于最小边覆盖的边子集则可以列举全部的最小边覆盖.
VertexCoverQ 把类似的概念作用于顶点.

范例

打开所有单元关闭所有单元

基本范例 (2)

检验一个边集是否是一个完全图的边覆盖：

不是说有的边集都是一个图的边覆盖：

范围 (6)

检验无向图：

有向图：

多重图：

混合图：

EdgeCoverQ 对不是图的表达式给出 False：

EdgeCoverQ 作用于大规模图：

应用 (2)

列举所有边覆盖：

列举边的所有子集，并且选取边覆盖：

突出显示边覆盖：

列举所有最小边覆盖：

求最小边覆盖的长度：

列举所有长度为3的边的子集，并且选取边覆盖：

突出显示边覆盖：

属性和关系 (4)

对于不含有孤立顶点的图，EdgeList 是一个边覆盖：

一个最小边覆盖可以使用 FindEdgeCover 求得：

完全二分图具有大小为的边覆盖：

对于一个连通图，独立边集和边覆盖的总大小等于顶点数：

顶部