Play as Webslides

mikeem em's List: Mathsmodels

THE CHINESE POSTMAN PROBLEM - HISTORY OF PROBLEM

people.bath.ac.uk/...historyofproblem.htm - Preview

chinese exam maths postman on 2007-12-16
- Euler wanted to discover, was whether it would be possible to cross all the bridges in a circuit without crossing the same bridge twice . Euler also wondered whether it was possible to end up in the same place one started from, having crossed all the bridges in a circuit, i.e. whether there existed a complete circuit across all the bridges.
- 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.
- 1 more annotations...
- - The Chinese Postman Problem itself gained its name because it was proposed by Mei-Ko Kwan, a Chinese mathematician, in 1962. It is often seen under the alternative and more modern name, of the “Route Inspection Problem”.
THE CHINESE POSTMAN PROBLEM - FLEURY'S ALGORITHM

people.bath.ac.uk/...fleuryalgorithm.htm - Preview

algorithm exam maths postman on 2007-12-16
- 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.
- Here, the second point is effectively saying that you should not go back to the starting vertex until you have to, i.e. right at the end of the construction of the path, as required.
- 5 more annotations...
- - Let us see an example of this algorithm at work. Here, I have invented a network that has seven vertices, all of which are of an even order. It therefore satisfies the conditions for Fleury's algorithm to work.
  - 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.
THE CHINESE POSTMAN PROBLEM - MODIFICATION OF FLEURY'S ALGORITHM

people.bath.ac.uk/...modfleuryalgorithm.htm - Preview

algorithm exam maths postman on 2007-12-16
- 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.
- 3 more annotations...
- - 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.
  - This is what we would have expected from our earlier analysis, and what the algorithm is designed to do, so we have applied it correctly. The semi-Eulerian circuit achieved is shown in green on the diagram below.
THE CHINESE POSTMAN PROBLEM - ALGORITHM FOR NETWORKS INVOLVING ODD VERTICES WITH DISCUSSION

people.bath.ac.uk/...oddnetdisc.htm - Preview

algorithm exam maths postman on 2007-12-16
- It may well be the case that the network we are dealing with does indeed contain odd vertices, and where we wish to return to our starting vertex. In this circumstance, we require a different algorithm to obtain a solution.
- 1) List all odd vertices in the network. There will be an even number of these.
- 7 more annotations...
- - 2) In order to make the network Eulerian, find possible all possible sets of pairings of odd vertices in order to make them of even degree so that no odd vertices are left in the network.
  - 3) For each set of pairings, for each pairing, find the shortest route you need to travel to get from one vertex in the pairing to the other. Hence, add up the total distance you need to travel for each set of possible pairings.
  - 4) Choose the pairing with the minimum total distance and repeat these edges in the network, i.e. makes the associated vertices have an even degree. Note: there may be many different routes that can be constructed, all of which take the same minimum distance.
  - By applying this algorithm, we are effectively converting the vertices of odd degree to even degree by adding additional edges. The process of eliminating odd vertices by adding additional edges is called “Eulerising” the graph. Once the additional edges have been added in, we can simply apply Fleury’s algorithm to the modified network to obtain an optimal solution.
  - If the graph has more than two vertices of odd degree, we will have to retrace some of the edges in order to traverse all edges at least once, which makes sense. This assumes that we wish to finish up at the same vertex that we started out from.
  - We can see from the way that odd vertices are paired in the algorithm that the minimum circuit for any network will always have a length of less than twice the sum of all the weightings on the graph. This is because each edge in the network must be traversed once, by definition. Any extra parts added onto the route, i.e. repeated edges, will minimise the total distance from considering all possible pairings of odd vertices. As the number of odd vertices must be less than or equal to the number of vertices in total, then the optimal way in which this is done means that the extra length added must be less than the sum of the lengths of the entire original network. Thus, a relatively good route will always exist given even the most difficult network (one with only odd vertices).
  - 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).

Weightings are significant in this algorithm, as certain edges have to be repeated in the solution. Therefore, I have added these onto the network. The modified graph is shown.
• 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.
3 more annotations...
- 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.

5.7 Eulerizing graphs

www.austincc.edu/...05-7.html - Preview

euler exam graphs maths on 2007-12-17

10 more annotations...
- this eulerized graph now has an Euler circuit!
- Eulerizing
  Konigsberg
  Here's the Konigsberg graph:
- Note that all 4 vertices are odd, so we will duplicate edges RD and AL,
  thus making all vertices even!
- of course, such a tour is a compromise between
  
  one the one hand, no tour and
  
  on the other, building new bridges
  
  and only approximates a real Euler circuit . . .
  
  but it's the best we can do for the poor folks of Konigsberg!
  
  remember:
  
  added edges must be duplicates of existing edges
  
  we're not asking that the Konigsbergers actually build new bridges
  
  we're just allowing some bridges to be recrossed
  
  and this rule is not just for Konigsberg; it holds for all eulerizations
  
  so here's a no-no; it is NOT
  an eulerization:
- Optimal
  eulerizations
  
  if the objective is to construct an Euler circuit that traverses
  as few edges as possible
  
  we want to add as few edges as possible
  
  adding as few edges as possible is called an optimal eulerization
- Semi-eulerizations
  
  If all we need is an Euler path (not a circuit), we can leave
  two of the vertices odd, which will then be the start and end of an Euler
  path. This is called a semi-eulerization:

THE CHINESE POSTMAN PROBLEM - MODELLING THE PROBLEM MATHEMATICALLY

people.bath.ac.uk/...modellingmathematically.htm - Preview

on 2007-12-16

Vertex: a point of the graph where edges begin or end.
Degree: the degree of a vertex is the number of edge ends at that vertex.
5 more annotations...
- Odd vertex: a vertex that has an odd number of edges emerging from it.
  
  Even vertex: a vertex that has an even number of edges emerging from it.
- Edge: a path connecting two vertices (or one vertex to itself).
- Path: a sequence of consecutive edges.
- Eulerian circuit: a graph is said to be Eulerian if there is a route through it that starts and finishes at the same vertex, traversing each edge only once
- The aim of the Chinese Postman Problem, or the optimal solution, is to find an Eulerian circuit, as this is bound to have the shortest route visiting all edges at least once, as it visits each edge only once.

THE CHINESE POSTMAN PROBLEM - HOW CAN WE TELL WHETHER THERE WILL BE A SOLUTION

people.bath.ac.uk/...howcan.htm - Preview

chinese maths postman on 2007-12-16

Basically, if all vertices in a graph are of an even order, then for any path the goes into a given vertex (excluding the one from which the path started), there will exist a continuation of the path leading out of the vertex. Therefore, it will be possible to find a circuit through the network in which every edge is included, by selective choice of path.
Basically, if all vertices in a graph are of an even order, then for any path the goes into a given vertex (excluding the one from which the path started), there will exist a continuation of the path leading out of the vertex.
3 more annotations...
- it has been proven that, if every vertex in a network is of an even degree, then at least one (though possibly a lot more) circuit through that network can be found such that each edge is traversed once and once only, arriving back at the starting vertex once all other edges have been included.
- Obviously, it would be possible to start at any vertex on the graph, as they are all identical in that their degrees are all even.
  
  Now, this will only be the case if there are no odd vertices in the network. This is because, if there is an odd degree vertex in the network, although a path may have a route into the vertex, it may not necessarily be able to leave again. There will be one occasion a path is not able to leave an odd vertex if a graph contains one or more of these, and so the cycle will break down.
- A connected graph does not have an Euler circuit or a semi-Euler circuit if and only if it has more than two odd vertices. This is because any path constructed, even if the initial vertex is an odd one, will necessarily reach an odd vertex that it is not able to leave again without repeating the same edge twice (which is not allowed as we are aiming to achieve an Eulerian or semi-Eulerian circuit).

THE CHINESE POSTMAN PROBLEM - HISTORY OF PROBLEM - MORE DETAILED DESCRIPTION

people.bath.ac.uk/...detaileddescription.htm - Preview

exam maths postman on 2007-12-16

If there does not exist such a route in our system, then we want to know why this is, and find a revised optimal solution, where it is allowable to go over a given path between two points in the network twice.