Definitions

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 (weight).

Definitions (cont)

• A path in a directed graph is a list of nodes (v1, v2,...,vn) such that

  • 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.