FindIndependentVertexSet

FindIndependentVertexSet[g]
求具有最大顶点数的图 g 的独立顶点集.

FindIndependentVertexSet[g,n]
求具有至多 n 个顶点的独立顶点集.

FindIndependentVertexSet[g,{n}]
求具有恰好 n 个顶点的独立顶点集.

FindIndependentVertexSet[g,{nmin,nmax}]
求所含顶点数在 之间的独立顶点集.

FindIndependentVertexSet[g,nspec,s]
求至多 s 个独立顶点集.

FindIndependentVertexSet[{g,v},]
求仅包含顶点 v 的独立集.

更多信息更多信息

背景
背景

  • FindIndependentVertexSet finds one or more maximal independent vertex sets in a graph, returning them as a list of vertex lists. Here, an independent vertex set is a set of vertices such that no two vertices in the set are connected by an edge. Independent vertex sets have found applications in finance, coding theory, map labeling, pattern recognition, social networks, molecular biology, and scheduling.
  • There are two especially important types of independent vertex sets: maximum and maximal. Note these are not equivalent. A maximum independent vertex set is a vertex set containing the largest possible number of vertices for a given graph. In contrast, a maximal independent vertex set is an independent vertex set that cannot be extended by including one more adjacent vertices, meaning it is not a subset of a larger independent vertex set. A maximum independent vertex set is therefore always maximal, but the converse is not necessarily true.
  • FindIndependentVertexSet can find maximal independent vertex sets of different sizes. FindIndependentVertexSet can also find a single maximal independent vertex sets of specified size, a specified number of maximal independent vertex sets, or all such sets.
  • FindIndependentVertexSet[g] finds a single maximum independent vertex set of a graph g, FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],s] finds at most s, and FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All] finds all such sets. The size of a maximum independent vertex set of a graph g is known as its (vertex) independence number. The problem of finding a maximum independent vertex set (and hence independence number) of a given graph is NP-complete, meaning computation can be exponentially slow.
  • FindIndependentVertexSet[g,Infinity] finds a single maximal independent vertex set of a graph g, FindIndependentVertexSet[g,Infinity,s] finds at most s, and FindIndependentVertexSet[g,Infinity,All] finds all such sets.
  • A set of vertices can be tested to see if it is independent (without the requirement that it also be maximal) using IndependentVertexSetQ. An independent vertex set corresponds to the complement of a vertex cover (cf. FindVertexCover). A maximal independent vertex set of a graph is equivalent to a maximal clique on the GraphComplement (cf. FindClique). FindIndependentEdgeSet applies the same concept as FindIndependentVertexSet to edges, with the resulting independent edge sets also being known as matchings.
2010年引入
(8.0)
| 2014年更新
(10.0)