Have you heard the true story of seven bridges of Konigsberg? The famous mathematician from the 18th century solved the enigma of crossing all bridges in one route. But, let’s start from scratch so we can get the bigger picture.
Konigsberg (now Kaliningrad) was a name of a city in Prussia, Germany back in 18-th century, until 1946. (In World War 2 it was occupied by Soviet Union and changed a name in Kaliningrad). It is located in on the coast of Baltic Sea. Though the whole city flows a river Pregel. This river flows in such way that in the middle of it lies an island and after passing the island, the river divides into two parts.
People build seven bridges so they could easily and quickly move around the city. Since people walked through there daily, they started to wonder if they can walk around the whole town, cross all the bridges only once and still walk over every bridge. People were quite intrigued by this question. Bridge looks like this:
The different areas are connected by seven bridges. We’ll mark them with a, b, c, d, e, f and g.
Let’s say there are four friends A, B, C and D living in different areas. They all wanted to know can they walk through the whole town, visit all areas and cross every bridge exactly one time and come back to their home.
This problem was solved by famous Swiss mathematician Leonhard Euler. He was very respected mathematician so people trusted him with this problem.
He approached this problems by imagining areas of land separated by the river into points connected with bridges or curved lines. This is how he represented this problem:
Now that he drew this he saw that the walking through every bridge is equivalent to our drawing with a pencil without lifting it of of the paper.
From this exact problem the foundation of graph theory was developed. Euler also set few new definitions:
A network is a kind of diagram where we have one or more vertices connected with non-intersecting curves.
Vertex is called off if it has an odd number of arcs leading to it. If it has even number of arcs, it is called even.
An Euler path is a continuous path that uses every edge of a graph once and only once.
If a network has more than two odd vertices, it does not have an Euler path.
This is how Euler solved this problem. Since every vertex here has an odd number of edges, it does not have an Euler path.
Let’s try an example with some simpler stuff you know from the beginning you can draw in just one stroke.
In these examples, you can start from any point you want, you could still finish this path.
The more complicated our shapes are, the more difficult for us is to see can we draw it without lifting the pencil of of the paper.
If a character can be drawn in one stroke, we say that it has an Euler path.
Now let’s think just like Euler thought. We should see what kind of a relationship do the vertices and edges have with the ability to draw Euler path. We’ll sort out vertices according to the number of edges that go through that vertex.
We can see, that in these, simple diagrams that we determined they have Euler path, all the vertices are even.
In general, all diagrams whose vertices are even has Euler path.
Let’s start with adding some odd vertices. Here we can see that we have four even vertices and two odd. Try to draw Euler path in this diagram:
We can also draw Euler path on every diagram that has exactly two odd vertices.
Let’s add even more odd vertices. Try to find Euler path yourself on the following diagrams.
From this we get to the following conclusion.
A network or a graph has an Euler path if the number of odd vertices is either zero or two.
This is how Euler solved this problem. Since four vertices here has an odd number of edges, it does not have an Euler path.
From this exact problem the foundation of graph theory was developed.
Introduction to Graphs
Every graph consists of the set of vertices and set of edges – connectors of vertices. If said otherwise, graph is final which means that we can count how many vertices and edges a certain graph has.
We say that a graph is simple if every two vertices are connected only by one edge and there are no loops. Loops are edges that connect vertex with itself.
A graph that looks like a broken line that connects points in a line is called path.
Closed path is called cycle.
Complete graph is a graph in which every two vertices are connected by one edge.
Graph is connected if every two vertices are connected by some path.
Connected path without cycle is called the tree.