40
Paper 2 – Travelling Salesman Problems
Example
Consider the following weighted graph :
( a ) Write down
( i ) the degree of B ;
( ii ) |
the vertices of odd degree . |
( b ) |
State the edge of the smallest weight . |
( c ) |
Is Eulerian circuit exists in the above graph ? Explain your answer . |
The following table shows the least weight of a path connecting any two vertices . |
[ 2 ]
[ 1 ]
[ 2 ]
9
A B C D E F A - 90 200 270 p 105 B 90 - 120 190 100 q
C 200 120 - 115 150 225
D 270 190 115 - 90 165 E p 100 150 90 - 75 F 105 q 225 165 75 -
( d ) Write down the value of
( i ) p ;
( ii ) q . [ 2 ]
141 www . seprodstore . com