From Bridges to Balaclavas: What is Graph Theory and Why should you care?
Introduction
An historical notable problem in Mathematics is the “seven bridges of Königsberg”.
The city in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel river, and included two large islands, Kneiphof and Lomse, connected to each other, and the mainland, by seven bridges.
The Problem
In 1736, Leonhard Euler set out to devise a walk through the city that would cross each of those bridges, once, and only once. With the rigour typical of a Mathematician, Euler specified this logical task unambiguously, to explicitly discount as unacceptable any solutions that involved:
- reaching an island or mainland bank other than via a bridge,
- accessing a bridge without fully crossing it to the other side.
Euler realised that the choice of route inside each land mass was irrelevant, the important feature of a route is the sequence of bridges crossed; this realisation allowed him to re-formulate the problem more abstractly, eliminating all features from his analysis except the list of land masses and the bridges connecting them.
Euler observed that, except for the endpoints of the walk, whenever one enters a land mass by a bridge, one leaves it by a bridge, so that during any walk, the number of times one enters a non-terminal land mass is equal to the number of times one leaves it. If every bridge has been traversed exactly once, it follows that for each non-terminal land mass, the number of bridges touching it must be even.
In so doing Euler not only proved that the 7-bridge problem has no such solution but laid the foundations for Graph Theory.
What are Graphs?
Since only the connection information is relevant, the pictorial representation of the 7-bridge problem may be distorted in any way, without changing the problem itself. Only the existence (or absence) of a bridge between each pair of land masses is significant.
In discrete mathematics, a graph, G(V, E) is a mathematical non-linear data structure used to model pairwise relations between objects; Made up of pairs of sets (V, E) where V is the non-empty set of vertices (also points, or, nodes), connected by the set of edges, E (also links), such that there is a mapping function F : E → V from the set E to the set of ordered, or, unordered pairs of elements of the set V.
Graphs can be undirected, directed, or, weighted.
Undirected graphs: here the edges are associated with an unordered pair of vertices. A graph G (V, E) without a loop and parallel edges is a simple graph. A graph with more than one edge between any pair of vertices is called a multigraph.
Directed graphs: a directed, or digraph, graph G consists of a set of vertices, V, and a set of edges, E, such that each edge, e, in E: (e ϵ E), is associated with an ordered pair of vertices, i.e. each edge has a direction.
Weighted graphs: graphs can have edges containing a weight associated to represent real-world implications such as cost, distance, and, quantity. Weighted graphs could be directed or undirected graphs.
Graph Theory
Graph Theory is the study of graphs. This study across a structure provides answers to problems in layout, networking, optimisation, matching and operation.
Graph Theory is an integral component of Computer Science, Artificial Engineering, Machine Learning, Deep Learning, Data Science, and Social Networks.
Cutting-edge applications of Graph Theory include traffic networks, navigable networks, and optimal routing for response.
Graph Colouring Problems
Graph colouring is a useful technique in which adjacent vertices obtain different colours. The minimum number of colours used for the correct colouring of the graph is an optimisation problem. This has many applications, such as Scheduling/Time-Tabling, Mobile Radio Frequency Assignment, Sudoku, Register Allocation, and Map Colouring.
Real-life Application
Google Maps: Google Maps uses graphs for construction and transport systems. The intersection of two or more roads is considered a vertex, and the road connecting two vertices is considered an edge. Their navigation system uses algorithms to calculate the shortest path between two vertices. In GPS navigation we use different shortest path algorithms such as DFS (Depth First Search) and BFS (Breadth First Search).
Facebook & LinkedIn: These Social Networking sites model their users as a graph in which each vertex is a user-profile. The edge between two users is the fact that they are friends/connected or “follow” one another. Friend/Connection suggestion algorithms use Graph Theory. Facebook is an example of an undirected graph.
Graph Theory is used in Netflix and other platforms, such as Amazon, to enhance recommendations. By representing users and products as nodes and their relationships as edges, Graph Theory helps identify patterns and connections. It enables personalised recommendations by analysing users’ viewing history, ratings, and purchases, with those of other users with similar viewing/purchasing patterns.
“Customers who purchase baseball bats often go on to purchase balaclavas.?”
Constructing a graph of interconnected content, platforms can suggest relevant shows or products based on a user’s interests and the preferences of similar users, leading to a more engaging and personalised experience.
However, these recommendations are based on historic data, they cannot take the creative leap necessary to suggest something new and create outlier data points.
Increasing application of AI (Artificial Intelligence) and ML (Machine Learning) in diverse fields such as Health, Social Science, Manufacturing and Defence, indicates that the Graph-theoretic approach to connections is a very rich research field, as more of the heavy-lifting in mapping out relationships between entities in any given system can be performed algorithmically.
About the Author:
Sharon Mitchell is an AWS Dev Ops Engineer here at Version 1.
