Bayesian Networks, 2nd Edition

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 directed from u to v, and is usually represented with an arrowhead in v ($u\to v$). It is also said that ...