mikeem em's Bookmarks tagged postman →  View Popular

•  First, we have to identify the odd vertices, B, D, E and F.

•  Next, we have to list all possible pairings of these; BD and EF, BE and DF, BF and DE.

•  For each of these three sets of pairings, we have to find the shortest distances between each pair of odd vertices.

•  For BD and EF, we have (6+3)+(1+8) = 21, from the diagram, going via G in both cases (Dijkstra's algorithm could be used, but inspection is fine here for such a small network).

•  For BE and DF, we have (6+1)+(3+8) = 18, from the diagram, going via G in both cases again.

•  Finally, for BF and DE, we have (7+2)+5=14, from the diagram, going via A for BF and direct for DE.

•  Comparing all possible sets of pairings, we find that BF and DE is the set of pairings that should be repeated in the solution. This gives the network shown below.

We can now apply the Fleury's algorithm to the network, knowing that the solution found will be optimal. With a starting point at A, one possibility would be the following.

Note also that by considering this algorithm, it is relatively easy to see how to modify Fleury’s algorithm for finding an Euler circuit in a graph with two odd vertices if it is necessary to return to the starting vertex. We would simply construct an extra path between the two vertices, and this path would represent the extra distance that we would need to travel in order to be able to go back to the start. Clearly in this case the solution would no longer be a semi-Eulerian circuit (nor would it be an Eulerian circuit, as we are effectively traversing a part of the network twice to accommodate the desire to return to the starting point).

Use Fleury's Algorithm just as stated above EXCEPT always start at one of the odd vertices.

The path produced by this modification of Fleury's algorithm is always a semi-Eulerian cycle for the reasons discussed previously.

We must start at one of the odd vertices, let us say D.

•  From here, we can select to go to any of the vertices E or G. Let us select G, as shown in the diagram.

•  Then we will traverse edge GC.

•  Next, we are forced to select CB, even though it is a bridge for the remaining edges at this stage.

•  From here, we will go to G, and then back to D (allowed as GD is not a bridge for remaining edges).

•  Then we will traverse the edge DE (although we know we must finish at vertex E, this is allowed, as DE is not a bridge for remaining arcs, and it is clear from the diagram that we are able to return later as there are three edges incident upon E).

•  Continuing to apply the algorithm, we get EG, GF, FA, AB.

•  At B, we have to select edge BF, because it is the only remaining edge leading out from B, although it is a bridge.

•  Finally, we take edge FE to finish at E, the other odd vertex.

The algorithm is as follows:

•  Pick any vertex as a starting point.

•  Marking your path as you move from vertex to vertex, travel along any edges you wish, except do not travel along an edge that is a bridge for the graph formed by the edges that have yet to be traversed unless you have to .

•  Continue until you return to your starting point.

Following the algorithm, then:

•  I will arbitrarily choose A to be my starting vertex.

•  From here, I have a choice of which edge to travel along, as neither the edges AB nor AF are bridges. I will select AB.

•  Next, I will choose to travel to F via the edge BF, which is again valid under the bridge constraint.

At the next stage, it would appear that I have three choices of arc to travel along. However, if we consider only the remaining edges that are not yet included in the solution, we can see that FA is now a bridge, and so we must not select this choice (we can now see why this rule works now; we would be “trapped” at A if we selected the edge FA, having to include the same arc twice). We will choose FE arbitrarily from the remaining options.

•  We will now continue our circuit without complication as there are no bridges for remaining arcs, using edges ED, DG, GD.

•  Note now that we are at D that we only have one arc choice, DE. This is a bridge for remaining edges, and so normally would not be allowed. However, as it is the only option, we must select it, as the algorithm states. This will happen many times throughout the remainder of the application of the algorithm. Each time, we are leaving a vertex for the final time.

•  Finishing off the algorithm with the bridge constraint gives the inclusion of edges EG, GC, CB, BG, GF, FA.

•  Thus, we have an Euler circuit through our network as required. This has been marked on the original network diagram shown below in green.

This algorithm can be applied to any network only containing vertices of an even degree.

It is interesting to note that Euler never published an algorithm for finding an Euler circuit, but only provided a method of determining if one existed or not

Although this problem is not identical to the Chinese Postman Problem, there are many similarities, and indeed Euler's analysis of the problem eventually led to the algorithm commonly used to solve it.