Topological relationships
When you work in fields that are concerned with revealing spatial patterns and problems, such as in wayfinding, 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); 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 core to the techniques applied in many fields of spatial study and practice, including space syntax and urban morphology.
On another level, graph theory evolved the ‘four colour theorem’ which defines how any map made up of areas or regions, can be coloured up with just four colours, and no two adjacent areas will share the same colour.
What defines a graph?
Most graphs are much more complex, but those shown here illustrate the common (root) 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.
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.
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} }
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) }
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) }
As further examples, Facebook may be considered an undirected graph as ‘friend’ invitations are mutual and two-way; bidirectional. On Instagram, however, if someone follows you, you have the option to not follow them back. As such, the relationship is directional and two edges are created [2]. Either party can change their decision at any time. The World Wide Web (WWW) is an example of a directed graph.
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.
Summary
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 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. It has been extensively applied in the fields of architecture, urban design and planning, transportation, building work and visitor spaces. The study of the impacts of spatial configuration and design on aspects of social, organisational and economic performance of buildings and urban areas is critical to their improvement.
Studio
The Cartographer
A Map-making Practice
Selected Map Works
Mapping Insights
Map Art
Connect
Privacy Policy · Terms
© Yellowfields, 2000–2023
