Directed Trees

In the following functions, the graph is assumed to be a directed tree. This means it is a tree containing a root vertex and all edges are directed away from that vertex.

IsRootedTree(G): GrphDir -> BoolElt, GrphVert

Returns true exactly when the directed graph \(G\) is a tree having a vertex \(v\) such that all edges are directed away from \(v\). In this case, the root vertex \(v\) is returned as a second value.

Root(G): GrphDir -> GrphVert

The root vertex of a rooted tree.

IsRoot(v): GrphVert -> BoolElt

Returns true if and only if the graph containing the vertex \(v\) is directed as a rooted tree with \(v\) as root.

RootSide(v): GrphVert -> GrphVert

When the graph containing the vertex \(v\) is directed as a rooted tree, this returns the unique neighbouring vertex to \(v\) which is closer to the root vertex. If \(v\) is the root vertex, it is returned itself.

VertexPath(u, v): GrphVert, GrphVert -> SeqEnum

A sequence of vertices comprising a path in a directed graph from the vertex \(u\) to the vertex \(v\). The path does not necessarily respect the edge directions. Indeed it will first trace back to a common ancestor of \(u\) and \(v\) and then follow edge directions to \(v\).

BranchVertexPath(u, v): GrphVert, GrphVert -> SeqEnum

The sequence of vertices on the vertex path from the vertex \(u\) to the vertex \(v\) having valency at least \(3\).