A few months ago I wrote an article where I spoke and explained how they work Internet searches through a mathematical theory, the graphs. It is true that this article seemed a bit complicated and we could only get the most out of it in high school classes, even doing a little exercise emulating the famous Google PageRank.
Now my intention is to be able to explain this graph theory in an even simpler way and for that I will use a small game in the classroom. To gamify in our classroom you need a small challenge or problem to mark the objective and the solution, that is why I will use one of the most famous stories that are told in mathematics: the bridges of Königsberg and that is also the birth of graph theory. .
To explain this activity it is best to start by explaining that they are the bridges of Königsberg by means of a little history.
The city of Königsberg (now called Kaliningrad), is a beautiful place located at the mouth of the river Pregolya, in the old East Prussia. This river crossed the city, dividing in several parts, including a small island.
To improve its communication between the different parts of the city, a network of bridges was created, of which the inhabitants of the place were very proud.
In total, there were seven great bridges in Kaliningrad: the blacksmith's bridge, the connecting bridge, the green bridge, the market bridge, the wooden bridge, the high bridge and the honey bridge.
Soon a small game arose among the inhabitants of the place, it was proposed to find out if it would be possible to find a path such that starting with one of the 4 zones, could end up in that area crossing the 7 bridges once and only once, that is, to be able to answer a simple question:
Can you cross all the bridges passing only once for each bridge?
A priori it seems impossible, it is necessary to cross a bridge more than once.
The Queen of Konigsberg posed this problem as a mathematical challenge. It was not until hundreds of years later, when in 1736 the famous mathematician Que was in town working at the Prussian Academy of Sciences, Leonhard Euler (1707-1783) immediately became interested in this riddle and set out to give a solution
What did Euler do?
First, Euler simplified the map of the territory to just a few lines and points, that is, I eliminate everything left on the map.
As we can see, the different territories in which the bridges divided the city became points, that is, in "vertices", and the bridges they became lines, what we call "Edges". It also determines that there is a "start" point and an "exit" point.
Euler managed with this scheme, to study a solution for this famous enigma that The queen of Konigsberg raised as a mathematical problem
To be able to travel the bridges of Königsberg, the "intermediate" vertices must have an even number of edges. That is, they must have a way to enter and a way out. Only the start and end points can have an odd number of edges, because, obviously, We never "enter" the starting point and never "leave" the point of arrival.
To simplify it further and explain it in the classroom, we will imagine a route that we have to travel, we could imagine any route or place to use it as an example in class but to continue with some notes of history, we will choose the only route that made the transatlantic TITANIC on its maiden voyage.
|Origin (Start Point)||Southampton|
|Scale (intermediate point)||Queenstown|
|Destination (Point of Arrival)||NY|
How do we solve it?
You have to leave the starting point once (odd number, blue), enter an intermediate point and exit it (no, red) and end up entering the point of arrival (odd number, green).
And where is the genius of Euler?
In which this method It applies to any problem of this type. With calculating the edges that have the intermediate and extreme points we can know the first If the problem has a solution or not. In the case of the Königsberg bridges, the intermediate vertices have an odd number of edges, so it is absolutely impossible to perform the feat of the proposed exercise.
We move from Euler's mathematics to Augmented Reality.
In order to understand this great mathematical enigma in an even clearer way, we have created the scenario in a real way using the Augmented Reality, even using this scenario interactively in the form of a game.
We must move Leonhard Euler through all the stages of the city and crossing the 7 bridges only once. As an important factor we see that every time the inhabitant crosses a bridge, it disappears to avoid breaking the rules of the mathematical enigma. We can see the game in this video.
We can also play in Virtual Reality
To finish our activity we propose to our students a real journey that can be completed (that is, the opposite of the Königsberg bridges) using the theory we have just studied.
For this we mention these 2 points (tracks) and 2 conditions
- The exercise must be done on a real and current map, using Google Maps or similar. After that, any image modification tool will be used to draw the "future bridges".
- Minimum there must be 7 bridges like in the city of Königsberg
- If the point of arrival and departure is the same, it must necessarily have an even number of edges (one to leave and one to return). This is known as the "Eulerian cycle."
- If, on the contrary, the starting point and the finishing point are different, they must necessarily have an odd number of edges. This is what we know as the “Eulerian way”.
"These studies conducted by Euler were the trigger of the theory of graphs, turning a simple village discussion into a whole scientific discipline. "