CS410, Summer 1998
Homework 8 Answers (a bit brief to call a sample solution)
Dan Grossman

1. 
   1. The star graph. (Make (1,i) an edge for i != 1 and make no other edges.)
   2. A balanced binary tree
   3. Entire graph is a simple cycle
   4. (i,j) is an edge iff j>i.

2.
 1. For i=0,1,...,n
       Build a graph with only vertices 0,1,...,i
        This can be done in O(n+m) by walking through the adjacency
        list representation of G
       Do DFS or BFS on the new graph counting the number of edges
        touched in each connected component
       If any has greater than n/k, return i-1

   2. As in 1, but do binary search on the i values.

   3. Use union-find by putting each vertex in its own set
      Also keep an edge count with each set, initialized to zero.
      For i=0,1,...
        For each edge (i,v)
          if (find(i) == find(v))
	     add one to find(i)'s set
          else
	     union(i,v) and make the size the sum of the sets' sizes
	     add one to find(i)'s set
        (If any set ever gets more than n/k edges, return i-1.)

3.
  1. Graphs with every vertex in its own SCC are dags.

For purpose of contradiction, assume vertices u and v in collapse(G)
are strongly-connected.  Then by the definition of edges in
collapse(G), there is some u_1, u_2, v_1, and v_2 in G such that:
  * u_1 and u_2 are in the SCC represented by u
  * v_1 and v_2 are in the SCC represented by v
  * (u_1, v_1) is an edge in G
  * (v_2, u_2) is an edge in G
By definition of strongly-connected we also know there are paths in G 
  * from u_2 to u_1
  * from v_1 to v_2
So in G there are paths of the form (---> for path, -> for edge):
  * u_1 -> v_1 ---> v_2
  * v_2 -> u_2 ---> u_1
So u_1 and v_2 are in the same SCC.  But they weren't collapsed to the
same node.  Contradiction.

   2. We know how to do SCC in O(n+m).  So we can get the vertices of
collapse(G) and for each vertex in G write down its corresponding
vertex in collapse(G).  To add the edges to collapse(G), we just walk
through the edges of G in time O(n+m) and add the corresponding edges
to collapse(G).

   3. Run collapse(G).
      Topologically sort collapse(G).
      Run DFS or BFS to build a forest over G, picking for each tree root 
        a vertex in the earliest unvisited SCC of the topological sort.

4. Possible answers:
   * Just do an MST algorithm -- an MST is a tree with smallest possible maximum
     weight.  (This is fairly hard to prove though.)
   * Do Kruskal's algorithm, but add _all_ edges of the next lightest weight
     until the graph is connected.  Then do a single DFS to make a tree
     using only the edges used to produce connectivity.

5.
   Modify Dijkstra's algorithm as follows:

   Make an array of size W*n where W is the maximum weight and the graph has n
   vertices.  If the shortest known path to v is i, then put vertex v in
   index i of the array.  So as a path length gets relaxed, the vertex
   moves left in the array.

   Then to extract-min, find the first vertex in the array and extract it.
   To find it, begin where the last extract-min ended and move to the right.
   (The critical insight is that relaxing will not move any vertex to the left
   of where the previous extract-min ended.)  So the total time for
   all extract-mins is the total time taken to move the pointer to the
   right.  This is <= W*n, the size of the array.  m (number of edges)
   relaxations take total time O(m), so the total is O(W*n + m).