1 Graph Theory
1.1 Directed Graphs
A digraph (directed graph) is a pair \(G=(V,E)\) where \(V\) is a finite set of vertexes and \(E\subseteq V \times V\) is a finite set of directed edges composed of ordered tow element subsets of \(V\). By convention we assume that \((v,v)\not\in E\) for all \(v \in V\).
A path in \(G\) is a sequence of vertices \(\langle v_{0}, v_{1}, \dots, v_{n}\rangle\) so that \((v_{i}, v_{i+1})\in E\) for each \(i=0, 1, \dots, n-1\). We say that the path goes from vertex \(v_{0}\) to vertex \(v_{n}\). The number of edges in a path is its length.
1.2 Directed Trees
A directed tree is a digraph that possess a unique vertex \(r \in V\) called the root so that: (1) there is a unique path from \(r\) to every vertex \(v \in V\) and (2) there is no \(v \in V\) so that \((v,r)\in E\).
For directed tree \(T=(V,E)\) and \(v,u \in V\) with \((v,u) \in E\), then \(u\) is called a child of \(v\) and correspondingly \(v\) is called a parent of \(u\). If there is a path from \(v\) to \(u\) in the \(T\), then \(u\) is called a descendent of \(v\) and correspondingly \(v\) is called an ancestor of \(u\).
The out-edges for a vertex \(v\in V\) denoted by \(E_{o}(v)\) are edges that connect \(v\) to its children, or written mathematically \[ E_{o}(v):=\{ (v,u)\in V:(v,u)\in E \}. \] If a vertex \(v \in V\) has no descendents then it is said to be a terminal vertex. All vertices not satisfying this property are said to be non-terminal or intermediate.
The height of a tree \(T\) is the length of the longest path in \(T\).
Lemma: For a directed tree \(T=(V,E)\), if \(v\) is a vertex of \(v\) and \(u\) is a descendent of \(v\) then there is no path from \(u\) to \(v\).
Theorem: For tree \(T=(V,E)\) suppos \(u \in V\) is a vertex and let \[ V(u)=\{ v \in V:v = u~\text{or}~v~\text{is a descendent of}~u \}. \] Let \(E(u)\) be the set of all edges defined in paths connecting \(u\) to a vertex in \(V(u)\). Then the graph \(T_{u}=(V(u), E(u))\) is a tree with root \(u\) and is called the sub-tree of \(T\) descended from \(u\).