A graph is a set of N nodes (or vertices) and E edges.
Each element of E is a pair of nodes (u,v),
which means there is an edge (or arc) between u and v.
- In a directed graph (or digraph),
each edge (u,v) is an ordered pair,
and there is an arc from u to v.
- u is a predecessor of v
- v is a successor of u
- In an undirected graph, each edge is an unordered pair,
and there is an undirected arc between u and v.
- u and v are said to be adjacent
- In a weighted graph each edge has an associated value
- A path in a directed graph is a list of nodes (v1, v2,...,vn)
- there is an arc from v(i) to v(i+1), for all 1 <= i < n.
- the length of the path is the number of arcs in
the path (n-1)
- A cycle in a directed graph is a path of length >= 1
that begins and ends with the same node.
- a path of length 0 is not a cycle
- if there is an arc from a node v to itself, there is
a cycle v -> v
- A cyclic graph is a graph that has at least one cycle;
an acyclic graph has no cycles.