Summary of Chapter 4

1 A graph is traversable if it is possible to traverse (travel along) every arc just once without taking your pen from the paper.2 A graph is traversable if all the valencies are even.3 A graph is semi-traversable if it has precisely two odd valencies. In this case, the start and finish point will be the two vertices with odd valencies.4 A graph is not traversable if it has more than two odd valencies.5 The route inspection algorithm can be used to find the shortest route that traverses every arc at least once and returns to the starting point.6 If there are only two odd valencies, repeat the shortest path between them and add it to the network.7 If there are more than two odd valencies, consider all possible complete pairings, select the one that gives the smallest total, then add this pairing to the network.

Page 1