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

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

- Usage:
    `d = numConnectedGraphComponents G`
- Inputs:
  - G, a hypergraph,
- 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

## See also

- Connected Components Tutorial -- clarifying the difference between graph and hypergraph components
- connectedGraphComponents -- returns the connected components of a graph
- isConnectedGraph -- determines if a graph is connected
- isolatedVertices -- returns all vertices not contained in any edge
- numConnectedComponents -- returns the number of connected components in a (hyper)graph

## Ways to use numConnectedGraphComponents:

- `numConnectedGraphComponents(HyperGraph)`

## For the programmer

The object numConnectedGraphComponents is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/EdgeIdeals.m2:3770:0.