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.
V2.28, 13 July 2023