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

## Synopsis

• Usage:
d = numConnectedGraphComponents G
• Inputs:
• G, ,
• Outputs:
• d, an integer, the number of connected components of G

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