independent.vertex.sets {igraph} | R Documentation |
A vertex set is called independent if there no edges between any two vertices in it. These functions find independent vertex sets in undirected graphs
independent.vertex.sets(graph, min=NULL, max=NULL) largest.independent.vertex.sets(graph) maximal.independent.vertex.sets(graph) independence.number(graph)
graph |
The input graph, directed graphs are considered as undirected, loop edges and multiple edges are ignored. |
min |
Numeric constant, limit for the minimum size of the
independent vertex sets to find. |
max |
Numeric constant, limit for the maximum size of
the independent vertex sets to find. |
independent.vertex.sets
finds all independent vertex sets in
the network, obeying the size limitations given in the min
and
max
arguments.
largest.independent.vertex.sets
finds the largest independent
vertex sets in the graph. An independent vertex set is largest if
there is no independent vertex set with more vertices.
maximal.independent.vertex.sets
finds the maximal independent
vertex sets in the graph. An independent vertex set is maximal if it
cannot be extended to a larger independent vertex set. The largest
independent vertex sets are maximal, but the opposite is not always
true.
independece.number
calculate the size of the largest
independent vertex set(s).
These functions use the algorithm described by Tsukiyama et al., see reference below.
independent.vertex.sets
, largest.independent.vertex.sets
and maximal.independent.vertex.sets
return a list containing
numeric vertex ids, each list element is an independent vertex set.
independence.number
returns an integer constant.
Tamas Nepusz ntamas@rmki.kfki.hu ported it from the Very Nauty Graph Library by Keith Briggs google@for.it and Gabor Csardi csardi@rmki.kfki.hu wrote the R interface and this manual page.
S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977.
# A quite dense graph g <- erdos.renyi.game(100, 0.8) independence.number(g) independent.vertex.sets(g, min=independence.number(g)) largest.independent.vertex.sets(g) # Empty graph subgraph(g, largest.independent.vertex.sets(g)[[1]]) length(maximal.independent.vertex.sets(g))