Mth 221

-------------------------------------------------

ANSWERS CHAPTER 3: Graph

1. Answer not unique

2. a) simple graph b) pseudograph c&d) directed multigraph

3. b) ({a}, {b}, {d}, {a,b}, {c,d}) c) ({a,b}, {b,c}, {c,d}, {c,d}, {a}, {e}, {a,e}) d) ({a,b}, {b,c}, {e,d}, {f})

4. pendant: a) c b) 0 c) 0 isolated: a) d b) 0 c) d, i

5. a) in-degree: 2,1,2,1 out-degree: 0,2,1,3 b) in-degree: 2,3,2,1 out-degree: 2,4,1,1

6. a) yes b) no c) yes

7. b) Ana&Matt, Barbara&Larry, Carol&Oscar, Dianne&Nick, Elizabeth&Jason

13. a) yes b) no c) no

14. a) (i) path, not simple, not circuit, 4 (ii) not path (iii) not path (iv) path, simple circuit, 5

b) (i) path, simple, not circuit, 4 (ii) path ,not simple, circuit, 4 (iii) not path (iv) not path

15. a) weakly b) neither c) weakly d) neither

16. a) {a,b,h,i}, {c,d,f,g}, {e} b) {a,b,f}, {c,d,e} c) {a,b,c,d,e,h}, {f}, {g} d) {a,b,d,f,g,h,i}, {c}, {e}

17. a) 2 b) 7 c) 20 d) 61

18. a) yes b) not

19. a) c b) b,c,e,i

20. a) none b) {a,b},{b,c}, {c,d}, {c,e}, {e,i}, {i,h}

21. a) euler circuit b) euler path c) euler circuit d) euler path e) euler circuit

22. a) Hamilton path b) Hamilton circuit c) neither

24. a) yes b) no c) yes d) no

25 a) yes b) no

26. a) 4 b) 4 c) 3