Embedded Files
Taking a tour of all the edges in a network
Taking a tour of all the edges in a network
The idea of finding a path through a network which uses every edge exactly once is considered one of the first mathematical Graph Theory problems.
In 1736, Leonard Euler wondered whether it was possible to start somewhere in the city of Königsberg and cross each of its seven bridges exactly once.
He found an answer to this question and proved it definitively, laying the groundwork for this topic.
See if you can find a way to use every bridge exactly once before continuing.
Bridges across the river Pregel in the town of Königsberg, in 1736.
Rather than use a map of Königsberg, a network representing the two islands and the two sides of the river shows the important connections. The network has four nodes (the places) and seven edges (one edge for each bridge). There are some multiple edges.
For this topic, we are usually not concerned with weights on edges.
The degree of each node has been added as a label. If your network already has weights labelled, it's a good idea to use a different coloured pen for these degree labels.
A path that uses every edge exactly once in a network is called an Euler path.
A circuit that uses every edge exactly once is called an Euler circuit.
These are sometimes called "edge tours".
We know the total weight of an Euler path or circuit; because it uses every edge exactly once, it is just the sum of all the weights in the distance table.
The seven bridges of Königsberg as a network, with degree labels.
Euler was a very clever mathematician, so he didn't just solve the one problem about these seven bridges in Königsberg. He described a method to quickly figure out whether a connected network has an Euler path or Euler circuit.
Before we look at this method, attempt the following four puzzles. Try to trace along all the edges of the network with one path - start anywhere you like.
You should have found that [a] and [b] have Euler paths, and that [c] has an Euler circuit. We call networks like this traversable.
Network [d] does not have an Euler path or circuit. We call networks like this not traversable.
The property of the network being investigated here is called traversability.
When a start node for the Euler path is specified, we say it is traversable from a node.
There are three cases to consider:
0: Traversable from any point
0: Traversable from any point
If no nodes in a connected network are odd, then the network is traversable from any point.
2: Traversable from two points
2: Traversable from two points
If exactly two nodes in a connected network are odd, then the network is traversable, but only from an odd node.
>2: Not traversable
>2: Not traversable
If more than two nodes in a connected network are odd, the the network is not traversable (from any node).
Euler proved this back in 1736.
The basic idea of the proof is that a tour through the network adds 1 to the degree of the start node, 2 to the degree of each node it passes through along the way, and 1 to the degree of the end node.
If it starts and ends in the same place, then all of the degrees are even.
If it starts at one node and ends at a different node, then those two nodes are odd, and the other nodes are even.
We can't make a traversable network with more than two odd nodes - only the start and end nodes can be odd.
It's a little more complicated to work through the rest of the Euler's proof, that these conditions are also sufficient for a network to be traversable. Regardless, we don't need to know how Euler's proof works for this standard.
If a network is not traversable, or not traversable from the desired start node, tasks often ask to find the 'best' path possible. This will mean either:
using some edges twice;
not using some edges; or
adding a new edge to the network.
Which of these to do depends on the context (do they say "include all the roads", or "don't use any road twice"?). Adding a new edge unlikely to fit well in a road network context - new roads are expensive!
In any case, the edges that are used twice (or not used) should usually be chosen with small total weight. This might require some careful thought about the possibilities available.
Checkpoint
Checkpoint
Is the Königsberg network traversable?
Where could you add a bridge in the city of Königsberg to make the network traversable?
How many odd nodes are there in this network?
Where could an Euler path in the network start?
If one of the edges at node C was removed from the network, would it be traversable?
Draw a network that has an Euler circuit (is traversable from any point). Explain your answer.
Exercises
Exercises
Use a copy of the exercise sheet and draw each network.
Label each node with its degree.
State whether the network is:
traversable from two nodes;
traversable from any node; or
not traversable.
You don't need to include the edge weights for these questions.
Exercise.pdfTasks
Tasks
100 Acre Wood
100 Acre Wood
Task 2: Tigger wants to go along all the tracks to check there are no Woozles, ending at Pooh's house. He would like to know if he has to go along any tracks more than once. Find an efficient route that checks all tracks.
100acre.pdfSherwood Forest
Sherwood Forest
Task 2: The Sheriff of Nottingham wants to start in Nottingham and set out to patrol as many of the roads as possible, looking for Robin Hood's men. He does not want to patrol any road twice (it scares the peasants). Prepare a route for the Sheriff to take, giving reasons for your choice.
sherwood.pdfThe Shire
The Shire
Task 2: Gandalf wishes to be seen across The Shire, and will travel every one of the roads between the notable towns (marked with black circles). Plan an efficient route, which takes every road at least once, starting in Waymoot.
shire.pdfInvestigations
Investigations
(A) Is it always possible to find a path that uses every edge in a (connected) network exactly twice?
(B) Why can there only be an even number of odd nodes in a network?
Key words: tour, Euler path, Euler circuit, traversable, traversable from a node
Google Sites
Report abuse