39

Paper 2 – Chinese Postman Problems

Example

The following table shows the weight of the edges of a graph with six vertices A , B , C ,

D , E and F :

A B C D E F A - 22 - - 23 27 B 22 - 18 12 20 - C - 18 - 18 - - D - 12 18 - 15 - E 23 20 - 15 - 5 F 27 - - - 5 -

( a ) Draw a weighted graph that represents the above table . ( b ) Write down

[ 3 ]

( i ) the degree of A ; ( ii ) the number of vertices of odd degree .

[ 2 ]

( c ) Write down the adjacency matrix M of the graph . [ 2 ]

( d ) Hence , find the total number of walks of length 2 from E to A . [ 2 ]

( e ) Use the Chinese postman algorithm to find a possible route of minimum weight that passes through all edges , starting and finishing at A .

[ 3 ]

( f ) Write down the corresponding weight of the route . [ 1 ]

135