Traversability of Networks
Maths Applications (Year 12) - Graphs and Networks
Let’s begin looking at some of the practical applications of networks by starting with the property of traversability. A network is traversable if it can be drawn in one go without taking your pen off the paper without going over the same edge twice, although passing through the same vertex more than once is allowed.
The network diagram A-D is very clearly traversable. You can begin drawing at any vertex and draw the whole network without taking your pen off the paper and without going over the same edge twice, and you will end up back at the same vertex you started at. What about KK-OO below?
The network KK-OO is traversable, but only if you start at vertex KK and end at vertex MM or vice versa.
There is an easy way to determine whether a network is traversable or not without drawing it out. We do this by looking at the degree of each vertex. Remember that the degree of a vertex is the number of edges connected to it, and vertices are termed as either even vertices or odd vertices depending on this number. For the network A-D above, all vertices have a degree of 2, so all vertices in this network are even. However for the network KK-OO, you will notice that vertices LL, NN and OO also have a degree of 2, but vertices KK and MM have a degree of 3 and are so termed odd vertices. For a network to be traversable, it must be connected and have either zero odd vertices or exactly two odd vertices.
Now, let's look at how these properties can be applied to a practical situation in real life. Say the weighted network PP-VV below is a map of trails at a national park you are planning to hike in, with each vertex representing a carpark. You would like to walk all trails in the park, and are trying to work out if you can do so by starting and finishing at the same carpark and also not repeating any trails twice as you don't want walk more than you need to. Is it possible?
Let's go through it together. Firstly, we can see that it is a connected graph. Now let's look at the degrees of each vertex: PP = 2; QQ = 3; RR = 3; SS = 2; TT = 2; UU = 3; VV = 3. Vertices PP, SS and TT are even vertices while vertices QQ, RR, UU and VV are odd vertices. This network is therefore not traversable as there are four odd vertices.
If a network has zero odd vertices (i.e. all even vertices) it can be traversed if you start and end at the same vertex. If a network has exactly two odd vertices, it can be traversed if you start at one odd vertex and end at the other odd vertex.