Slides in this set

Slide 1

Preview of page 1

This is used when we are trying to find the shortest
route round a network such all the arcs are travelled
along at least once.…read more

Slide 2

Preview of page 2

Step 1: Identify all the odd vertices
Step 2: Form all possible pairings of odd vertices
Step 3: For each pairing find the arcs that make the
total distance of repeats as small as possible
Step 4: Choose the pairing with the smallest sum and add
this to the graph
Step 5: Find a route that works and add the smallest sum
found in Step 4 to the sum of all the weights in
the original graph to find the length of the
required route.…read more

Slide 3

Preview of page 3

AOdd vertices
postman are B, at
starts G, H &T
the depot T and Add
toto the network
deliver mail
Possible pairings:
The all the streets
shortest extra shown in the network below. Find a
route is: Possible route is:
route that means he travels the shortest BGpossible
& HT distance.
Route: BEG & HECT
You don't believe
Length: me?
1.7 + 1.8 = 3.5
WantBHto & GT
see it?
Route: BEH & GECT
Length: 1.5 + 2.0 = 3.5
Route: BCT & GH
Length: 0.8 + 0.9 = 1.7…read more

Slide 4

Preview of page 4

Total length of all
original paths is
A D 16.45 km
Add on the extra
routes BCT and GH
E = 1.7 km
Shortest length =
16.45 + 1.7 = 18.15 km
Route is:
T A B E A G H E G H F D F E C D T C B C T…read more


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »