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

connectedComponents -- returns the connected components of a hypergraph

Synopsis

Description

This function returns the 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 appear in any connected components. This is in contrast to connectedGraphComponents in which isolated vertices form their own connected components. See the Connected Components Tutorial for more information.

i1 : R = QQ[a..l];
 
i2 : H = hyperGraph {a*b*c, c*d, d*e*f, h*i, i*j, l}

o2 = HyperGraph{"edges" => {{a, b, c}, {c, d}, {d, e, f}, {h, i}, {i, j}, {l}}}
                "ring" => R
                "vertices" => {a, b, c, d, e, f, g, h, i, j, k, l}

o2 : HyperGraph
 
i3 : L = connectedComponents H

o3 = {{a, b, c, d, e, f}, {h, i, j}, {l}}

o3 : List
 
i4 : apply(L, C -> inducedHyperGraph(H,C))

o4 = {HyperGraph{"edges" => {{a, b, c}, {c, d}, {d, e, f}}},
                 "ring" => QQ[a..f]                         
                 "vertices" => {a, b, c, d, e, f}           
     ------------------------------------------------------------------------
     HyperGraph{"edges" => {{h, i}, {i, j}}}, HyperGraph{"edges" => {{l}} }}
                "ring" => QQ[h..j]                       "ring" => QQ[l]
                "vertices" => {h, i, j}                  "vertices" => {l}

o4 : List

In the following example, hypergraph H contains the isolated vertex d and the vertex c which is in an edge of size one. Notice that d does not appear in any connected component while c does.

i5 : R = QQ[a,b,c,d];
 
i6 : H = hyperGraph {a*b, c}

o6 = HyperGraph{"edges" => {{a, b}, {c}}  }
                "ring" => R
                "vertices" => {a, b, c, d}

o6 : HyperGraph
 
i7 : connectedComponents H

o7 = {{a, b}, {c}}

o7 : List
 
i8 : isolatedVertices H

o8 = {d}

o8 : List

See also

Ways to use connectedComponents :

For the programmer

The object connectedComponents is a method function.