Difference between pages "Chapter 8" and "Chapter 7"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
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]]
 
  
 +
:[[7.11]]
  
:8.12
 
  
===Union Find===
+
:7.12
  
:[[8.13]]
 
  
 +
===Applications===
  
:8.14
+
:[[7.13]]
  
  
===Shortest Paths===
+
:7.14
  
:[[8:15]]
 
  
 +
:[[7.15]]
  
:8.16
+
===Algorithm Design===
  
 +
:7.16
  
:[[8.17]]
 
  
 +
:[[7.17]]
  
:8.18
 
  
 +
:7.18
  
:[[8.19]]
 
  
 +
:[[7.19]]
  
:8.20
 
  
 +
:7.20
  
:[[8.21]]
 
  
 +
:[[7.21]]]
  
:8.22
 
  
 +
:7.22
  
:[[8.23]]
 
  
 +
:[[7.23]]
  
:8.24
 
  
 +
:7.24
  
:[[8.25]]
 
  
 +
:[[7.25]]
  
:8.26
 
  
 +
:7.26
  
:[[8.27]]
 
  
 +
===Directed Graphs===
  
===Network Flow and Matching===
+
:[[7.27]]
  
:8.28
 
  
 +
:7.28
  
:[[8.29]]
+
 
 +
:[[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]]

Revision as of 16:13, 14 September 2020

Graph Traversal

Simulating Graph Algorithms

7.1. For the following graphs [math]\displaystyle{ G_1 }[/math] (left) and [math]\displaystyle{ G_2 }[/math] (right):
(see book for figures)
(a)Report the order of the vertices encountered on a breadth-first search starting from vertex [math]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).
(b)Report the order of the vertices encountered on a depth-first search starting from vertex [math]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).

Solution


7.2. Do a topological sort of the following graph [math]\displaystyle{ G }[/math]:
(see book for figure)

Traversal

7.3


7.4


7.5


7.6


7.7


7.8


7.9


7.10


7.11


7.12


Applications

7.13


7.14


7.15

Algorithm Design

7.16


7.17


7.18


7.19


7.20


7.21]


7.22


7.23


7.24


7.25


7.26


Directed Graphs

7.27


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