-
a (directed) graph G = (N,E) consists of a set N of
nodes and a set E of edges
- each edge in E is an (ordered) pair of nodes
(x,y), where x is the source and y
is the target
- a path from x1 to
xn is a sequence of edges
(x1, x2), (x2, x3), ... ,
(xn-1, xn)
- the length of a path is the number of edges in it
- a node r is a root for graph G if there
is a path from r to every other node in G
- a cycle is a path from a node to itself
- a graph with no cycles is called acyclic
