Consider the two standard representations of directed graphs: the adjacency-list representation and the adjacency-matrix representation. Find a
Question:
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]
Quantitative Analysis for Management
ISBN: 978-0132149112
11th Edition
Authors: Barry render, Ralph m. stair, Michael e. Hanna