7 . The following weighted graph shows a network of railways connecting eight train stations A , B , C , D , E , F , G and H , in a town . The weight on each edge shows the transportation fee ( in dollars ) for a passenger to travel between two adjacent stations by train .
12 25 10
15
H
E
20 16
D
17 18
G
24
F
( a ) Write down
( i ) the degree of E ;
( ii ) the number of vertices of odd degree ;
( iii ) the number of vertices of even degree ;
( iv ) the minimum amount of transportation fee needed to travel from
A to F .
( v ) the minimum amount of transportation fee needed to travel from C to G .
[ 5 ]
( b ) Use the Chinese postman algorithm to find a possible route of minimum transportation fee required to pass through all edges , starting at H and finishing at B .
[ 3 ] ( c ) Write down the corresponding transportation fee required of the route .
[ 1 ] Assume that it is necessary to start and finish at the same point . Joseph starts his journey at the station B .
© SE Production Limited 26 All Rights Reserved 2021