Connected Components Tutorial -- clarifying the difference between graph and hypergraph components

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