is.bipartite             package:igraph             R Documentation

_D_e_c_i_d_e _w_h_e_t_h_e_r _a _g_r_a_p_h _i_s _b_i_p_a_r_t_i_t_e

_D_e_s_c_r_i_p_t_i_o_n:

     This function decides whether the vertices of a network can be
     mapped to two vertex types in a way that no vertices of the same
     type are connected.

_U_s_a_g_e:

     is.bipartite(graph)

_A_r_g_u_m_e_n_t_s:

   graph: The input graph.

_D_e_t_a_i_l_s:

     A bipartite graph in igraph has a ''type'' vertex attribute giving
     the two vertex types.

     This function simply checks whether a graph _could_ be bipartite.
     It tries to find a mapping that gives a possible division of the
     vertices into two classes, such that no two vertices of the same
     class are connected by an edge.

     The existence of such a mapping is equivalent of having no
     circuits of odd length in the graph. A graph with loop edges
     cannot bipartite.

     Note that the mapping is not necessarily unique, e.g. if the graph
     has at least two components, then the vertices in the separate
     components can be mapped independently.

_V_a_l_u_e:

     A named list with two elements: 

     res: A logical scalar, 'TRUE' if the can be bipartite, 'FALSE'
          otherwise.

    type: A possibly vertex type mapping, a logical vector. If no such
          mapping exists, then an empty vector.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_E_x_a_m_p_l_e_s:

     ## A ring has just one loop, so it is fine
     g <- graph.ring(10)
     is.bipartite(g)

     ## A star is fine, too
     g2 <- graph.star(10)
     is.bipartite(g2)

     ## A graph containing a triangle is not fine
     g3 <- graph.ring(10)
     g3 <- add.edges(g3, c(0,2))
     is.bipartite(g3)

