independent.vertex.sets        package:igraph        R Documentation

_I_n_d_e_p_e_n_d_e_n_t _v_e_r_t_e_x _s_e_t_s

_D_e_s_c_r_i_p_t_i_o_n:

     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

_U_s_a_g_e:

     independent.vertex.sets(graph, min=NULL, max=NULL)
     largest.independent.vertex.sets(graph)
     maximal.independent.vertex.sets(graph)
     independence.number(graph)

_A_r_g_u_m_e_n_t_s:

   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. 'NULL' means no limit.

     max: Numeric constant, limit for the maximum size of the
          independent vertex sets to find. 'NULL' means no limit. 

_D_e_t_a_i_l_s:

     '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.

_V_a_l_u_e:

     '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.

_A_u_t_h_o_r(_s):

     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.

_R_e_f_e_r_e_n_c_e_s:

     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.

_S_e_e _A_l_s_o:

     'cliques'

_E_x_a_m_p_l_e_s:

     # 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))

