Fun Graph Theory

Initial Example

This is a small town with five points of interest and a series of roads linking them. The points of interest can be called nodes and the roads linking them can be called links. From here, you could assign values to the links (such as distances) and values to the nodes (such as how many roads link them). It should be fairly obvious you can't travel on every road just once, and that's because of how many roads link to each point. The corners all have three linking roads, which is an odd number, and so each of the corners must logically be an endpoint on the journey for this to work. Obviously this is impossible, so you cannot complete such a journey - it's a non-Eulerian path. Reduce the links between them and it becomes possible, however.

Coloured Maps

One of the most well known graph theory problems is the four colour map theorem, which states that any given map can be coloured in with only four colours should adjacent regions not share the same colour, as in the example given above. We assume the theorem works because a computer program in the 1970s went through multiple possibilities and hasn't been proven wrong yet, though many Luddites refuse to accept this proof as legitimate. Either way,

The classic problem

This is rather basic graph theory, of which the most famous problem is the Seven Bridges of Königsberg, where you have this set-up:

There are a series of islands in Königsberg with seven bridges connecting them like this, and you have to cross all of them, only crossing each one once.

 

The picture on the left is a simplified model with the nodes, or islands connected by the various links, or bridges, and the possible routes you can take to get to the next one. The picture on the right is the actual situation, simplified in Paint. From the image on the left, you can see that you can't travel across each bridge just once because you'll end up missing out on one by the end. What was once seen as a very difficult problem was resolved efficiently by Euler, as he noticed that the number of bridges connecting each major island was odd - this problem would only work if you had an even number. From here, graph theory began. The unfortunate thing is that the problem is very much a relic of its time: Königsberg was a major city in Prussia, but now it's the Russian city of Kaliningrad, and most of the bridges were destroyed during World War 2.

The complex problem

Another famous problem in graph theory is the travelling salesman problem. You have a range of nodes and links that are connected and you can only visit each node once (like a Hamiltonian path) before returning to the start in the shortest distance possible. I'll reuse the graph of the town from before for this. Assuming the length between each stop is 1, if you start from the top-left corner, then the minimum distance will obviously be 5. Let's change the distances, however:

 

 

All of a sudden, we have various different possible distances. The nature of this graph means we have to always use one of the horizontal routes, and from a first glance it's obvious we shouldn't take the route of distance 3. As a result, the best route appears to be {1,2,1,2,1}, or length 7. This isn't the only length 7, though - {1,3,1,1,1} also works, so the assumption wasn't always correct. The worst route, meanwhile, could be {2,2,3,2,1}, which is length 10. 

Should the graph be even more chaotic, however, with greater variation in distances and points, it's easier to use bounds to narrow down what the optimal route could be. In this graph, if I was operating a route of the smallest length, I wouldn't mind a route length 8 - it's not too long, even if it's not the shortest. 

This is the classic travelling salesman problem - the practical travelling salesman problem, on the other hand, allows us to travel across each link as many times as possible. I'll let you work that out for yourself.

Epilogue

• Will there be more blogposts on algorithms?

 Maybe - in the meantime, here's a Kruskal's algorithm calculator that I enjoyed playing around with when making this blogpost: https://algorithms.discrete.ma.tum.de/graph-algorithms/mst-kruskal/index_en.html

• Can we have a list of sources used for this blogpost?

Colour Map Theorem:

https://mathworld.wolfram.com/Four-ColorTheorem.html

Königsberg:

https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg (decent introduction)

https://www.britannica.com/science/Konigsberg-bridge-problem

Node image:  https://en.wikipedia.org/wiki/File:K%C3%B6nigsberg_graph.svg

Travelling salesman problem:

Further maths textbook

https://www.britannica.com/science/traveling-salesman-problem

and there may be other sources I have forgotten to list.

There is also additional content over at my new miniblog blog, -b: https://negativeb.bearblog.dev/fun-graph-theory-bonus-content/ - and it discusses a graph theory problem I somewhat made using bus routes.