Mathematics for Electrical Engineering and Computing

19

Graph theory

19.1 Introduction

A graph consists of points, called vertices, and lines connecting them, called edges. They can be used to represent many diverse situations, for example five cities and five roads connecting them as in Figure 19.1. The same graph could represent some people and the edge connections could represent those people who do business with each other.

Figure 19.1 Five cities with five roads connecting them represented by a graph.

Sometimes the relationship is ‘one-way’, for instance, in the case of a network of one-way streets, or a graph representing a circuit where the arrows on the edges represent the current flow. In this ...