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

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

Synopsis

Description

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.