CS-113. Problem Set 8

Due Tuesday, Dec.12

1. For an undirected graph G and the ST(G,s) algorithm in class, show that G has no path from s to v in G shorter than the one in T obtained by using a FIFO queue. In other words, show that T is a Shortest Path tree measuring path length in the number of edges (i.e. each edge has length 1). Yet another way of stating it is to prove that the (shortest path) distance of v from s in G is equal to the depth of v in the tree T (rooted in s).
    

2. Show the result of (a) BFS (ST, using queue) and (b) the result of DFS (ST using stack) on a clique K₆ of 6 nodes. And now, (c & d)on a complete bipartite graph K_4,4. (e) How will these results look for a general K_n? 
    

3. We have discussed the ST(G,s) algorithm for undirected graphs in class. What happens when you run it on a directed graph? Draw all the possible results (for all orders of selecting edges of a visited node for storage) of both BFS and DFS for this graph:
   
   
    

4. Can the the red edges be the tree T output by ST(G,s) if the storage is implemented as (a) stack, (b) queue?

   

   Draw all possible outcomes for (a) and (b).
    

5. Give the representation of the two graphs above as (a) adjacency matrix, (b) adjacency list.
    
6. Prove that if a weighted graph G=(V,E,W) has distinct weights for all the edges then there exists only one Minimum Spanning Tree of G.
   Hint: Suppose that there are two Minimum Spanning Trees T₁ and T₂, and consider a cycle in their union (prove that it must exist first).
    
7. Extra credit: ST(G,s) can be used to compute Shortest Path (from s) if we use Priority Queue for Storage: a data structure which returns the smallest element currently in the storage (see the notes for more details). Show however, that this Shortest Path algorithm will not work if weights can be negative (give a counter-example).