Bridges in Königsberg
This story is about the Swiss mathematician Leonard Euler (1707 – 1783). While he lived in the Russian town of Königsberg at the Baltic sea, he was thinking about the following problem:
Königsberg is divided into four parts by the river Pregel, and connected by seven bridges. Is it possible to tour Königsberg along a path that crosses every bridge once, and at most once? You can start and finish wherever you want, not necessarily in the same place.
Trying various paths very quickly suggests that it is impossible: you always end up with a bridge you haven’t crossed, but with no way to get there without crossing another bridge twice. But it would take a very long time to try every possible path…
Have a look at these cities and try to find the same kind of paths – crossing every bridge exactly once. If you can find one path, try to find a second one in the same city.
Not all cities are possible. Read on for the explanation!
Before we can solve the Königsberg Bridges problem, we have to think about an area of mathematics called graph theory.
A graph is a collection of vertices (points) that are connected by edges (lines). Some graphs can be directed, which means the lines have an arrow and only go in one direction. Some (rather boring) graphs can have no edges at all, the edges can overlap and there can be many edges coming out of the same vertex.
Here is a very simple question we could ask about graphs:
Which graphs can be drawn without lifting the pencil off the paper and without drawing any line twice?
Leonard Euler observed that some graphs can be drawn in such a way, some even have many possibilities, while others can’t. Try the following examples and see whether you can find a pattern.
Here are a couple of simple graphs. Determine which ones can be drawn without lifting the pencil and drawing a line twice. Now think about how many edges meet at every vertex and try to find a pattern.
It is possible that whether a graph can be drawn or not depends on the number of vertices with an odd number of vertices. Can you work out what’s going on? Read on to see the explanation…
Not all graphs can be drawn. Read on to see the explanation…
Whether a graph can be drawn or not depends on the number of vertices with an odd number of edges. Above you may have observed that graphs which have more than two “odd” vertices can’t be drawn in the way we want. For the explanation we have to look at one individual vertex and see what happens to it as we connect the vertices of the graph.
Initially there are no edges going through our vertex. At some point we will connect our vertex to the remainder of the graph, and unless it is the final vertex of the path we draw, we will draw another edge going away from our vertex. So in total we have added two edges.
Maybe we will return to our vertex a second time. But again we have to move away again, so we add two more edges. You see that edges are always added in pairs so we know that if vertices in our graph have an odd number of edges, the graph can’t possibly be drawn.
The only exceptions are the vertices where we start and where we finish our path. If we start and end at two different vertices, only these two will have an odd number of edges. If we start and finish at the same vertex, then all vertices are even.
This makes it possible to determine whether graphs can be drawn just by looking at them – and we are even told where to start!
Bridges in Königsberg revisited
Having solved the Drawing Graphs problem, we can now solve the Königsberg Bridges problem by converting the map of Königsberg into a graph: Every “island” is represented by a vertex, and every bridge connecting two islands is represented by an edge connecting the two points. Here is what we get:
Finding a tour through Königsberg that crosses every bridge, but not twice, is exactly the same as finding a way to draw the graph without crossing a line twice. If we count the number of edges that meet at each vertex, we see that there are more than 2 odd vertices. Therefore such a drawing or tour does not exist in Königsberg.
Now you can go back to the city maps in the first exercise, convert them into graphs and determine whether they can be toured or not.
Graph theory is now a very important part of mathematics with countless applications in technology, computing or science. Some important ideas in graph theory are outlined in the following sections.
Travelling Salesman Problem
When trying to find a route for the Königsberg Bridges problem we didn’t think about how long it would take. But in many cases this is of great importance: and we want to find the shortest possible route. This is called the Travelling Salesman problem:
A salesman has to visit a number of cities to deliver items. What is the shortest route that connects all the cities?
Of course we need to know how many cities there are and what the distances between any two cities are. But even with all that information the Traveling Salesman problem is still very difficult. We could just try every possible path, but with many cities this becomes very impractical.
If we have 10 cities to visit there are more than 3 million possible orders to visit them in! Testing 100 cities in that way would take longer than the age of the universe!
Visiting 100 cities does not happen very often in real life but it does happen if you plan airline networks or want to optimise production lines in factories. There are many other important application which you can read about below.
Unfortunately mathematicians have not been able to find a way to solve the Travelling Salesman problem in a much more efficient way. Problems like this, which take a very long time to solve using a computer, are called NP-hard (non-deterministic polynomial-time hard)
If we are connecting n cities there are n! (n-factorial) different routes (this is explained in the article on Combinatorics). The most efficient computer algorithm takes of the order of 2n steps. This is not very useful since the number of steps increases exponentially with n.
Instead there are approximate algorithms to solve the Travelling Salesman problem and similar ones. These are much faster and usually give very good results, but sometimes they miss the very best solutions.
Travelling Salesman Simulator ... coming soon
Four Colour Theorem
Here is another famous problem that is related to Graph Theory:
We want to colour a map of countries so that no two adjacent countries get the same colour. What is the maximum amount of colours we need to be able to colour any map?
Here is an example that works with four colours. Notice that it wouldn’t work with only three colours: eventually we would always arrive at a point where we cannot colour a state because all three colours have already been used on its neighbours.
But are four colours always enough? Or are there certain maps for which we need at least five colours? In 1852, Francis Guthrie together with Augustus De Morgan (1806 – 1871) conjectured that four colours are enough to colour any map: the four colour theorem.
And while the problem is easy to understand, proving it seemed to be rather more difficult. There were several early proofs, and in some cases it took more than 10 years until a mistake was found. It is reasonably simple to prove that five colours are always enough – but the four colour problem remained unsolved for many years.
The four colour theorem can be translated into graph theory: we convert every country into a vertex and whenever there is a border between two countries we connect their vertices with an edge. Now we want to colour a graph so that vertices connected by an edge get different colours.
Mathematicians thought about the four colour theorem for a very long time. Unfortunately they were neither able to find a map for which 4 colours are not enough, nor were they be able to come up with a proof that four colours are always enough. Any map/graph we try does work with four colours, but of course we can’t try all infinitely many maps.
In 1976 the mathematicians Kenneth Appel and Wolfgang Haken considered a total of 1936 smaller “subgraphs” which make up any graph corresponding to a map. They checked each of these cases on a computer and deduced that the four colour theorem is indeed true for any map.
This was the first significant example in history when a computer was used to solve a mathematical theorem. This was subject to much controversy: how can you be absolutely sure that the computer didn’t make a mistake? Today there are a number of simpler and more trusted proofs.
Colouring Maps Game ... coming soon
Remember Leonard Euler, the mathematician who invented Graph Theory? He played around with many different graphs and discovered another interesting property related to the number of vertices, edges and faces. This applies to planar graphs, graphs which can be drawn so that no edges overlap unless they meet at a vertex.
Click on the button below to count the number of vertices, edges and faces in these graphs:
|Faces + Vertices||11||10||13||21|
If you have a look at the last two rows of the table above you will notice that “faces + vertices” is always one more than the number of edges, or that
faces + vertices = edges + 1
Euler managed to prove that this is true for all planar graphs, and it is known as Euler’s formula.
In the article on Polygons and Polyhedra we found a very similar formula for the number of edges, vertices and faces of 3-dimensional solids, but the 1 in the equation above was replaced by a 2. We could imagine that 3-dimensional polyhedra are graphs on the surface of a sphere. We say that the Euler Characteristic of a flat surface is 1 and the Euler Characteristic of a sphere is 2.
Applications of Graph Theory
Everything in our world is linked: cities are linked by street, rail and flight networks. Pages on the internet are linked by hyperlinks. The different components of an electric circuit or computer chip are connected and the paths of disease outbreaks form a network. Scientists, engineers and many others want to analyse, understand and optimise these networks. And this can be done using graph theory.
For example, mathematicians are tying to apply graph theory to road networks, trying to find a way to reduce traffic congestion. An idea which, if successful, could save millions every year which are lost due to time spend on the road, as well as the enormous environmental impact. It could also make life safer by allowing emergency services to travel faster and avoid car accidents in the first place.
These Intelligent Transportation Systems could work by collecting location data from smartphones of motorists and telling them where/how fast to drive in order to reduce overall congestion.
Graph theory is already utilised in flight networks. Airlines want to connect countless cities in the most efficient way, moving the most passengers with the fewest possible trips: a problem very similar to the Travelling Salesman.
At the same time, air traffic controllers need to make sure hundreds of planes are at the right place at the right time and don’t crash: an enormous task that would be almost impossible without computers and graph theory.
One area where speed and the best connections are of crucial importance is the design of computer chips. Integrated circuits (ICs) consist of millions of transistors which need to be connected. Although the distances are only a few millimetres, it is important to optimise these countless connections to improve the performance of the chip.
Graph theory also plays an important role in the evolution of animals and languages, crowd control and the spread of diseases.
In recent years, there has been another important use of Graph Theory: the internet. Every page in the internet could be a vertex in a graph, and whenever there is a link between two pages, there is an edge between the corresponding vertices. The resulting graph is of course very, very large.
Early web search engines had a very big problem: they could search the web for a particular keyword, but they couldn’t determine whether a page is “good” or just spam. If you searched for ‘London’, you might get hundreds of websites of small shops in London, or people who live there, before the official london.gov website.
Google found a solution to this: any page that is very good will have many other pages linking to it. Pages that are rarely visited, or not very interesting, will be very “lonely” in the internet graph with only few other pages linking to it. This gives a way to rank websites and allows Google to display the best results at the beginning
There is a another digital graph, of which you yourself are a part: Facebook. All the users form vertices and whenever two users are friends they are linked by an edge. Graph theory can help web developers improve the performance of social networking sites, and it can help us understand Facebook better.
If I were to choose two users of Facebook completely at random, how many of these friendship edges do I need to get from one to the other? 10? 100? Surprisingly the answer, on average, is only six. On average you are less than six friends away from any other Facebook user: that’s globalisation!
Experiments have been conducted to test this and the longest distance ever found on Facebook was only 12. The number of Degrees of Separation has inspired countless writers and film makers. How many degrees are you away from the Queen? Or the American president? Nobody knows the exact answer, but it is probably a lot less than you think!