Transcription of CHAPTER 3 Chinese postman problem
{{id}} {{{paragraph}}}
Example: bankruptcy
CHAPTER 3 Chinese postman problem
IntroductionIn 1962, a Chinese mathematician called Kuan Mei-Ko wasinterested in a postman delivering mail to a number of streetssuch that the total distance walked by the postman was as shortas possible. How could the postman ensure that the distancewalked was a minimum?In the following example a postman has to start at A, walk alongall 13 streets and return to A. The numbers on each edgerepresent the length, in metres, of each street. The problem is tofind a trail that uses all the edges of a graph with will return to solving this actual problem later, but initiallywe will look at drawing various 3 Chinese postman problemLearning objectivesAfter 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 postman Traversable graphsIf we try drawing the three graphs shown above we find: it is impossible to draw graph 1 without either taking the penoff the paper or re-tracing an edge we can draw graph 2, but only by starting at either A or D ineach case the path will end at the other vertex of D or A graph 3 can be drawn regardless of the starting position andyou will always return to the start is the difference between the three graphs?
46 Chinese postman problem Graph 3 When the order of all the vertices is even, the graph is traversable and we can draw it. When there are two odd vertices we can draw the graph …
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: