---
title: "Directed Trees"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/directed-tree.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/directed-tree.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Spanning Trees of a Graph or Digraph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/spanning-tree.md"}
next: {"title": "Colourings", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/colouring.md"}
intrinsics:
  - {"name": "IsRootedTree", "signature": "IsRootedTree(G): GrphDir -> BoolElt, GrphVert"}
  - {"name": "Root", "signature": "Root(G): GrphDir -> GrphVert"}
  - {"name": "IsRoot", "signature": "IsRoot(v): GrphVert -> BoolElt"}
  - {"name": "RootSide", "signature": "RootSide(v): GrphVert -> GrphVert"}
  - {"name": "VertexPath", "signature": "VertexPath(u, v): GrphVert, GrphVert -> SeqEnum"}
  - {"name": "BranchVertexPath", "signature": "BranchVertexPath(u, v): GrphVert, GrphVert -> SeqEnum"}
---

<a id="directed-tree"></a>
<a id="graph-sec-dir-tree"></a>
# 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.

<a id="function-isrootedtree-grphdir"></a>
## `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.

<a id="function-root-grphdir"></a>
## `Root(G): GrphDir -> GrphVert`

The root vertex of a rooted tree.

<a id="function-isroot-grphvert"></a>
## `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.

<a id="function-rootside-grphvert"></a>
## `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.

<a id="function-vertexpath-grphvert-grphvert"></a>
## `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$.

<a id="function-branchvertexpath-grphvert-grphvert"></a>
## `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$.
