Understanding graphs, trees, and networks
We will start by defining graphs mathematically, along with any other related definitions, before moving on to consider common ideas about trees, networks, and directed graphs.
Definition: graph
A graph G has two parts. First, V = {v1, v2, …, vk} is a set of vertices, also known as nodes. Second, E is a set of edges, each of which connects some pairs of nodes. We represent a graph as G = (V, E).
An edge is represented mathematically as a set made up of the two vertices it connects. If there is an edge connecting nodes vi and vj, we will call this edge eij = {vi, vj} and we say it is incident to vertices vi and vj.
An example of a graph follows with vertices V = {v1, v2, v3, v4, v5, v6} and edges E = {e12, e13, e15, e23, e24, e26, e34, e35, e45}:
Figure 8.1 – A graph with six vertices, and nine edges connecting them
We can see, for example, the edge connecting vertex 3 (v3) to vertex 4 (v4...
