6. The table below shows the distances, in km, between six towns \(A , B , C , D , E\) and \(F\).
| \cline { 2 - 7 }
\multicolumn{1}{c|}{} | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) |
| \(A\) | - | 85 | 110 | 175 | 108 | 100 |
| \(B\) | 85 | - | 38 | 175 | 160 | 93 |
| \(C\) | 110 | 38 | - | 148 | 156 | 73 |
| \(D\) | 175 | 175 | 148 | - | 110 | 84 |
| \(E\) | 108 | 160 | 156 | 110 | - | 92 |
| \(F\) | 100 | 93 | 73 | 84 | 92 | - |
- Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
(4) - Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
- Use a short cut to reduce the upper bound to a value less than 680 .
(4)
- Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem.
(4)