
A
Graph Theory
A.1 Graphs, Nodes and Arcs
A graph G = (V, A) consists of a non-empty set V of nodes or vertices and a
finite (but possibly empty) set A of pairs of vertices called arcs, links or edges.
Each arc a = (u, v) can be defined either as an ordered or an unordered
pair of nodes, which are said to be connected by and incident on the arc and
to be adjacent to each other. Here we will restrict ourselves to graphs having
zero or one connection between any pair of nodes. Since they are adjacent, u
and v are also said to be neighbours. If (u, v) is an ordered pair, u is said to
be the tail of the arc and v the head; then the arc is said to be directe ...