FindEdgeCover

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

更多信息更多信息

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

背景
背景

  • FindEdgeCover finds a single minimum edge cover of a graph and returns the result as an edge list. Here, an edge cover is a set of edges for which at least one edge endpoint is incident to every vertex in a graph. A minimum edge cover is an edge cover having the smallest possible number of edges. Minimum edge covers have applications in social networks, biology, and social sciences.
  • The size of (i.e. the number of edges in) a minimum edge cover of a graph is known as its edge cover number and is denoted . An edge cover can be found in polynomial time.
  • EdgeCoverQ can be used to test if a given edge set is a (not necessarily minimum) edge cover. Application of EdgeCoverQ to all possible edge subsets of a graph can therefore be used to enumerate all edge covers, and application to subsets of size equal to the edge cover number can be used to enumerate all minimum edge covers. FindVertexCover applies the same concept to vertices.
2010年引入
(8.0)