# Chapter 8

## Contents

# 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 .
- (d) Compute the maximum flow from to .

### 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.

- 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.

- 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 of a given graph (with vertices and edges) and a new edge of weight that we will add to . Give an efficient algorithm to find the minimum spanning tree of the graph . Your algorithm should run in time to receive full credit.

- 8.8. (a) Let be a minimum spanning tree of a weighted graph . Construct a new graph by adding a weight of to every edge of . Do the edges of form a minimum spanning tree of ? Prove the statement or give a counterexample.
- (b) Let describe a shortest path between vertices and of a weighted graph . Construct a new graph by adding a weight of to every edge of . Does describe a shortest path from to in ? Prove the statement or give a counterexample.

- 8.9. Devise and analyze an algorithm that takes a weighted graph 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 . Your algorithm must be correct and run in polynomial time.

- 8.10. Consider the problem of finding a minimum-weight connected subset of edges from a weighted connected graph . The weight of is the sum of all the edge weights in .
- (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 .

- 8.11. Let be a minimum spanning tree of a given graph with positive edge weights. Now suppose the weight of a particular edge is modified from to a new value . We seek to update the minimum spanning tree 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) and
- (b) and
- (c) and
- (d) and

- 8.12. Let be an undirected graph. A set of edges is called a
*feedback-edge set*if every cycle of has at least one edge in . - (a)Suppose that is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
- (b)Suppose that 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 .
- (c)Retrieve a minimum edge from a given component.

- 8.14. Design a data structure that can perform a sequence of,
*union*and*find*operations on a universal set of elements, consisting of a sequence of all*unions*followed by a sequence of all*finds*, in time .

### Shortest Paths

- 8.16

- 8.18

- 8.20

- 8.22

- 8.24

- 8.26

### Network Flow and Matching

- 8.28

Back to Chapter List