Data Structures and Algorithms
Tutorial Problems: Part 5

Graphs

  1. Is the minimum spanning tree of a graph unique? Provide an example to prove your answer.
  2. A minimum spanning tree has already been computed for a graph. Suppose that a new node is added (along with appropriate costs). How long will it take to re-compute the minimum spanning tree?
  3. Let T be a MST of a graph G and let L be the sorted list of the edge weights of T. Show that for any other MST T' of G, the list L is also the sorted list of edge weights of T'.
  4. You are given a directed graph, G = (V,E). Each edge (u,v) in G has a value r(u,v) associated with it. For all r(u,v), 0 <= r(u,v) <= 1. r(u,v) can be interpreted as the probability that a channel from u to v will not fail, ie it's a measure of the reliability of the channel. Devise an efficient algorithm to find the most reliable path between two given vertices.
  5. Suppose that all the edge weights in a graph are integers between 1 and | E |.
    1. Does this improve the time to find the MST?
    2. Does this improve the running time of Dijkstra's algorithm?
  6. Explain how to modify Dijkstra's algorithm so that if there is more than one minimum path from u to v, the path with the fewest number of edges is chosen.

Continue on to Tutorials: Part 6 Back to the Table of Contents
© John Morris, 1998