{"id":183,"date":"2020-04-08T11:05:35","date_gmt":"2020-04-08T11:05:35","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/edward-mellor\/?p=183"},"modified":"2020-04-30T14:33:27","modified_gmt":"2020-04-30T14:33:27","slug":"the-seven-bridges-of-konigsberg","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/edward-mellor\/2020\/04\/08\/the-seven-bridges-of-konigsberg\/","title":{"rendered":"The seven bridges of K\u00f6nigsberg"},"content":{"rendered":"\n

During the spring term at STOR-i we were given the opportunity to work on two independent projects with the guidance of an academic supervisor. My first research topic was Extreme Value Theory with Emma Eastoe<\/a> and my second was on Optimal Patrolling with Kevin Glazebrook<\/a>. I plan to briefly discus both these projects in future blog posts. <\/p>\n\n\n\n

To be able to talk about Optimal Patrolling we will need a basic understanding of graph theory. In this context, the word graph does not mean a plot, with two axis and line showing the relationship between two variables. Instead a graph is an way of repressing and visualizing connections. This is best explained by example and so in this post, I will talk the problem which first introduced me to this type of graph. <\/p>\n\n\n\n

The Pregel River divides the city of K\u00f6nigsberg into four landmasses as shown below. Seven bridges (shown in black) connect these landmasses. The problem is then to find a route around the city visiting each of the four landmasses by crossing each of these bridges exactly once. No other means of crossing a river is permitted.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

In 1736 a mathematician called Leonard Euler proved that the problem has no solution. A detailed explanation of the proof is given here<\/a> by the Mathematical Association of America. <\/p>\n\n\n\n

The general idea is as follows:<\/p>\n\n\n\n