edge.connectivity           package:igraph           R Documentation

_E_d_g_e _c_o_n_n_e_c_t_i_v_i_t_y.

_D_e_s_c_r_i_p_t_i_o_n:

     The edge connectivity of a graph or two vertices, this is recently
     also called group adhesion.

_U_s_a_g_e:

     edge.connectivity(graph, source=NULL, target=NULL, checks=TRUE)
     edge.disjoint.paths(graph, source, target)
     graph.adhesion(graph, checks=TRUE)

_A_r_g_u_m_e_n_t_s:

   graph: The input graph.

  source: The id of the source vertex, for 'edge.connectivity' it can
          be 'NULL', see details below.

  target: The id of the target vertex, for 'edge.connectivity' it can
          be 'NULL', see details below.

  checks: Logical constant. Whether to check that the graph is
          connected and also the degree of the vertices. If the graph
          is not (strongly) connected then the connectivity is
          obviously zero. Otherwise if the minimum degree is one then
          the edge connectivity is also one. It is a good idea to
          perform these checks, as they can be done quickly compared to
          the connectivity calculation itself.  They were suggested by
          Peter McMahan, thanks Peter. 

_D_e_t_a_i_l_s:

     The edge connectivity of a pair of vertices ('source' and
     'target') is the minimum number of edges needed to remove to
     eliminate all (directed) paths from 'source' to 'target'.
     'edge.connectivity' calculates this quantity if both the 'source'
     and 'target' arguments are given (and not 'NULL'). 

     The edge connectivity of a graph is the minimum of the edge
     connectivity of every (ordered) pair of vertices in the graph.
     'edge.connectivity' calculates this quantity if neither the
     'source' nor the 'target' arguments are given (ie. they are both
     'NULL').

     A set of edge disjoint paths between two vertices is a set of
     paths between them containing no common edges. The maximum number
     of edge disjoint paths between two vertices is the same as their
     edge connectivity.

     The adhesion of a graph is the minimum number of edges needed to
     remove to obtain a graph which is not strongly connected. This is
     the same as the edge connectivity of the graph.

     The three functions documented on this page calculate similar
     properties, more precisely the most general is
     'edge.connectivity', the others are included only for having more
     descriptive function names.

_V_a_l_u_e:

     A scalar real value.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

     Douglas R. White and Frank Harary: The cohesiveness of blocks in
     social networks: node connectivity and conditional density, TODO:
     citation

_S_e_e _A_l_s_o:

     'graph.maxflow', 'vertex.connectivity', 'vertex.disjoint.paths',
     'graph.cohesion'

_E_x_a_m_p_l_e_s:

     g <- barabasi.game(100, m=1)
     g2 <- barabasi.game(100, m=5)
     edge.connectivity(g, 99, 0)
     edge.connectivity(g2, 99, 0)
     edge.disjoint.paths(g2, 99, 0)

     g <- erdos.renyi.game(50, 5/50)
     g <- as.directed(g)
     g <- subgraph(g, subcomponent(g, 1))
     graph.adhesion(g)

