Chinese Postman Problem

4499 Words18 Pages
CHAPTER 3 Chinese postman problem Learning objectives After studying this chapter, you should be able to: ■ understand the Chinese postman problem ■ apply an algorithm to solve the problem ■ understand the importance of the order of vertices of graphs. 3.1 Introduction In 1962, a Chinese mathematician called Kuan Mei-Ko was interested in a postman delivering mail to a number of streets such that the total distance walked by the postman was as short as possible. How could the postman ensure that the distance walked was a minimum? In the following example a postman has to start at A, walk along all 13 streets and return to A. The numbers on each edge represent the length, in metres, of each street. The problem is to find a trail that uses all the edges of a graph with minimum length. E 70 B 50 A 50 C 50 50 70 70 D 120 70 G 50 70 F 60 60 H We will return to solving this actual problem later, but initially we will look at drawing various graphs. Chinese postman problem 45 3.2 Traversable graphs A traversable graph is one that can be drawn without taking a pen from the paper and without retracing the same edge. In such a case the graph is said to have an Eulerian trail. E E Eulerian trails are dealt with in detail in Chapter 5. 3 B C B C B C A D A D A D F Graph 1 Graph 2 Graph 3 If we try drawing the three graphs shown above we find: ● it is impossible to draw Graph 1 without either taking the pen off the paper or re-tracing an edge ● we can draw Graph 2, but only by starting at either A or D – in each case the path will end at the other vertex of D or A ● Graph 3 can be drawn regardless of the starting position and you will always return to the start vertex. What is the difference between the three graphs? In order to establish the differences, we must consider the order of the vertices for each graph. We obtain

More about Chinese Postman Problem

Open Document