Consider the two standard representations of directed graphs: the adjacency-list representation and the adjacency-matrix representation. Find a problem that can be solved more efficiently in the adjacency-list representation than in the adjacency-matrix representation, and another problem that can be solved more efficiently in the adjacency-matrix representation than in the adjacency-list representation. [4 marks]

(b) Prove or disprove (by giving a counter-example) the following claim: If a directed graph G contains a path from a vertex u to a vertex v, then any depth-first search must result in v.d ? u.f, where .d is the discovery time and .f the finishing time. [4 marks]

(c) We are given an undirected, connected graph G = (V, E) with edge-weights w : E ? R + and a minimum spanning tree T of G. How would you update your minimum spanning tree T in each of the following three cases? Specify the runtime of your algorithm and give a proof that the returned tree is indeed a minimum spanning tree.

(i) We increase the weight of an edge e which is not in T. [3 marks]

(ii) We decrease the weight of an edge e which is in T. [3 marks]

(iii) We add a new edge e with weight w(e) to G. The weight w(e) is arbitrary, but for simplicity you may assume that after adding the edge e no two edges in G have the same weight. [6 marks]