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

connectedGraphComponents -- returns the connected components of a graph



This function returns the connected components of a graph. A connected component of a graph is any maximal set of vertices which are pairwise connected by a (possibly trivial) path. Isolated vertices, which are those not appearing in any edge, form their own connected components. This is in contrast to connectedComponents in which isolated vertices do not appear in any connected components. See the Connected Components Tutorial for more information.

i1 : R = QQ[a..k];
i2 : G = graph {a*b,b*c,c*d,a*d,f*g,h*i,j*k,h*k}

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

o2 : Graph
i3 : L = connectedGraphComponents G

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

o3 : List

In the following example, graph G contains the isolated vertex d. Notice that d appears in its own connected component and hence G is not connected.

i4 : R = QQ[a,b,c,d];
i5 : G = graph {a*b, b*c}

o5 = Graph{"edges" => {{a, b}, {b, c}}}
           "ring" => R
           "vertices" => {a, b, c, d}

o5 : Graph
i6 : connectedGraphComponents G

o6 = {{d}, {a, b, c}}

o6 : List
i7 : isolatedVertices G

o7 = {d}

o7 : List
i8 : isConnectedGraph G

o8 = false

See also

Ways to use connectedGraphComponents :

For the programmer

The object connectedGraphComponents is a method function.