|
Join The Student Room TodayBe part of the UK's largest and fastest growing student community. It's free to join and a lot of fun - Get inspired, express your ideas, interact and share Revision:Route InspectionFrom The Student RoomTSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Route Inspection
A route is traversable if and only if it is Eulerian (or semi-Eulerian). An Eulerian graph has nodes of even order only. In an Eulerian graph, the least weight path is the sum of all the arc weights. To find the least weight path of non-Eulerian graphs we must first effectively make the graph Eulerian by adding arcs to make all nodes even. These newly added arcs are the routes that must be repeated to make the graph traversable. In this case the least weight path is the sum of all arc weights plus the sum of the repeated weights (i.e. the newly added weights).
The Chinese Postman algorithmThis algorithm produces the least weight closed trail containing every arc in a network, starting and ending at the same node.
Weight of closed trail = total weight of network + sum of minimum weight paths found in step 3 Example
Minimum weight grouping is AB, DE (55)
Therefore, weight of closed trail = 312 + 55 = 367
Problems with the algorithmAs the number of odd nodes increases, the number of possible pairings to be considered increases dramatically. It is therefore impractical to do the algorithm by hand with more than 6 nodes. Even with a computer, it can become too time consuming - with 12 odd nodes there are 10395 combinations to consider. Also SeeSee the other D1 notes:
Comments |
|