Solutions to Written HW#4

Disclaimer: even if it looks like C++ code, it is supposed to be pseudo-code. I haven't compiled/run any of the below code, although I believe it to be correct modulo some possible typos. --Ami.

1. (I did this problem by mistake -- only realized it wasn't assigned after I typed it all up. Figured I'd put it up anyway so you can check yourselves if you feel like doing it anyway -- Ami).
   1. The adjacency matrix for 13-33 is:

      	0	1	2 	3	4	5
      0	inf	9	inf	inf	1	inf
      1	9	inf	8	inf	6	inf
      2	inf	8	inf	5	inf	2
      3	inf	inf	5	inf	inf	inf
      4	1	6	inf	inf	inf	7
      5	inf	inf	2	inf	7	inf
      

      The adjanceny list is:

      0 --> {1,9} --> {4,1}
      1 --> {0,9} --> {2,8} --> {4,6}
      2 --> {1,8} --> {3,5} --> {5,2}
      3 --> {2,5}
      4 --> {0,1} --> {1,6} --> {5,7}
      5 --> {2,2} --> {4,7}
      

   2. The adjacency matrix for 13-34 is:

      	a	b	c	d	e	f	g	h	i
      a	0	1	1	0	0	0	0	0	0
      b	0	0	0	1	0	0	0	1	0
      c	0	0	0	1	1	0	0	0	0
      d	0	0	0	0	0	0	0	1	0
      e	0	0	0	0	0	0	1	0	0
      f	0	0	0	0	0	0	0	0	1
      g	0	0	1	0	0	0	0	0	0
      h	0	0	0	0	0	0	1	0	0
      i	0	0	1	0	0	0	0	0	0
      

      The adjanceny list is:

      a --> {b} --> {c}
      b --> {d} --> {h}
      c --> {d} --> {e}
      d --> {h}
      e --> {g}
      f --> {g} --> {i}
      g --> {c}
      h --> {g}
      i --> {c}
      

4. Write pseudo-code to detect a cycle in a graph:

   bool Graph::Detect_Cycle() {
       return Detect_Cycle(0);
   }
   
   bool Graph::Detect_Cycle(int v) {
       mark v as visited
       
       if (v has more than 1 visited neighbor)
         return true;
       
       bool temp=false;
   
       for (each unvisited neighbor u of v)
         temp=temp||Detect_Cycle(u);
   
       return temp;
   }
   

5. The topological orders are:
   1. {a,b,d,e,c}
   2. {a,d,b,c}
   3. {a,b,d,e,c}

8. The BFS tree is:

   		a      h
   	      / | \   /
                /  |  \ /
   	    b   c   d
                   |   |
                   |   |
   		e   f
                  / \
   	      /   \
   	     i     g
   

   The DFS tree is:

   		a      h
   	      / |     /
                /  |    /
   	    b   c---d
                       |
                       |
   		e---f
                  / \
   	      /   \
   	     i     g
   

   The MST is:

   		a      h
   	      / |     /
                /  |    /
   	    b   c---d
                   |    
                   |   
   		e---f
                  /   /
   	      /   /
   	     i   g  
   

9. This is the same as the traversal algorithm, except that instead of marking nodes, add them to the tree, and when doing so, add the respective edge (this means a little more house-keeping, but it ain't rocket science).
10. MST for 13-22 when starting with:
    1. vertex g:

       		b
       	      /     c   h
       	     /     / \ /
       	    a     e   d
       	   / \       /
       	  /   \     g 
       	 i     \   /
       	        \ /
       		 f
       

    2. vertex c: Same thing.
11. The final W[] array should be: W[7]={0,2,4,6,5,8,6}

15. Prove that a graph-traversal algorithm visits every vertex if and only if the graph is connected, regardless of where the search starts:

    If the graph is not connected, then at least one vertex will not be visited, as all of our traversal algorithms rely on the crossing of edges. If no path of successive edges connects two nodes (which is necessary if the graph is to be disconnected), then one of them (at least) will not be visited by the algorithm (since if the algorithm did visit both, it would mean that some chain of edges allows passage from one to the other).
    Conversly, if DFS misses even one vertex, that means that no succession of edges leads to that vertex from some vertex, meaning that the graph is disconnected (if another node is connected to the vertex in question and to the initial vertex, it gives a path from the initial to the final vertex, contradicting the assumption that DFS missed the final vertex).
    Thus, the two conditions are equivalent.

17. Prove the loop invariant in Dijkstra's algorithm by induction on Step:

    Loop Invariant: Once a vertex v is placed in S, W[v] is the weight of the absolutely shortest path from 0 to v and will not change.

    Base case: for Step=1, S consists of only one vertex (0), and W[0]==0, which is in fact the shortest path from 0 to 0, so base case is done.
    Inductive Hypothesis: We assume that the invariant is true for steps 1 to N.
    Inductive Step: The inductive hyp. tells us that S consists of {v1, v2, ... , vN, w}, and that W[v1], ..., W[vN] is the shortest path cost from 0 to each of the first N vertices. We need to show that W[w] is the cost of the shortest path from 0 to w: Suppose there is a shorter path. Then it must pass through some vertex u not in S (because by construction, W[w] is the shortest path possible by using only vertices in S). Then the shortest path cost for w (call it x) is the shortest path cost for u (call it y) added to the shortest path cost from u to w (call it z), i.e.: x=y+z. But then y is less than x, and neither u nor w was in S in the N'th step, so u would have been added to S in the N+1'st step, and *NOT* w. This contradiction shows that the invariant is in fact true. QED.