Weighted Graph Algorithms

Simulating Graph Algorithms

8.1. For the graphs in Problem 7-1:

(a) Draw the spanning forest after every iteration of the main loop in Kruskal’s algorithm.

(b) Draw the spanning forest after every iteration of the main loop in Prim’s algorithm.

(c) Find the shortest-path spanning tree rooted in [math]\displaystyle{ A }[/math].

(d) Compute the maximum flow from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ H }[/math].

Minimum Spanning Tree

8.2. Is the path between two vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

8.3. Assume that all edges in the graph have distinct edge weights (i.e., no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

Solution

8.4. Can Prim’s and Kruskal’s algorithms yield different minimum spanning trees? Explain why or why not.

8.5. Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Explain why or why not.

Solution

8.6. (a) Assume that all edges in the graph have distinct edge weights (i.e., no pair of edges have the same weight). Is the minimum spanning tree of this graph unique? Give a proof or a counterexample.

(b) Again, assume that all edges in the graph have distinct edge weights (i.e. no pair of edges have the same weight). Is the shortest-path spanning tree of this graph unique? Give a proof or a counterexample.

8.7. Suppose we are given the minimum spanning tree [math]\displaystyle{ T }[/math] of a given graph [math]\displaystyle{ G }[/math] (with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges) and a new edge [math]\displaystyle{ e = (u, v) }[/math] of weight [math]\displaystyle{ w }[/math] that we will add to [math]\displaystyle{ G }[/math]. Give an efficient algorithm to find the minimum spanning tree of the graph [math]\displaystyle{ G + e }[/math]. Your algorithm should run in [math]\displaystyle{ O(n) }[/math] time to receive full credit.

Solution

8.8. (a) Let [math]\displaystyle{ T }[/math] be a minimum spanning tree of a weighted graph [math]\displaystyle{ G }[/math]. Construct a new graph [math]\displaystyle{ G' }[/math] by adding a weight of [math]\displaystyle{ k }[/math] to every edge of [math]\displaystyle{ G }[/math]. Do the edges of [math]\displaystyle{ T }[/math] form a minimum spanning tree of [math]\displaystyle{ G' }[/math]? Prove the statement or give a counterexample.

(b) Let [math]\displaystyle{ P = {s, . . . , t} }[/math] describe a shortest path between vertices [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] of a weighted graph [math]\displaystyle{ G }[/math]. Construct a new graph [math]\displaystyle{ G' }[/math] by adding a weight of [math]\displaystyle{ k }[/math] to every edge of [math]\displaystyle{ G }[/math]. Does [math]\displaystyle{ P }[/math] describe a shortest path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] in [math]\displaystyle{ G' }[/math]? Prove the statement or give a counterexample.

8.9. Devise and analyze an algorithm that takes a weighted graph [math]\displaystyle{ G }[/math] and finds the smallest change in the cost to a non-minimum spanning tree edge that would cause a change in the minimum spanning tree of [math]\displaystyle{ G }[/math]. Your algorithm must be correct and run in polynomial time.

Solution

8.10. Consider the problem of finding a minimum-weight connected subset [math]\displaystyle{ T }[/math] of edges from a weighted connected graph [math]\displaystyle{ G }[/math]. The weight of [math]\displaystyle{ T }[/math] is the sum of all the edge weights in [math]\displaystyle{ T }[/math].

(a) Why is this problem not just the minimum spanning tree problem? (Hint: think negative weight edges.)

(b) Give an efficient algorithm to compute the minimum-weight connected subset [math]\displaystyle{ T }[/math].

8.11. Let [math]\displaystyle{ T = (V, E') }[/math] be a minimum spanning tree of a given graph [math]\displaystyle{ G = (V, E) }[/math] with positive edge weights. Now suppose the weight of a particular edge [math]\displaystyle{ e \in E }[/math] is modified from [math]\displaystyle{ w(e) }[/math] to a new value [math]\displaystyle{ \hat{w}(e) }[/math]. We seek to update the minimum spanning tree [math]\displaystyle{ T }[/math] to reflect this change without recomputing the entire tree from scratch. For each of the following four cases, give a linear-time algorithm to update the tree:

(a)[math]\displaystyle{ e \notin E' }[/math] and [math]\displaystyle{ \hat{w}(e) \gt w(e) }[/math]

(b) [math]\displaystyle{ e \notin E' }[/math] and [math]\displaystyle{ \hat{w}(e) \lt w(e) }[/math]

(c) [math]\displaystyle{ e \in E' }[/math] and [math]\displaystyle{ \hat{w}(e) \lt w(e) }[/math]

(d) [math]\displaystyle{ e \in E' }[/math] and [math]\displaystyle{ \hat{w}(e) \gt w(e) }[/math]

Solution

8.12. Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A set [math]\displaystyle{ F \subseteq E }[/math] of edges is called a feedback-edge set if every cycle of [math]\displaystyle{ G }[/math] has at least one edge in [math]\displaystyle{ F }[/math].

(a)Suppose that [math]\displaystyle{ G }[/math] is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.

(b)Suppose that [math]\displaystyle{ G }[/math] is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.

Union Find

8.13. Devise an efficient data structure to handle the following operations on a weighted directed graph:

(a)Merge two given components.

(b)Locate which component contains a given vertex [math]\displaystyle{ v }[/math].

(c)Retrieve a minimum edge from a given component.

Solution

8.14. Design a data structure that can perform a sequence of, [math]\displaystyle{ m }[/math] union and find operations on a universal set of [math]\displaystyle{ n }[/math] elements, consisting of a sequence of all unions followed by a sequence of all finds, in time [math]\displaystyle{ O(m+n) }[/math].