next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EdgeIdeals :: numConnectedComponents

numConnectedComponents -- returns the number of connected components in a (hyper)graph



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

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

We depart from this method in two cases: We define the hypergraph with only the empty edge (corresponding to the irrelevant simplicial complex) and the hypergraph with empty edge set (corresponding to the void simplicial complex) to have 0 connected components.

Although this method can be applied to graphs, its output does not match the most common meaning for the number of connected components of a graph. Instead, one should use numConnectedGraphComponents.

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 : numConnectedComponents g

o4 = 1
i5 : numConnectedComponents h

o5 = 2

The following example contains a hypergraph with an edge of size one. The vertex in this edge is not considered isolated and does count as a connected component.

i6 : S = QQ[a..d];
i7 : H = hyperGraph {a*b,c}

o7 = HyperGraph{edges => {{a, b}, {c}}  }
                ring => S
                vertices => {a, b, c, d}

o7 : HyperGraph
i8 : isolatedVertices H

o8 = {d}

o8 : List
i9 : connectedComponents H

o9 = {{a, b}, {c}}

o9 : List
i10 : numConnectedComponents H

o10 = 2

See also

Ways to use numConnectedComponents :

For the programmer

The object numConnectedComponents is a method function.