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 0th reduced homology group. This number plus 1 plus the number of isolated vertices of G gives the number of connected components of G.
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 |