CS5800 Homework 10- Graphs Part 1 Solved

Graphs part 1

Problems

1. (15 pts) Exercise 22.1-5.
2. (15 pts) Exercise 22.2-6.
3. (15 pts) Exercise 22.2-7.
4. (10 pts) Exercise 22.3-7.
5. (10 pts) Exercise 22.3-10.
6. (15 pts) Exercise 22.3-12.
7. (20 pts) Exercise 22.4-5.
8. (15 pts) Two special vertices s and t in the undirected graph G=(V,E) have the fol- lowing property: any path from s to t has at least 1 + |V |/2 edges. Show that all paths from s to t must have a common vertex v (not equal to either s or t) and give an algorithm with running time O(V+E) to find such a node v.
9. (Extra credit 25) Problem 22-3.
10. (Extra credit 25) Problem 22-4.
11. (25 pts) Exercise 23.1-3.
12. (25 pts) Exercise 23.2-2.
13. (25 pts) Exercise 23.2-4.
14. (25 pts) Exercise 23.2-5.
15. (Extra credit 40 pts) Problem 23-1.
16. (Extra credit 30 pts) Exercise 23.1-11.
17. (Extra credit 30 pts) Write the code for Kruskal algorithm in a language of your choice. You will first have to read on the disjoint sets datastructures and operations (Chapter 21 in the book) for an efficient implementation of Kruskal trees.

    1