A social network is represented by a graph \(G\), where vertices represent people and edges represent friendships. The adjacency matrix \(A\) for graph \(G\) with vertices P, Q, R, S, T is given below.

\(A=\begin{pmatrix}
0&1&1&0&1\\
1&0&1&1&0\\
1&1&0&1&1\\
0&1&1&0&1\\
1&0&1&1&0
\end{pmatrix}\)

(a) Draw the graph \(G\). [2]

(b) Find the number of walks of length 3 starting at vertex Q and ending at vertex T. [3]

The cost (in arbitrary units) of sending a message between connected people is given in the weighted adjacency table below. An entry “–” indicates no direct connection.

(c) Use Kruskal’s algorithm to find the minimum spanning tree for the network represented by the weighted table. State the total weight of the minimum spanning tree. [4]

(d) State the minimum total length of cable required. [1]

The company now wants to find the shortest route that starts at P, visits every other person exactly once, and returns to P.

(e) (i) State the name of this problem.
(ii) Use the nearest neighbour algorithm, starting at vertex P, to find an upper bound for the length of this route. [4]

(f) By deleting vertex R, find a lower bound for the length of this route. [4]