EdgeCoverQ

EdgeCoverQ[g,elist]
如果边列表 elist 是图 g 的一个边覆盖,则产生 True;否则,产生 False.

更多信息更多信息

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

背景
背景

  • EdgeCoverQ checks if a given edge list is an edge cover of a given graph. An edge cover is a set of graph edges that are incident to every vertex of a graph (i.e. their endpoints "cover" the vertices of the graph). Edge covers have applications in social networks, biology, and social sciences.
  • An edge cover having the smallest possible number of edges for a given graph is known as a minimum edge cover and can be found using FindEdgeCover. Application of EdgeCoverQ to all possible edge subsets of a graph can be used to enumerate all edge covers, and application to subsets of size equal to that of the smallest edge cover can be used to enumerate all minimum edge covers.
  • VertexCoverQ applies the analogous concept to vertices.
2010年引入
(8.0)