Your Practice Set – Applications and Interpretation for IBDP Mathematics
4 . The following weighted graph shows a network of roads connecting nine fountains A , B ,
C , D , E , F , G , H and I , in a park . The weight on each edge shows the time , in seconds , needed to travel along the road represented by that edge .
( a ) Write down
( i ) the degree of F ;
( 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 B to H . [ 4 ]
( b ) Use the Chinese postman algorithm to find a possible route of minimum time required to passes through all roads , starting at D and finishing at F .
[ 3 ]
( c ) Write down the corresponding time required of the route . [ 1 ]
Assume that it is necessary to start and finish at the same point . Peter starts his journey at
D .
( d ) |
( i ) |
Use the Chinese postman algorithm to find a possible route of |
|
|
minimum time required to passes through all roads . |
( ii ) Write down the corresponding time required of the route .
[ 4 ]
140
SE Production Limited