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

FindEdgeCover

FindEdgeCover[g]

求含有最小边数的图 g 的边覆盖.

FindEdgeCover[{vw,…}]

使用 vw 指定图 g.

更多信息

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

FindEdgeCover 返回边列表.
如果没有找到边覆盖则 FindEdgeCover 会返回空列表.
FindEdgeCover 可用于无向图、有向图、加权图、多重图和混合图.

背景

FindEdgeCover 会找出图的单个最小边覆盖并返回边列表作为结果. 这里，边覆盖是一个边的集合，图的每个顶点都至少和这个集合中一条边的顶点重合. 最小边覆盖是有最小可能边数的边覆盖. 最小边覆盖在社交网络、生物学和社会科学中都有应用.
图的最小边覆盖的大小（即其中边的数目）被称为它的边覆盖数并被表示为 . 可以在多项式时间内找到边覆盖.
EdgeCoverQ 可被用于测试给定的边集合是否是（未必是最小的）边覆盖. EdgeCoverQ 可被应用于图的全部边子集，以此来枚举全部的边覆盖，而将其应用于全部大小等于边覆盖数的子集则可以枚举全部的最小边覆盖. FindVertexCover 将同样的概念用在了顶点上.

范例

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

基本范例 (1)

求边覆盖：

显示边覆盖：

范围 (8)

FindEdgeCover 适用于无向图：

有向图：

加权图：

多重图：

混合图：

使用规则指定图：

当不存在边覆盖时 FindEdgeCover 会返回空结果：

FindEdgeCover 作用于大规模图：

属性和关系 (5)

一个边覆盖中的边与每个顶点相关联：

用 EdgeCoverQ 检验一个边集是否是边覆盖：

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

完全二分图具有边覆盖数：

一个 StarGraph 的边覆盖包含了它的所有边：

顶部