next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 web site

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

Synopsis

Usage:
d = numConnectedComponents H
Inputs:
- H, an object of class HyperGraph
Outputs:
- d, an integer, the number of connected components of H

Description

The function returns the number of connected components of a (hyper)graph. To count the number of components, the algorithm turns H into a simplicial complex, and then computes the rank of the 0^th reduced homology group. This number plus 1 gives us the number of connected components.

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

See also

connectedComponents -- returns the connected components of a hypergraph
isConnected -- determines if a (hyper)graph is connected

Ways to use `numConnectedComponents` :

numConnectedComponents(HyperGraph)