## Graph Theory

### Introduction

When you work in mapping and other fields that are concerned with revealing spatial patterns, you come to realise how useful it is to understand the basics of some discrete mathematics, such as graph theory. Essentially, graph theory is the study of topological relationships. From a given set of nodes (vertices) and connecting edges (segments or arcs), we can abstract a range of conditions.

Studying systems in this more abstract way has numerous applications that are concerned with spatial arrangements (networks), whether physical, biological, data or social. For example, vehicle route planning, social networks, spatial connectivity and integration of urban spaces, or the spread of COVID-19 through a community. Graph theory is clearly core to the techniques applied in many fields of spatial analysis and practice, including urban morphology and Space Syntax.

### What Defines a Graph?

Most graphs are much more complex, but those shown here illustrate the common forms. The *tree graph* can only flow from the parent (root) vertex to the child vertcies. No two-way or looped connections. It is possible for a single vertex (node) to have a circular edge (link), starting and finishing at the same node — a self-loop — called a singleton graph.

###### Tree Graph

The edges on an *undirected graph* can travel both ways; they are all bidirectional (no fixed origin or destination). This is different to a *directed graph* [1] [2], also called a digraph, as there is a direction of flow (from origin to destination), and only in that direction. However, a directed graph can have a mix of one- and two-way edges [2] due to having an origin and destination.

The last form of directed graph [2] can be confusing as if edges go both ways to vertices, then isn"t that an undirected graph? Why not show it without arrows? There is a mathematical convention and argument in that a graph (G) is made up or object pairs, vertices (V) and edges (E), such that G = (V,E). These can be written as unordered or ordered pairs.

###### Undirected Graph

In the the undirected graph, it doesn’t matter the order of the vertices as unordered pairs:

```
V = {A,B,C,D,E,F}
E = { {A,B}, {A,C}, {B,C}, {B,D}, {B,E}, {B,F}, {D,E}, {E,F} }
```

###### Directed Graph [1]

In the directed graph [1], the order of vertices is significant in ordered pairs and the notation slightly different:

```
V = { A,B,C,D,E,F }
E = { (A,B), (A,C), (B,D), (B,E), (C,B), (D,C) (D,E), (E,F), (F,B) }
```

###### Directed Graph [2]

For the sake of clarity, the directed graph [2] is written as:

```
V = { A,B,C,D,E,F }
E = { (A,B), (A,C), (B,E), (B,F), (C,A), (C,B), (C,D), (D,C), (D,E), (E,D), (E,F), (F,B) }
```

### Eulers Theorem

This special type of graph is created where every edge need only be visited once to traverse the entire graph. A *Eulerian cycle* is a path that traverses across a graph, finishing where it started. This can only be done where all vertices have an odd degree, and you can start from any vertex. A *Eulerian trail* exists where a traverse can only start and end at different vertices, where both have an odd degree. Simply, the degree measure of a vertex is the number of edges starting or terminating at it.

###### Eulerian cycle (above left) and Eulerian trail (above right)

### Four Colour Map Theorem

There's more. You also have the four colour map theorem, that states that no more than four colours are required to colour the regions of any map so that no two adjacent regions have the same color. Graphs, as a mathematical concept, find there way in to numerous mapping techniques and applications.

###### Four Colour Map Theorem

### Summary

Graph Theory is another of those theorems that you may have no knowledge of, or understanding of, but then discover it is fundamental to the workings of the tools you may be using every day. This basic introduction, to what is a very interesting field, has numerous applications in real world situations. Here *agents*, algorithms and weighting start to play a part in the analysis. Vehicle route planning adds weighting to road lengths and class (e.g. A-Road) to find the shortest and/or fastest route from A to B.

However, the application that interests me most, and one that I have employed in projects, is Space Syntax. The science and methodology of Space Syntax provides for the analysis of spatial configurations of all kinds and at all scales, internal and external, in terms of connectedness, integration and visibility. It has been extensively applied in the fields of architecture, urban design and planning, transportation, building work and visitor spaces. It can be used to understand the impacts of spatial configuration and design on aspects of social, organisational and economic performance of buildings and urban areas, and provide evidence to their improvment or otherwise.