How an 18th century Maths puzzle solves 21st century problems
This is a guest blogpost by Emil Eifrem, CEO, Neo4j, in which he explains how an elegant solution to the mathematical puzzle to find the most efficient way of traversing the bridges in Prussia’s Koenigsberg resulted in graph theory
It’s the anniversary this month (15 April) of Swiss mathematician Leonhard Euler’s (1707-1783) birth. While some of us already know him for introducing huge chunks of modern mathematical terminology and breakthrough work in mechanics, fluid dynamics, optics and astronomy, more and more of us are beginning to appreciate him for one of his lesser known achievements: inventing graph theory.
The story begins with Euler taking on a popular problem of the day – the “seven bridges of Königsberg” problem. The challenge was to see whether it was possible to visit all four areas of that city while only crossing each bridge once.
Formalising relationships in data to reveal hidden structures
To get his answer, Euler was able to abstract the problem. And today, we still talk of a Eulerian path being defined as one where every node in a network is visited exactly once, just as the puzzle demands, making a proper cycle if you start and finish at the same place.
This has since been applied, very successfully, to derive the most efficient routes in scenarios such as snow ploughs and mail delivery, but Eulerian paths are also used by other algorithms for processing data in tree structures. His key insight was that only the connections between the items in the case were relevant. Publishing his solution in 1736 he created a whole new sub-set of mathematics – a framework that can be applied to any connected set of components. He had discovered a way to quantify and measure connected data that still works today – and because of this foundational work we can also use his way of formalising relationships in data to reveal hidden structures, infer group dynamics, and even predict behaviour.
It wasn’t until 1936, two hundred years later, when the first textbook was written on what Euler did with the Seven Bridges problem that the concept of graphs came into circulation. It took 40 more years until network science as a discipline and applied graph analytics began to emerge.
Looking at real-world puzzles analytically
Fast forward to today: Euler gave us a powerful framework, but graphs, in software terms, only really became prolific in today’s interconnected, data-driven world. Our unprecedented ability to collect, share and analyse massive amounts of connected data, accompanied by an unrelenting drive to digitise more and more aspects of our lives as well as the growth in computing power and accessible storage, presents us with the perfect context for lots of networks to emerge. These networks contain lots of information in them that we can tease out using graph techniques.
Euler is well known to generations of mathematicians and computer scientists – but even among those who are familiar with him, his ideas on graphs aren’t as well known as they should be. Yet, every graph database user is so indebted to him for his insights. Just as Euler’s life’s work was about looking at real-world puzzles analytically, so the graph software developers of today are solving highly complex, real-world issues, in areas such as AI, Machine Learning, sophisticated recommendations and fraud – and finding practical, graph-based ways to fix them.
Here’s to the man who solved the Seven Bridges problem and gave us a great way to understand and improve the world. Happy 312th birthday, Herr Euler!