CS W3139-02 Homework 5 Solutions


Non-Programming Problems

  1. Exercise 8.1

    Please note that there is an error in the following solutions for parts a, b, and c. Nodes 6 and 7 are in the wrong positions. In exercise 8.1, you are required to do union(1,7) and union(3,6), so node 6 should be in the spot node 7 is in, and vice versa. Credit Maya Rosenthal for pointing this out.

  2. Exercise 8.2

    In each case, have nodes 16 and 0 point directly to the root.

  3. Exercise 9.1

    The following ordering is arrived at by using a queue and assumes that vertices appear on an adjacency list alphabetically. The topological order that results is then:

    s, G, D, H, A, B, E, I, F, C, t

  4. Exercise 9.5

    1. (Unweighted paths) A->B, A->C, A->B->G, A->B->E, A->C->D, A->B->E->F.

    2. (Weighted paths) A->C, A->B, A->B->G, A->B->G->E, A->B->G->E->F, A->B->G->E->D.

  5. Exercise 9.15

    One possible minimum spanning tree is shown here. This solution is not unique. 

              3
     A-----------B            C
    /           / \            \ 
 4 /        2  /   \ 3          \ 1 
  /           /     \      2     \
 D           E       F------------G
            / \        
         2 /   \ 1       
          /     \      7 
	 H       I-----------J

  6. Exercise 9.26

    The first depth-first spanning tree is 

                        A
		     \
		      \
		       B
		      / \
		     /	 \
		    C	  G
		   / \
		  /   \
		 D     E
		/
	       /
	      F
    (The following is a list of back edges for this tree: (A,C), (B,E), (D,A), (E,D), (E,F), (G,E))

    The order to perform the second depth-first search is (see figure 9.84, page 345): (F,1), (D,2), (E,3), (C,4), (G,5), (B,6), (A,7). The strongly connected components are {F} and all other vertices.

  7. Exercise 9.30

    Let (u,v) be an edge of the breadth-first spanning tree. (u,v) are connected, thus they must be in the same tree. Let the root of the tree be r; if the shortest path from r to u is du, then u is at level du; likewise, v is at level dv. If (u,v) were a back edge, then du>dv, and v is visited before u. But if there were an edge between u and v, and v is visited first, then there would be a tree edge (v,u), and not a back edge (u,v). Likewise, if (u,v) were a forward edge, then there is some w, distinct from u and v, on the path from u to v; this contradicts the fact that dv = dw + 1. Thus only tree edges and cross edges are possible.

  8. Exercise 9.34

    Neither of the proposed algorithms works. For example, consider the graph with vertices {a,b,c,d,e,f} with adjacency sets Va = {b,d}, Vb = {a,c,e,f}, Vc = {b,d,e,f}, Vd = {a,c}, Ve = {b,c}, and Vf ={b,c}. A depth-first search of a biconnected graph that follows a, b, c, d is forced back to a, where it is stranded.

  9. Exercise 9.36

    All the algorithms work without modification for multigraphs.

  10. a ---------- b                            g --------- h
  \          |                              \         |
    \        |				      \       |
      \      |				        \     |  
        \    |			                  \   |
          \  |			                    \ |
            c ----------- d ---------- f             i
	                  |
			  |
			  |
			  |
			  |
			  e
    A graph can consist of one or more connected components. A connected component is a portion of a graph in which there is a path connecting any two vertices in the component. If a graph has several separate connected components, there is no path from a vertex in one component to a vertex in a separate component.

    The graph G has two separate connected components. The first component consists of vertices {a, b, c, d, e, f}. The second component consists of vertices {g, h, i}.

    The vertices in the two simple cycles are {a, b, c} and {g, h, i}.

Programming Problems

The following solution was provided by Carl Huttenlocher:

[CS3139 Home]