Algorithm Problems: Cycle Detection, Single Connectivity, MST, and Shortest Paths

Detecting Cycles in an Undirected Graph

1.Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle, your algorithm should run in O(|V |) time, independent of |E|.

2.A directed graph G = (V, E) is Singly connected if u → v implies that there is at most one simple path from u to v for all vertices u, v ∈ V . Give an efficient algorithm to determine whether or not a directed graph is singly connected.

3.Does depth first search of an undirected graph produce any forward or cross edges?

4.A tree T = (V, E) is a connected graph on n vertices (|V | = n) with no cycles in it. Prove the following is true for every tree on n vertices:

(a) T has at least two leaves (nodes of degree 1)

(b) There are exactly n − 1 edges in T. 

5. Mr. Ash proposes the following greedy algorithm for finding a minimum spanning tree of a connected weighted graph G = (V, E, W): Until there are |V | − 1 edges left, remove a maximum-weight edge whose removal does not disconnect G. Prove or disprove the assertion that this algorithm is correct. If the algorithm is correct, analyze its running time

6.Given a graph G = (E, V ), let e be the second smallest edge in G according to the weight function w. Argue that there is a minimum spanning tree containing e. You can assume there are no ties in the weight function (all weights are unique).

7.Let G be a directed graph with real-valued edge costs and with a start vertex s and target vertex t. We wish to find a shortest path from s to t. Consider the following version of the single-source shortest path algorithm, where e(v) is an easily-computed function that estimates the shortest distance from v to t:

Repeat the following steps until L is empty (t is not reachable from s) or t is removed from L:

Delete from L a vertex v such that d(v) +e(v) is minimum. For each edge (v, w) such that d(v) + c(v, w) < d(w), replace d(w) by d(v) + c(v, w), replace p(w) by v, and add w to L if it is not already present.

The hope is that when t is removed from L, d(t) will be the length of a shortest path from s to t, and this path may be recovered by following p-pointers backward from t. We wish to find conditions on the estimate e that guarantee that this is the case. 

a.Prove that if e is a safe estimate then, for any vertex v, e(v) is a lower bound on the length of a shortest path from v to t.

b. Prove that if there is a negative cycle from which t is reachable, then no estimate is safe.

c.Prove that if e is a safe estimate, then the shortest path algorithm removes every vertex from L at most once, and when a vertex v is removed from L, d(v) is the actual shortest distance from s to v.

d. Suppose e and f are both safe estimates, with e(v) ≥ f(v) for every vertex v. Prove that, when the algorithm is run with estimate e, no more vertices are removed from L than when the algorithm is run with estimate f.