V 2 and E1 E2.
A directed graph G is a pair (V, E), where V is a finite set and E is a relation on V . The elements of V are called nodes or vertices. The elements of E are called edges or arcs.
u is a predecessor of v, and v is successor of u, in G if (u, v) is an edge of G. The graph is said to be ordered if some ordering is assumed on the predecessors of each node, and on the successors of each node.
A path in G is a sequence v1, . . . , vn of nodes such that vi is a successor of vi-1 for i = 2, . . . , n. The length of the path is n - 1. The path is a cycle if n > 1 and vn = v1.
A graph G1 = (V 1, E1) is said to be a subgraph of a graph G2 = (V 2, E2), if
V 1 V 2 and E1 E2.
Each graph G = (V, E) can be represented by a diagram of the following form. For each node v in V the graph has a corresponding geometric shape (e.g. period, circle). For each edge (u, v) in E the graph has an arrow from the geometric shape corresponding to u to the geometric shape corresponding to v. Whenever the graphs are ordered, the predecessors and successors of each node are drawn from left to right in their given orders.
A directed graph is said to be acyclic if it contains no cycles. An acyclic graph is said to be rooted if exactly one of its nodes, called the root , has no predecessors. A node in a graph with no successors is called a leaf . A rooted, acyclic, directed graph is called a tree if each of its nodes, excluding the root, has exactly one predecessor.
In general, a rooted acyclic graph is drawn with the root on top and the arcs pointing downward. The directions on the arrows are omitted.