Exercise 40
1 . Consider the following weighted graph :
( a ) Write down
( i ) the degree of E ;
( ii ) the vertices of odd degree .
( b ) State the edge of the smallest weight .
( c ) Is Eulerian trail exists in the above graph ? Explain your answer .
The following table shows the least weight of a path connecting any two vertices .
A B C D E F
A |
- |
41 |
94 |
64 |
31 |
29 |
B |
41 |
- |
53 |
23 |
37 |
p |
C 94 53 - 47 q 123 D 64 23 47 - 59 96 E 31 37 q 59 - 37 F 29 p 123 96 37 -
[ 2 ]
[ 1 ]
[ 2 ]
9
( d ) Write down the value of
( i ) p ;
( ii ) q . [ 2 ]
( e ) Using the nearest neighbour algorithm , starting and finishing at B , find an upper bound of the total weight of a cycle that passes through all six vertices .
[ 3 ] ( f ) Using the deleted vertex algorithm by deleting the vertex B , find a lower bound of the total weight of a cycle that passes through all six vertices . [ 4 ]
143 www . seprodstore . com