CS 3158: Design and Analysis of Algorithms
Homework 6: Due Friday, 14th August 1998

1. (15 points) Let G be a graph. Suppose a BFS is done in G with s as the starting vertex. Prove that the BFS number that gets assigned to any vertex v gives the shortest distance from s to v.
2. (15 points) Exercise 23.3-9, page 485 of the text.
3. (15 points) Exercise 23.4-3, page 488 of the text.
4. (10 points) Exercise 23.5-4, page 494 of the text.
5. (10 points) Let G be a connected, undirected graph. Prove that a vertex v of G is an articulation point iff there exist two distinct vertices x,y such that every path between x and y pass through v.
6. (10 points) Exercise 24.1-1, page 503 of the text.

• About this document ...