Macaulay2 » Documentation
Packages » EdgeIdeals :: numConnectedGraphComponents
next | previous | forward | backward | up | index | toc

numConnectedGraphComponents -- returns the number of connected components in a graph



This function returns the number of connected components of a graph. A connected component of a graph is any maximal set of vertices which are pairwise connected by a path. Isolated vertices, which are those not appearing in any edge, count as connected components. This is in contrast to numConnectedComponents in which isolated vertices are not counted as connected components. See the Connected Components Tutorial for more information.

The algorithm used by numConnectedGraphComponents turns G into a simplicial complex, and then computes the rank of the 0^{th} reduced homology group. This number plus 1 plus the number of isolated vertices of G gives the number of connected components of G.

This method is intended to match the most common meaning for the number of connected components of a graph. This method can also be used on hypergraphs.

i1 : S = QQ[a..e];
i2 : g = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o2 : Graph
i3 : h = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not connected)

o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o3 : Graph
i4 : k = graph {a*b,b*c,c*d,a*d} -- 4-cycle and isolated vertex (not connected)

o4 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o4 : Graph
i5 : numConnectedGraphComponents g

o5 = 1
i6 : numConnectedGraphComponents h

o6 = 2
i7 : numConnectedGraphComponents k

o7 = 2

See also

Ways to use numConnectedGraphComponents :

For the programmer

The object numConnectedGraphComponents is a method function.