Difference between revisions of "Chapter 8"
Jump to navigation
Jump to search
| Line 12: | Line 12: | ||
===Minimum Spanning Tree=== | ===Minimum Spanning Tree=== | ||
| − | :8.2 | + | :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]] | + | :[[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.3|Solution]] | ||
| − | :8.4 | + | :8.4. Can Prim’s and Kruskal’s algorithms yield different minimum spanning trees? Explain why or why not. |
| − | :[[8.5]] | + | :[[8.5]]. Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Explain why or why not. |
| + | [[8.5|Solution]] | ||
| − | :8.6 | + | :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]] | + | :[[8.7]]. Suppose we are given the minimum spanning tree <math>T</math> of a given graph <math>G</math> (with <math>n</math> vertices and <math>m</math> edges) and a new edge <math>e = (u, v)</math> of weight <math>w</math> that we will add to <math>G</math>. Give an efficient algorithm to find the minimum spanning tree of the graph <math>G + e</math>. Your algorithm should run in <math>O(n)</math> time to receive full credit. |
| + | [[8.7|Solution]] | ||
| − | :8.8 | + | :8.8. (a) Let <math>T</math> be a minimum spanning tree of a weighted graph <math>G</math>. Construct a new graph <math>G'</math> by adding a weight of <math>k</math> to every edge of <math>G</math>. Do the edges of <math>T</math> form a minimum spanning tree of <math>G'</math>? Prove the statement or give a counterexample. |
| + | :(b) Let <math>P = {s, . . . , t}</math> describe a shortest path between vertices <math>s</math> and <math>t</math> of a weighted graph <math>G</math>. Construct a new graph <math>G'</math> by adding a weight of <math>k</math> to every edge of <math>G</math>. Does <math>P</math> describe a shortest path from <math>s</math> to <math>t</math> in <math>G'</math>? Prove the statement or give a counterexample. | ||
| − | :[[8.9]] | + | :[[8.9]]. Devise and analyze an algorithm that takes a weighted graph <math>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>G</math>. Your algorithm must be correct and run in polynomial time. |
| + | [[8.9|Solution]] | ||
| − | :8.10 | + | :8.10. Consider the problem of finding a minimum-weight connected subset <math>T</math> of edges from a weighted connected graph <math>G</math>. The weight of <math>T</math> is the sum of all the edge weights in <math>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>T</math>. | ||
| Line 43: | Line 51: | ||
:8.12 | :8.12 | ||
| − | |||
===Union Find=== | ===Union Find=== | ||
Revision as of 22:43, 13 September 2020
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 [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.
- 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 [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.
- 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.
- 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.12
Union Find
- 8.14
Shortest Paths
- 8.16
- 8.18
- 8.20
- 8.22
- 8.24
- 8.26
Network Flow and Matching
- 8.28
Back to Chapter List
