3 . The following weighted graph shows a network of roads connecting seven cities A , B ,
C , D , E , F and G . The weight on each edge shows the time , in minutes , needed to travel along the road represented by that edge .
( a ) |
Write down |
( i ) |
the degree of D ; |
( ii ) |
the number of vertices of odd degree ; |
( iii ) |
the number of vertices of even degree ; |
( iv ) the minimum amount of time needed to travel from A to C .
( b ) Use the Chinese postman algorithm to find a possible route of minimum time required to passes through all roads , starting and finishing at C .
( c ) Write down the corresponding time required of the route .
Assume that it is not necessary to start and finish at the same point . A car starts its journey at C .
[ 4 ]
[ 3 ]
[ 1 ]
9
( d ) |
( i ) |
Write down a finishing point other than C such that the total time |
|
|
required to passes through all roads attains its minimum . |
( ii ) Hence , use the Chinese postman algorithm to find a possible route of minimum time required to passes through all roads .
( iii ) Write down the corresponding time required of the route .
[ 5 ] www . seprodstore . com
139