Homework Two Answers

- 1. 1.1.4 – graph appears to be directed, but since all arcs go both ways, the graph is actually undirected. Edges: (j m)(j w)(m r) (m s)(r s)(r t)(s t)(w t)(w s). Letters stand for names. J->S takes 2 days, through M or W. If J, W, stop talking, rumors take 3 days to reach j -> t.

- 2. 1.1.20 – c,e,k, and h,b,i. If c is chosen, k is forced, this forces e. If h is chosen, b forced, and this forces i.

- 3. Top entry in sequence must be n (or n-1 if low entry is 0). This value is too large

- 4. 1.1.28 – part (d) of #27, with vertex g eliminated.

- 5. 1.1.30 – b,d,f are all disjoint intervals. E touches all, so it must be of different length.

- 6. 1.1.36 – vertices are labeled 0 – 16. Each vertex has arcs to next 3 (e.g. 8 -> 9, 10, 11). Second player wins by always getting to these states: 16,12,8, 4.

- 7. 1.2.4 – not isomorphic: cube has all even cycles, pinwheel has odd cycles.

- 8. 1.2.6 parts a,b a) LHS has 3 verts of degree 4; b) isomorphic

- 9. 1.2.16 a) same as #4 above; b) 5 connected to all others. Removing 5 leaves a graph with odd number of verts of odddegree; c) start with a hexagon, then correct.

- 10. First is impossible; second can be reduced to (2 1 1 1 1), which is a real graph.

-- RobbieMoll - 26 Sep 2006

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2006-09-26 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback