FindEdgeCover

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

更多信息更多信息

  • 一个边覆盖是与每个顶点相关联的边集合.
  • FindEdgeCover 返回边列表.
  • 如果没有找到边覆盖,FindEdgeCover 将返回一个空列表.

背景
背景

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