Once upon a time…
To find out how we got here, we first need to take a trip back in time.
It’s 1736, in Königsberg, Prussia.
Leonhard Euler is presumably sitting at his desk, with a dilemma. Kongsberg (modern day Kaliningrad, Russia) is divided by the Pregel River into four sections which are connected by seven bridges.
The question that Euler is pondering is: Can we take a walk through the city that would cross each of the seven bridges only once?
Foundation for graph theory
He eventually solved the problem by reformulating it, and in doing so laid the foundations for graph theory.
He realized that the land masses themselves weren’t an important factor. In fact, it was the bridges that connected the land masses that were the most important thing.
His approach was to define the problem in abstract terms, taking each land mass and representing it as an abstract vertex or node, then connecting these land masses together with a set of seven edges that represent the bridges. These elements formed a “graph”.
Applying the theory
Using this abstraction, Euler was able to definitively demonstrate that there was no solution to this problem. Regardless of where you enter this graph, and in which order you take the bridges, you can’t travel to every land mass without taking one bridge at least twice.
But it wasn’t a completely wasted effort. Although graphs originated in mathematics, they are also a very convenient way of modeling and analyzing data. While there is certainly value in the data that we hold, it is the connections between data that can really add value. Creating or inferring relationships between your records can yield real insights into a dataset.
Fast forward 300 years and these founding principles are used to solve complex problems including route finding, supply chain analytics, and real-time recommendations.
Check your understanding
Who is the inventor of graph theory?
-
✓ Leonhard Euler
-
❏ Emil Eifrem
-
❏ Charles Koningsberg
-
❏ Euclid
Hint
He described the Seven Bridges of Konigsberg problem and that it had no solution.
Solution
Oops! You have fallen at the first hurdle. Leonhard Euler was the inventor of graph theory back in 1736.
Summary
In this lesson you learned how graph theory was invented. Next, you will learn about the elements that make up a graph.