In this tutorial, we discuss the various methods that deal with connected components of graphs and hypergraphs. Our main objective is to make a distinction between the two different definitions of connected components that are used in the EdgeIdeals package.
A vertex of a (hyper)graph H said to be an isolated vertex if it is not contained in any edge of H. In particular, if a vertex of H is contained in a edge of size one then it is not considered isolated.
i1 : R = QQ[u,v,x,y,z]; |
i2 : H = hyperGraph({{u,v},{x}}); |
i3 : isolatedVertices H o3 = {y, z} o3 : List |
Graph Components. A connected component of a graph is any maximal set of vertices which are pairwise connected by a (possibly trivial) path. The most important part of this definition is that isolated vertices count as connected components.
The following methods use this definition of a connected component: connectedGraphComponents, numConnectedGraphComponents and isConnectedGraph.
Hypergraph Components. A connected component of a hypergraph is any maximal set of vertices which are pairwise connected by a non-trivial path. Here isolated vertices do not count as connected components.
The following methods use the hypergraph definition of a connected component: connectedComponents, numConnectedComponents and isConnected.
The next example uses all of these methods on a graph to illustrate the difference between the two definitions.
i4 : R = QQ[u,v,x,y,z]; |
i5 : G = graph({{x,y},{y,z}}); |
i6 : isolatedVertices G o6 = {u, v} o6 : List |
i7 : connectedGraphComponents G o7 = {{u}, {v}, {x, y, z}} o7 : List |
i8 : numConnectedGraphComponents G o8 = 3 |
i9 : isConnectedGraph G o9 = false |
i10 : connectedComponents G o10 = {{x, y, z}} o10 : List |
i11 : numConnectedComponents G o11 = 1 |
i12 : isConnected G o12 = true |