In this article, we have collected all the articles concerning algorithms and the mathematical theory of graphs. Enjoy!
In the first and the second part of our summer reads last week we collected some articles on the broad topic of technology and computation, and interviews and personal blog posts respectively. But there would be no Network Pages if we wouldn't pay attention to modern research into algorithms and graphs - a mathematical concept used to study networks.
Four colors to paint them all
A mathematician once told me that problems that are very simple to state can be very deceiving, and sometimes turn out to be extremely difficult to solve. One such problem was the Four Color Problem. In this article, we take you back to London, October of 1852, and into the scripts of mathematics student Francis Guthrie who was puzzling with this problem. A problem that would need more than a century to be solved!
A traveler trying to visit them all
If you want to read more about the Traveling Salesman Problem. Suppose you are running a delivery service. You have a single truck and each day you must deliver a large number of parcels to various cities throughout the country. Then you face the following problem: in which order should you visit the cities? In other words, you want to find a round-trip that starts at the depot where the parcels are kept, then visits each of the given cities, and finally returns to the depot. Such a round-trip is called a tour of the given cities. Of course, the goal is to find a tour with minimum travel cost. Here, travel cost can refer to the average time it takes to follow the tour, or the total length of the tour. Computer scientists call this problem the Travelling Salesman Problem, or TSP for short. You may think that if we know the cities to be visited and the travel costs of the roads connecting them, then a computer can easily compute a shortest tour. But the fact that TSP is so simple to state is deceptive: it turns out finding the best tour is extremely difficult, even with state-of-the-art computers. Want to know why? Read this article.
And if you want to read how the optimal tour between 57,912 national monuments in the Netherlands was computed, then you should have a look at this article!
Gossip, DNA and graphs
For those of you who want to learn about percolation theory and see a beautiful, but more abstract, result from mathematics you can have a look at this article.
Or maybe read how DNA-assembly is related to problems from graph theory? Then have a look at this article!
Enigma: a complexity titan
If you want to learn how the German encryption machine Enigma worked and how the British managed to crack it then have a look at this article!
Next week the fourth and last part of our summer reads: articles on applications of mathematics in real-world problems!