|
|
Line 1: |
Line 1: |
− | =Weighted Graph Algorithms= | + | =Graph Traversal= |
| | | |
| ===Simulating Graph Algorithms=== | | ===Simulating Graph Algorithms=== |
| | | |
− | :[[8.1]]. For the graphs in Problem 7-1: | + | :[[7.1]]. For the following graphs <math>G_1</math> (left) and <math>G_2</math> (right): |
− | :(a) Draw the spanning forest after every iteration of the main loop in Kruskal’s algorithm.
| + | :(see book for figures) |
− | :(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>A</math>.
| |
− | :(d) Compute the maximum flow from <math>A</math> to <math>H</math>.
| |
− | [[8.1|Solution]]
| |
| | | |
− | ===Minimum Spanning Tree===
| + | :(a)Report the order of the vertices encountered on a breadth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). |
| + | :(b)Report the order of the vertices encountered on a depth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). |
| + | [[7.1|Solution]] |
| | | |
− | :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.
| |
| | | |
| + | :7.2. Do a topological sort of the following graph <math>G</math>: |
| + | :(see book for figure) |
| | | |
− | :[[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.
| + | ===Traversal=== |
− | [[8.3|Solution]]
| |
| | | |
| + | :[[7.3]] |
| | | |
− | :8.4. Can Prim’s and Kruskal’s algorithms yield different minimum spanning trees? Explain why or why not.
| |
| | | |
| + | :7.4 |
| | | |
− | :[[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]]
| |
| | | |
| + | :[[7.5]] |
| | | |
− | :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.
| |
| | | |
| + | :7.6 |
| | | |
− | :[[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]]
| |
| | | |
| + | :[[7.7]] |
| | | |
− | :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.
| |
| | | |
| + | :7.8 |
| | | |
− | :[[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]]
| |
| | | |
| + | :[[7.9]] |
| | | |
− | :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>.
| |
| | | |
| + | :7.10 |
| | | |
− | :[[8.11]]. Let <math>T = (V, E')</math> be a minimum spanning tree of a given graph <math>G = (V, E)</math> with positive edge weights. Now suppose the weight of a particular edge <math>e \in E</math> is modified from <math>w(e)</math> to a new value <math>\hat{w}(e)</math>. We seek to update the minimum spanning tree <math>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>e \notin E'</math> and <math> \hat{w}(e) > w(e)</math>
| |
− | :(b) <math>e \notin E'</math> and <math>\hat{w}(e) < w(e)</math>
| |
− | :(c) <math>e \in E'</math> and <math>\hat{w}(e) < w(e)</math>
| |
− | :(d) <math>e \in E' </math> and <math>\hat{w}(e) > w(e)</math>
| |
− | [[8.11|Solution]]
| |
| | | |
| + | :[[7.11]] |
| | | |
− | :8.12. Let <math>G=(V,E)</math> be an undirected graph. A set <math>F \subseteq E</math> of edges is called a ''feedback-edge set'' if every cycle of <math>G</math> has at least one edge in <math>F</math>.
| |
− | :(a)Suppose that <math>G</math> is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
| |
− | :(b)Suppose that <math>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===
| + | :7.12 |
| | | |
− | :[[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>v</math>.
| |
− | :(c)Retrieve a minimum edge from a given component.
| |
− | [[8.13|Solution]]
| |
| | | |
| + | ===Applications=== |
| | | |
− | :8.14. Design a data structure that can perform a sequence of, <math>m</math> ''union'' and ''find'' operations on a universal set of <math>n</math> elements, consisting of a sequence of all ''unions'' followed by a sequence of all ''finds'', in time <math>O(m+n)</math>. | + | :[[7.13]] |
| | | |
− | ===Shortest Paths===
| |
| | | |
− | :[[8:15]] | + | :7.14 |
| | | |
| | | |
− | :8.16 | + | :[[7.15]] |
| | | |
| + | ===Algorithm Design=== |
| | | |
− | :[[8.17]] | + | :7.16 |
| | | |
| | | |
− | :8.18 | + | :[[7.17]] |
| | | |
| | | |
− | :[[8.19]] | + | :7.18 |
| | | |
| | | |
− | :8.20 | + | :[[7.19]] |
| | | |
| | | |
− | :[[8.21]] | + | :7.20 |
| | | |
| | | |
− | :8.22 | + | :[[7.21]]] |
| | | |
| | | |
− | :[[8.23]] | + | :7.22 |
| | | |
| | | |
− | :8.24 | + | :[[7.23]] |
| | | |
| | | |
− | :[[8.25]] | + | :7.24 |
| | | |
| | | |
− | :8.26 | + | :[[7.25]] |
| | | |
| | | |
− | :[[8.27]] | + | :7.26 |
| | | |
| | | |
− | ===Network Flow and Matching=== | + | ===Directed Graphs=== |
| | | |
− | :8.28 | + | :[[7.27]] |
| | | |
| | | |
− | :[[8.29]] | + | :7.28 |
| + | |
| + | |
| + | :[[7.29]] |
| + | |
| + | |
| + | :7.30 |
| + | |
| + | |
| + | :[[7.31]] |
| + | |
| + | |
| + | :7.32 |
| + | |
| + | |
| + | :[[7.33]] |
| + | |
| + | |
| + | :7.34 |
| + | |
| + | |
| + | :[[7.35]] |
| + | |
| + | |
| + | :7.36 |
| + | |
| + | |
| + | :[[7.37]] |
| + | |
| + | |
| + | ===Articulation Vertices=== |
| + | |
| + | :7.38 |
| + | |
| + | |
| + | :[[7.39]] |
| + | |
| + | |
| + | :7.40 |
| + | |
| + | |
| + | :[[7.41]] |
| + | |
| + | |
| + | ===Interview Problems=== |
| + | |
| + | :7.42 |
| + | |
| + | |
| + | :[[7.43]] |
| | | |
| | | |
| Back to [[Chapter List]] | | Back to [[Chapter List]] |