3 . Consider the following weighted graph :
( a ) Write down
( i ) the number of vertices of odd degree ;
( ii ) the number of vertices of even degree . [ 2 ]
( b ) Use the Chinese postman algorithm to find a possible route of minimum weight that passes through all edges , starting and finishing at C .
[ 3 ]
( c ) Write down the corresponding weight of the route . [ 1 ]
The following table shows the least weight of a path connecting any two vertices .
|
A |
B |
C |
D |
E |
F |
A |
- |
10 |
21 |
36 |
30 |
17 |
B |
10 |
- |
11 |
26 |
44 |
27 |
C |
21 |
11 |
- |
15 |
27 |
46 |
D |
36 |
26 |
15 |
- |
12 |
25 |
E |
30 |
44 |
27 |
12 |
- |
13 |
F |
17 |
27 |
46 |
25 |
13 |
- |
9
( d ) Using the nearest neighbour algorithm , starting and finishing at A , find an upper bound of the total weight of a cycle that passes through all six vertices .
[ 3 ] ( e ) Using the deleted vertex algorithm by deleting the vertex A , find a lower bound of the total weight of a cycle that passes through all six vertices . [ 4 ]
www . seprodstore . com
145