# CSC 344 Homework 2

## Assigned Mar 10, due Mar 24

Problems from the textbook
• Chapter 3, Exercise 7, sorta-proof about connectedness. 2 points.
• Chapter 3, Exercise 8, proof-or-disproof about diameter and average pairwise distance. 4 points.
• Chapter 3, Exercise 9, sorta-proof and algorithm about articulation points. 3 points.
• Chapter 3, Exercise 10, algorithm for counting shortest paths from v to w. 1 point.
• Chapter 3, Exercise 12, algorithm for checking consistency of life spans. 3 points.
A problem from another textbook:

Recall the definition of a connected graph. In this problem we'll study how securely connected a graph is. (For example, if we think of the graph as representing a computer network, could an enemy disconnect the network by sabotaging a single computer or communication link?)

A bridge edge is defined as an edge which, if removed, would leave a disconnected graph.

An articulation point is defined as a vertex which, if removed (with all its incident edges) would leave a disconnected graph.

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its bridge edges. (3 points)

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points. (3 points)

For both of these, you'll get partial credit for a correct but inefficient algorithm.

Hint: It may help to start by drawing a graph with a single bridge edge or an articulation point, run a breadth-first or depth-first search on it, and see what's special about the bridge edge or articulation point. Then try one with two bridge edges or two articulation points....