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

connectedGraphComponents -- returns the connected components of a graph

Synopsis

Description

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.