Definition:  A directed graph is a pair G = (V, E) where V is a finite set of vertices and E ⊆ V × V a relation on V, the set of edges.

Example:  G₁ = (V, E)   with   V = {0, 1, 2, 3, 4}   and   E = {(0,1), (0,2), (3,0), (2,0), (1,2)}

Definition:  Let G = (V, E) be a graph and u ∈ V be a vertex. A vertex v ∈ V is called adjacent to u, if there exists an edge from u to v, i.e. if (u, v) ∈ E.

The out-degree o(u) of a vertex u is the number of vertices v adjacent to u, i.e.

o(u)  =  | { v |  (u, v) ∈ E } |

The in-degree i(u) of a vertex u is the number of vertices v it is adjacent to, i.e.

 i(u)  =  | { v |  (v, u) ∈ E } |

A vertex u is isolated if  o(u) = i(u) = 0.

Example:  In G₁ vertex 0 is adjacent to vertex 3; vertex 2 has out-degree 1 and in-degree 2. Vertex 4 is isolated.

Definition:  A walk in a graph is a finite sequence of edges

p  =  (u₀, v₀) ... (u_m-1, v_m-1)

with   m ∈ ℕ₀   and   v_i-1 = u_i   for all   i ∈ {1, ..., m-1}.

m is the length of the walk. The walk of length 0 is called the empty walk. Vertex u₀ is called start vertex of p, vertex v_m-1 is called end vertex of p. All other vertices of p are called inner vertices of p.

Example:  

p₁  =  (3,0) (0,2) (2,0) (0,2)

p₂  =  (0,1) (1,2) (2,0)

p₃  =  (3,0)

p₄  =  (3,0) (0,1) (1,2) (2,0)

are walks in the above graph G₁.

Walk p₁ has a length of 4, walk p₃ has length 1. In walk p₂ vertex 0 is start and end vertex. In p₄ vertex 0 is inner vertex and end vertex.

Definition:  Let   p  =  (u₀, v₀) ... (u_m-1, v_m-1)   be a walk in a graph G.

• p is a trail if it contains each edge at most once, i.e. if all (u_i, v_i) are different (i = 0, ..., m-1);
• p is called a circuit if it is closed, i.e. if  v_m-1 = u₀;
• p is a path, if it contains each vertex at most once, i.e. if all u_i among each other and all v_j among each other are different (i, j = 0, ..., m-1);
• p is a cycle, if it is a closed path, i.e. if it is a circuit with no repetitions of vertices.

Example:  In G₁ walk p₁ is not a trail since it contains edge (0,2) more than once. Walk p₄ is a trail but no path since it visits vertex 0 more than once. Walk p₂ is a circuit and even a cycle.

Definition:  A directed graph T = (V, E) is a tree if

• it contains no cycles,
• there is exactly one vertex r with in-degree 0, the root of the tree, and
• all other vertices have in-degree 1.

Definition:  Let T be a tree with root r. A vertex v is called a direct descendant of a vertex u, if it is adjacent to u, i.e. if there is an edge from u to v. A vertex w is a descendant of u, if there is a non-empty path from u to w.

A vertex b is a leaf if it has no descendants; all other vertices are inner vertices of T.

The depth d(v) of a vertex v is the length of the path from the root r to v. The depth d(T) of the tree is the maximum depth of all vertices.

Definition:  A tree T is a binary tree if each vertex has an out-degree of at most 2.

A binary tree is called almost complete if

• all vertices of depth  <  d(T)-1 have out-degree 2, and
• at most one vertex has out-degree 1.