Computer Science 280: Homework 6

Homework 6:
3/12/03 (due 3/26/03) Read Section 3.4, 3.5, 3.6, 3.8 Think about (don't hand in) Section 3.8, problems 13 and 25. 

Section     Number     Points      Comments


3.5 	    2(a)       5           That is, repeat only part (a) of 1.
            7          6
3.6 	    7(a)       5 	   Describe your method clearly
3.8 	    8 	       5 
            14 	       4 	   Assume each person does at most one job and each job
                                   is done by at most one person.  Also, don't forget to answer the 
                                   question after the graph (how good is your answer).
            32(b)      5


Supp. 	    5(a)       4

More problems:

1.
[6 points] Which of the three graphs in Section 3.7, Problem 2 (p. 263) have Eulerian cycles? (Explain why or why not.) Of the ones that do not have Eulerian cycles, which have Eulerian paths? (Again, explain why or why not.) Describe the Eulerian path/cycle when there is one. This will require drawing the graph in your homework and naming the vertices. For simplicity, label the graphs using vertices v1, v2, v3, v4 and (for parts (b) and (c)) v5, with v1 at the top and the rest of the vertices labeled in clockwise order.
2.
[4 points] For the graph described in Section 3.7, Problem 2(c), describe the order that the vertices would be visited using BFS (starting at v1). Repeat for DFS. When the algorithm gives you a choice, choose the lower labeled vertex (for example, if you have a choice between v2 and v3, choose v2).