Difference between revisions of "Weighted-graphs-TADM2E"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
Line 5: Line 5:
 
'''Simulating Graph Algorithms'''
 
'''Simulating Graph Algorithms'''
  
<br>6-1.  
+
<br>6-1.  
 
For the graphs in Problem (see book):
 
For the graphs in Problem (see book):
 
#Draw the spanning forest after every iteration of the main loop in Kruskal's algorithm.
 
#Draw the spanning forest after every iteration of the main loop in Kruskal's algorithm.
 
#Draw the spanning forest after every iteration of the main loop in Prim's algorithm.
 
#Draw the spanning forest after every iteration of the main loop in Prim's algorithm.
#Find the shortest path spanning tree rooted in &lt;math&gt;A&lt;/math&gt;.
+
#Find the shortest path spanning tree rooted in <math>A</math>.
#Compute the maximum flow from &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;H&lt;/math&gt;.
+
#Compute the maximum flow from <math>A</math> to <math>H</math>.
  
 
[[TADM2E 6.1|(Solution 6.1)]]  
 
[[TADM2E 6.1|(Solution 6.1)]]  
Line 18: Line 18:
 
'''Minimum Spanning Trees'''
 
'''Minimum Spanning Trees'''
  
&lt;br&gt;6-2.  
+
<br>6-2.  
 
Is the path between two vertices in a minimum spanning tree
 
Is the path between two vertices in a minimum spanning tree
 
necessarily a shortest path between the two vertices in the full graph?
 
necessarily a shortest path between the two vertices in the full graph?
 
Give a proof or a counterexample.
 
Give a proof or a counterexample.
  
&lt;br&gt;6-3.  
+
<br>6-3.  
 
Assume that all edges in the graph have distinct edge weights
 
Assume that all edges in the graph have distinct edge weights
 
(i.e., no pair of edges have the same weight).
 
(i.e., no pair of edges have the same weight).
Line 32: Line 32:
 
[[TADM2E 6.3|(Solution 6.3)]]  
 
[[TADM2E 6.3|(Solution 6.3)]]  
  
&lt;br&gt;6-4.  
+
<br>6-4.  
 
Can Prim's and Kruskal's algorithm yield different minimum spanning trees?
 
Can Prim's and Kruskal's algorithm yield different minimum spanning trees?
 
Explain why or why not.
 
Explain why or why not.
  
&lt;br&gt;6-5.  
+
<br>6-5.  
 
Does either Prim's and Kruskal's algorithm work if there are negative edge
 
Does either Prim's and Kruskal's algorithm work if there are negative edge
 
weights?
 
weights?
Line 43: Line 43:
 
[[TADM2E 6.5|(Solution 6.5)]]  
 
[[TADM2E 6.5|(Solution 6.5)]]  
  
&lt;br&gt;6-6.  
+
<br>6-6.  
Suppose we are ''given'' the minimum spanning tree &lt;math&gt;T&lt;/math&gt; of a given graph &lt;math&gt;G&lt;/math&gt;
+
Suppose we are ''given'' the minimum spanning tree <math>T</math> of a given graph <math>G</math>
(with &lt;math&gt;n&lt;/math&gt; vertices and &lt;math&gt;m&lt;/math&gt; edges)
+
(with <math>n</math> vertices and <math>m</math> edges)
and a new edge &lt;math&gt;e=(u,v)&lt;/math&gt; of weight &lt;math&gt;w&lt;/math&gt; that we will add to &lt;math&gt;G&lt;/math&gt;.
+
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
 
Give an efficient algorithm to find the minimum spanning tree of the graph
&lt;math&gt;G + e&lt;/math&gt;.
+
<math>G + e</math>.
Your algorithm should run in &lt;math&gt;O(n)&lt;/math&gt; time to receive full credit.
+
Your algorithm should run in <math>O(n)</math> time to receive full credit.
  
&lt;br&gt;6-7.  
+
<br>6-7.  
(a) Let &lt;math&gt;T&lt;/math&gt; be a minimum spanning tree of a weighted graph &lt;math&gt;G&lt;/math&gt;.
+
(a) Let <math>T</math> be a minimum spanning tree of a weighted graph <math>G</math>.
Construct a new graph &lt;math&gt;G'&lt;/math&gt; by adding a weight of &lt;math&gt;k&lt;/math&gt; to every edge of &lt;math&gt;G&lt;/math&gt;.
+
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 &lt;math&gt;T&lt;/math&gt; form a minimum spanning tree of &lt;math&gt;G'&lt;/math&gt;?
+
Do the edges of <math>T</math> form a minimum spanning tree of <math>G'</math>?
 
Prove the statement or give a counterexample.
 
Prove the statement or give a counterexample.
&lt;br&gt;
+
<br>
(b) Let &lt;math&gt;P=\{ s, \ldots, t \}&lt;/math&gt; describe a shortest weighted path between
+
(b) Let <math>P=\{ s, \ldots, t \}</math> describe a shortest weighted path between
vertices &lt;math&gt;s&lt;/math&gt; and &lt;math&gt;t&lt;/math&gt; of a weighted graph &lt;math&gt;G&lt;/math&gt;.
+
vertices <math>s</math> and <math>t</math> of a weighted graph <math>G</math>.
Construct a new graph &lt;math&gt;G'&lt;/math&gt; by adding a weight of &lt;math&gt;k&lt;/math&gt; to every edge of &lt;math&gt;G&lt;/math&gt;.
+
Construct a new graph <math>G'</math> by adding a weight of <math>k</math> to every edge of <math>G</math>.
Does &lt;math&gt;P&lt;/math&gt; describe a shortest path from &lt;math&gt;s&lt;/math&gt; to &lt;math&gt;t&lt;/math&gt; in &lt;math&gt;G'&lt;/math&gt;?
+
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.
 
Prove the statement or give a counterexample.
  
 
[[TADM2E 6.7|(Solution 6.7)]]  
 
[[TADM2E 6.7|(Solution 6.7)]]  
  
&lt;br&gt;6-8.  
+
<br>6-8.  
Devise and analyze an algorithm that takes a weighted graph &lt;math&gt;G&lt;/math&gt; and
+
Devise and analyze an algorithm that takes a weighted graph <math>G</math> and
 
finds the smallest change in the cost to a non-MST edge that would
 
finds the smallest change in the cost to a non-MST edge that would
 
cause a change in the
 
cause a change in the
minimum spanning tree of &lt;math&gt;G&lt;/math&gt;.
+
minimum spanning tree of <math>G</math>.
 
Your algorithm must be correct and run in polynomial time.
 
Your algorithm must be correct and run in polynomial time.
  
&lt;br&gt;6-9.  
+
<br>6-9.  
Consider the problem of finding a minimum weight connected subset &lt;math&gt;T&lt;/math&gt;
+
Consider the problem of finding a minimum weight connected subset <math>T</math>
of edges from a weighted connected graph &lt;math&gt;G&lt;/math&gt;.
+
of edges from a weighted connected graph <math>G</math>.
The weight of &lt;math&gt;T&lt;/math&gt; is the sum of all the edge weights in &lt;math&gt;T&lt;/math&gt;.
+
The weight of <math>T</math> is the sum of all the edge weights in <math>T</math>.
 
#Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges.
 
#Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges.
#Give an efficient algorithm to compute the minimum weight connected subset &lt;math&gt;T&lt;/math&gt;.
+
#Give an efficient algorithm to compute the minimum weight connected subset <math>T</math>.
  
 
[[TADM2E 6.9|(Solution 6.9)]]  
 
[[TADM2E 6.9|(Solution 6.9)]]  
  
&lt;br&gt;6-10.  
+
<br>6-10.  
Let &lt;math&gt;G=(V,E)&lt;/math&gt; be an undirected graph.
+
Let <math>G=(V,E)</math> be an undirected graph.
A set &lt;math&gt;F \subseteq E&lt;/math&gt; of edges is called a
+
A set <math>F \subseteq E</math> of edges is called a
''feedback-edge set'' if every cycle of &lt;math&gt;G&lt;/math&gt; has at least one edge in &lt;math&gt;F&lt;/math&gt;.
+
''feedback-edge set'' if every cycle of <math>G</math> has at least one edge in <math>F</math>.
#Suppose that &lt;math&gt;G&lt;/math&gt; is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
+
#Suppose that <math>G</math> is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
#Suppose that &lt;math&gt;G&lt;/math&gt; is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.
+
#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.
  
&lt;br&gt;6-11.  
+
<br>6-11.  
Modify Prim's algorithm so that it runs in time &lt;math&gt;O(n \log k)&lt;/math&gt;
+
Modify Prim's algorithm so that it runs in time <math>O(n \log k)</math>
on a graph that has only &lt;math&gt;k&lt;/math&gt; different edges costs.
+
on a graph that has only <math>k</math> different edges costs.
  
 
[[TADM2E 6.11|(Solution 6.11)]]  
 
[[TADM2E 6.11|(Solution 6.11)]]  
Line 98: Line 98:
 
'''Union-Find'''
 
'''Union-Find'''
  
&lt;br&gt;6-12.  
+
<br>6-12.  
 
Devise an efficient data structure to handle
 
Devise an efficient data structure to handle
 
the following operations on a weighted directed graph:
 
the following operations on a weighted directed graph:
 
#Merge two given components.
 
#Merge two given components.
#Locate which component contains a given vertex &lt;math&gt;v&lt;/math&gt;.
+
#Locate which component contains a given vertex <math>v</math>.
 
#Retrieve a minimum edge from a given component.
 
#Retrieve a minimum edge from a given component.
  
&lt;br&gt;6-13.  
+
<br>6-13.  
Design a data structure that can perform a sequence of, &lt;math&gt;m&lt;/math&gt; ''union'' and {\em
+
Design a data structure that can perform a sequence of, <math>m</math> ''union'' and {\em
find} operations on a universal set of &lt;math&gt;n&lt;/math&gt; elements, consisting of a
+
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'',
 
sequence of all ''unions'' followed by a sequence of all ''finds'',
in time &lt;math&gt;O(m+n)&lt;/math&gt;.
+
in time <math>O(m+n)</math>.
  
 
[[TADM2E 6.13|(Solution 6.13)]]  
 
[[TADM2E 6.13|(Solution 6.13)]]  
Line 117: Line 117:
 
'''Shortest Paths'''
 
'''Shortest Paths'''
  
&lt;br&gt;6-14.  
+
<br>6-14.  
 
The ''single-destination shortest path'' problem for a directed graph
 
The ''single-destination shortest path'' problem for a directed graph
 
seeks the shortest path ''from'' every vertex to a specified vertex
 
seeks the shortest path ''from'' every vertex to a specified vertex
&lt;math&gt;v&lt;/math&gt;.
+
<math>v</math>.
 
Give an efficient algorithm to solve the single-destination shortest paths
 
Give an efficient algorithm to solve the single-destination shortest paths
 
problem.
 
problem.
  
&lt;br&gt;6-15.  
+
<br>6-15.  
Let &lt;math&gt;G=(V,E)&lt;/math&gt; be an undirected weighted graph, and let &lt;math&gt;T&lt;/math&gt; be the
+
Let <math>G=(V,E)</math> be an undirected weighted graph, and let <math>T</math> be the
shortest-path spanning tree rooted at a vertex &lt;math&gt;v&lt;/math&gt;.
+
shortest-path spanning tree rooted at a vertex <math>v</math>.
Suppose now that all the edge weights in &lt;math&gt;G&lt;/math&gt; are increased
+
Suppose now that all the edge weights in <math>G</math> are increased
by a constant number &lt;math&gt;k&lt;/math&gt;.
+
by a constant number <math>k</math>.
Is &lt;math&gt;T&lt;/math&gt; still the shortest-path spanning tree from &lt;math&gt;v&lt;/math&gt;?
+
Is <math>T</math> still the shortest-path spanning tree from <math>v</math>?
  
 
[[TADM2E 6.15|(Solution 6.15)]]  
 
[[TADM2E 6.15|(Solution 6.15)]]  
  
&lt;br&gt;6-16.  
+
<br>6-16.  
 
Answer all of the following:
 
Answer all of the following:
#Give an example of a weighted connected graph &lt;math&gt;G=(V,E)&lt;/math&gt; and a vertex &lt;math&gt;v&lt;/math&gt;, such that the minimum spanning tree of &lt;math&gt;G&lt;/math&gt; is the same as the shortest-path spanning tree rooted at &lt;math&gt;v&lt;/math&gt;.
+
#Give an example of a weighted connected graph <math>G=(V,E)</math> and a vertex <math>v</math>, such that the minimum spanning tree of <math>G</math> is the same as the shortest-path spanning tree rooted at <math>v</math>.
#Give an example of a weighted connected directed graph &lt;math&gt;G=(V,E)&lt;/math&gt; and a vertex &lt;math&gt;v&lt;/math&gt;, such that the minimum-cost spanning tree of &lt;math&gt;G&lt;/math&gt; is very different from the shortest-path spanning tree rooted at &lt;math&gt;v&lt;/math&gt;.
+
#Give an example of a weighted connected directed graph <math>G=(V,E)</math> and a vertex <math>v</math>, such that the minimum-cost spanning tree of <math>G</math> is very different from the shortest-path spanning tree rooted at <math>v</math>.
 
#Can the two trees be completely disjointed?
 
#Can the two trees be completely disjointed?
  
&lt;br&gt;6-17.  
+
<br>6-17.  
 
Either prove the following or give a counterexample:
 
Either prove the following or give a counterexample:
 
#Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
 
#Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
Line 146: Line 146:
 
[[TADM2E 6.17|(Solution 6.17)]]  
 
[[TADM2E 6.17|(Solution 6.17)]]  
  
&lt;br&gt;6-18.  
+
<br>6-18.  
 
In certain graph problems, vertices have can have weights instead of or in
 
In certain graph problems, vertices have can have weights instead of or in
 
addition to the weights of edges.
 
addition to the weights of edges.
Let &lt;math&gt;C_v&lt;/math&gt; be the cost of vertex &lt;math&gt;v&lt;/math&gt;, and &lt;math&gt;C_{(x,y)}&lt;/math&gt; the cost of the edge
+
Let <math>C_v</math> be the cost of vertex <math>v</math>, and <math>C_{(x,y)}</math> the cost of the edge
&lt;math&gt;(x,y)&lt;/math&gt;.
+
<math>(x,y)</math>.
 
This problem is concerned with finding the cheapest path between vertices
 
This problem is concerned with finding the cheapest path between vertices
&lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; in a graph &lt;math&gt;G&lt;/math&gt;.
+
<math>a</math> and <math>b</math> in a graph <math>G</math>.
 
The cost of a path is the sum of the costs of the edges and vertices
 
The cost of a path is the sum of the costs of the edges and vertices
 
encountered on the path.
 
encountered on the path.
#Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of &lt;math&gt;\infty&lt;/math&gt;). Assume that &lt;math&gt;C_v = 1&lt;/math&gt; for all vertices &lt;math&gt;1 \leq v \leq n&lt;/math&gt; (i.e., all vertices have the same cost). Give an ''efficient'' algorithm to find the cheapest path from &lt;math&gt;a&lt;/math&gt; to &lt;math&gt;b&lt;/math&gt; and its time complexity.
+
#Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of <math>\infty</math>). Assume that <math>C_v = 1</math> for all vertices <math>1 \leq v \leq n</math> (i.e., all vertices have the same cost). Give an ''efficient'' algorithm to find the cheapest path from <math>a</math> to <math>b</math> and its time complexity.
#Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an ''efficient'' algorithm to find the cheapest path from &lt;math&gt;a&lt;/math&gt; to &lt;math&gt;b&lt;/math&gt; and its time complexity.
+
#Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an ''efficient'' algorithm to find the cheapest path from <math>a</math> to <math>b</math> and its time complexity.
#Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an ''efficient'' algorithm to find the cheapest path from &lt;math&gt;a&lt;/math&gt; to &lt;math&gt;b&lt;/math&gt; and its time complexity.
+
#Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an ''efficient'' algorithm to find the cheapest path from <math>a</math> to <math>b</math> and its time complexity.
  
&lt;br&gt;6-19.  
+
<br>6-19.  
Let &lt;math&gt;G&lt;/math&gt; be a weighted ''directed''
+
Let <math>G</math> be a weighted ''directed''
graph with &lt;math&gt;n&lt;/math&gt; vertices and &lt;math&gt;m&lt;/math&gt; edges, where all edges have positive weight.
+
graph with <math>n</math> vertices and <math>m</math> edges, where all edges have positive weight.
 
A directed cycle is a directed path that starts and ends at the same
 
A directed cycle is a directed path that starts and ends at the same
 
vertex and contains at least one edge.
 
vertex and contains at least one edge.
Give an &lt;math&gt;O(n^3)&lt;/math&gt; algorithm to find a directed cycle in &lt;math&gt;G&lt;/math&gt; of minimum total
+
Give an <math>O(n^3)</math> algorithm to find a directed cycle in <math>G</math> of minimum total
 
weight.
 
weight.
Partial credit will be given for an &lt;math&gt;O(n^2 m)&lt;/math&gt; algorithm.
+
Partial credit will be given for an <math>O(n^2 m)</math> algorithm.
  
 
[[TADM2E 6.19|(Solution 6.19)]]  
 
[[TADM2E 6.19|(Solution 6.19)]]  
  
&lt;br&gt;6-20.  
+
<br>6-20.  
 
Can we modify Dijkstra's algorithm to solve the
 
Can we modify Dijkstra's algorithm to solve the
 
single-source ''longest'' path problem by changing {\em
 
single-source ''longest'' path problem by changing {\em
Line 177: Line 177:
 
If not, then provide a counterexample.
 
If not, then provide a counterexample.
  
&lt;br&gt;6-21.  
+
<br>6-21.  
Let &lt;math&gt;G=(V,E)&lt;/math&gt; be a weighted acyclic directed graph with possibly negative
+
Let <math>G=(V,E)</math> be a weighted acyclic directed graph with possibly negative
 
edge weights.
 
edge weights.
 
Design a linear-time algorithm to solve the single-source shortest-path
 
Design a linear-time algorithm to solve the single-source shortest-path
problem from a given source &lt;math&gt;v&lt;/math&gt;.
+
problem from a given source <math>v</math>.
  
 
[[TADM2E 6.21|(Solution 6.21)]]  
 
[[TADM2E 6.21|(Solution 6.21)]]  
  
&lt;br&gt;6-22.  
+
<br>6-22.  
Let &lt;math&gt;G=(V,E)&lt;/math&gt; be a directed weighted graph such that all the weights are
+
Let <math>G=(V,E)</math> be a directed weighted graph such that all the weights are
 
positive.
 
positive.
Let &lt;math&gt;v&lt;/math&gt; and &lt;math&gt;w&lt;/math&gt; be two vertices in &lt;math&gt;G&lt;/math&gt; and &lt;math&gt;k \leq |V|&lt;/math&gt; be an integer.
+
Let <math>v</math> and <math>w</math> be two vertices in <math>G</math> and <math>k \leq |V|</math> be an integer.
Design an algorithm to find the shortest path from &lt;math&gt;v&lt;/math&gt; to &lt;math&gt;w&lt;/math&gt; that contains
+
Design an algorithm to find the shortest path from <math>v</math> to <math>w</math> that contains
exactly &lt;math&gt;k&lt;/math&gt; edges.
+
exactly <math>k</math> edges.
 
Note that the path need not be simple.
 
Note that the path need not be simple.
  
&lt;br&gt;6-23.  
+
<br>6-23.  
 
''Arbitrage'' is the use of discrepancies in currency-exchange rates to
 
''Arbitrage'' is the use of discrepancies in currency-exchange rates to
 
make a profit.
 
make a profit.
Line 200: Line 200:
 
2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars.
 
2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars.
 
At such a time, a smart trader can trade one U.S. dollar and end up with
 
At such a time, a smart trader can trade one U.S. dollar and end up with
&lt;math&gt;0.75 \times 2 \times 0.7 = 1.05&lt;/math&gt; U.S. dollars---a profit of 5%.
+
<math>0.75 \times 2 \times 0.7 = 1.05</math> U.S. dollars---a profit of 5%.
Suppose that there are &lt;math&gt;n&lt;/math&gt;
+
Suppose that there are <math>n</math>
currencies &lt;math&gt;c_1,...,c_n&lt;/math&gt; and an &lt;math&gt;n \times n&lt;/math&gt; table &lt;math&gt;R&lt;/math&gt; of exchange rates, such
+
currencies <math>c_1,...,c_n</math> and an <math>n \times n</math> table <math>R</math> of exchange rates, such
that one unit of currency &lt;math&gt;c_i&lt;/math&gt; buys &lt;math&gt;R[i,j]&lt;/math&gt; units of currency &lt;math&gt;c_j&lt;/math&gt;.
+
that one unit of currency <math>c_i</math> buys <math>R[i,j]</math> units of currency <math>c_j</math>.
 
Devise and analyze an algorithm to determine the maximum value of
 
Devise and analyze an algorithm to determine the maximum value of
&lt;math&gt; R[c_1,c_{i1}] \cdot R[c_{i1},c_{i2}] \cdots R[c_{i{k-1}},c_{ik}] \cdot R[c_{ik},c_1] &lt;/math&gt;
+
<math> R[c_1,c_{i1}] \cdot R[c_{i1},c_{i2}] \cdots R[c_{i{k-1}},c_{ik}] \cdot R[c_{ik},c_1] </math>
 
Hint: think all-pairs shortest path.
 
Hint: think all-pairs shortest path.
  
Line 214: Line 214:
 
'''Network Flow and Matching'''
 
'''Network Flow and Matching'''
  
&lt;br&gt;6-24.  
+
<br>6-24.  
 
A matching in a graph is a set of disjoint edges---i.e., edges
 
A matching in a graph is a set of disjoint edges---i.e., edges
 
that do not share any vertices in common.
 
that do not share any vertices in common.
 
Give a linear-time algorithm to find a maximum matching in a tree.
 
Give a linear-time algorithm to find a maximum matching in a tree.
  
&lt;br&gt;6-25.  
+
<br>6-25.  
An ''edge cover'' of an undirected graph &lt;math&gt;G=(V,E)&lt;/math&gt; is a set of edges such
+
An ''edge cover'' of an undirected graph <math>G=(V,E)</math> is a set of edges such
 
that each vertex in the graph is incident to at least one edge from the set.
 
that each vertex in the graph is incident to at least one edge from the set.
 
Give an efficient algorithm, based on matching,
 
Give an efficient algorithm, based on matching,
to find the minimum-size edge cover for &lt;math&gt;G&lt;/math&gt;.
+
to find the minimum-size edge cover for <math>G</math>.
  
 
[[TADM2E 6.25|(Solution 6.25)]]
 
[[TADM2E 6.25|(Solution 6.25)]]

Revision as of 18:23, 11 September 2014

Weighted Graph Algorithms

Simulating Graph Algorithms


6-1. For the graphs in Problem (see book):

  1. Draw the spanning forest after every iteration of the main loop in Kruskal's algorithm.
  2. Draw the spanning forest after every iteration of the main loop in Prim's algorithm.
  3. Find the shortest path spanning tree rooted in $ A $.
  4. Compute the maximum flow from $ A $ to $ H $.

(Solution 6.1)


Minimum Spanning Trees


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


6-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 6.3)


6-4. Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.


6-5. Does either Prim's and Kruskal's algorithm work if there are negative edge weights? Explain why or why not.

(Solution 6.5)


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


6-7. (a) Let $ T $ be a minimum spanning tree of a weighted graph $ G $. Construct a new graph $ G' $ by adding a weight of $ k $ to every edge of $ G $. Do the edges of $ T $ form a minimum spanning tree of $ G' $? Prove the statement or give a counterexample.
(b) Let $ P=\{ s, \ldots, t \} $ describe a shortest weighted path between vertices $ s $ and $ t $ of a weighted graph $ G $. Construct a new graph $ G' $ by adding a weight of $ k $ to every edge of $ G $. Does $ P $ describe a shortest path from $ s $ to $ t $ in $ G' $? Prove the statement or give a counterexample.

(Solution 6.7)


6-8. Devise and analyze an algorithm that takes a weighted graph $ G $ and finds the smallest change in the cost to a non-MST edge that would cause a change in the minimum spanning tree of $ G $. Your algorithm must be correct and run in polynomial time.


6-9. Consider the problem of finding a minimum weight connected subset $ T $ of edges from a weighted connected graph $ G $. The weight of $ T $ is the sum of all the edge weights in $ T $.

  1. Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges.
  2. Give an efficient algorithm to compute the minimum weight connected subset $ T $.

(Solution 6.9)


6-10. Let $ G=(V,E) $ be an undirected graph. A set $ F \subseteq E $ of edges is called a feedback-edge set if every cycle of $ G $ has at least one edge in $ F $.

  1. Suppose that $ G $ is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
  2. Suppose that $ G $ is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.


6-11. Modify Prim's algorithm so that it runs in time $ O(n \log k) $ on a graph that has only $ k $ different edges costs.

(Solution 6.11)


Union-Find


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

  1. Merge two given components.
  2. Locate which component contains a given vertex $ v $.
  3. Retrieve a minimum edge from a given component.


6-13. Design a data structure that can perform a sequence of, $ m $ union and {\em find} operations on a universal set of $ n $ elements, consisting of a sequence of all unions followed by a sequence of all finds, in time $ O(m+n) $.

(Solution 6.13)


Shortest Paths


6-14. The single-destination shortest path problem for a directed graph seeks the shortest path from every vertex to a specified vertex $ v $. Give an efficient algorithm to solve the single-destination shortest paths problem.


6-15. Let $ G=(V,E) $ be an undirected weighted graph, and let $ T $ be the shortest-path spanning tree rooted at a vertex $ v $. Suppose now that all the edge weights in $ G $ are increased by a constant number $ k $. Is $ T $ still the shortest-path spanning tree from $ v $?

(Solution 6.15)


6-16. Answer all of the following:

  1. Give an example of a weighted connected graph $ G=(V,E) $ and a vertex $ v $, such that the minimum spanning tree of $ G $ is the same as the shortest-path spanning tree rooted at $ v $.
  2. Give an example of a weighted connected directed graph $ G=(V,E) $ and a vertex $ v $, such that the minimum-cost spanning tree of $ G $ is very different from the shortest-path spanning tree rooted at $ v $.
  3. Can the two trees be completely disjointed?


6-17. Either prove the following or give a counterexample:

  1. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
  2. Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

(Solution 6.17)


6-18. In certain graph problems, vertices have can have weights instead of or in addition to the weights of edges. Let $ C_v $ be the cost of vertex $ v $, and $ C_{(x,y)} $ the cost of the edge $ (x,y) $. This problem is concerned with finding the cheapest path between vertices $ a $ and $ b $ in a graph $ G $. The cost of a path is the sum of the costs of the edges and vertices encountered on the path.

  1. Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of $ \infty $). Assume that $ C_v = 1 $ for all vertices $ 1 \leq v \leq n $ (i.e., all vertices have the same cost). Give an efficient algorithm to find the cheapest path from $ a $ to $ b $ and its time complexity.
  2. Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an efficient algorithm to find the cheapest path from $ a $ to $ b $ and its time complexity.
  3. Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path from $ a $ to $ b $ and its time complexity.


6-19. Let $ G $ be a weighted directed graph with $ n $ vertices and $ m $ edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an $ O(n^3) $ algorithm to find a directed cycle in $ G $ of minimum total weight. Partial credit will be given for an $ O(n^2 m) $ algorithm.

(Solution 6.19)


6-20. Can we modify Dijkstra's algorithm to solve the single-source longest path problem by changing {\em minimum} to maximum? If so, then prove your algorithm correct. If not, then provide a counterexample.


6-21. Let $ G=(V,E) $ be a weighted acyclic directed graph with possibly negative edge weights. Design a linear-time algorithm to solve the single-source shortest-path problem from a given source $ v $.

(Solution 6.21)


6-22. Let $ G=(V,E) $ be a directed weighted graph such that all the weights are positive. Let $ v $ and $ w $ be two vertices in $ G $ and $ k \leq |V| $ be an integer. Design an algorithm to find the shortest path from $ v $ to $ w $ that contains exactly $ k $ edges. Note that the path need not be simple.


6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with $ 0.75 \times 2 \times 0.7 = 1.05 $ U.S. dollars---a profit of 5%. Suppose that there are $ n $ currencies $ c_1,...,c_n $ and an $ n \times n $ table $ R $ of exchange rates, such that one unit of currency $ c_i $ buys $ R[i,j] $ units of currency $ c_j $. Devise and analyze an algorithm to determine the maximum value of $ R[c_1,c_{i1}] \cdot R[c_{i1},c_{i2}] \cdots R[c_{i{k-1}},c_{ik}] \cdot R[c_{ik},c_1] $ Hint: think all-pairs shortest path.

(Solution 6.23)


Network Flow and Matching


6-24. A matching in a graph is a set of disjoint edges---i.e., edges that do not share any vertices in common. Give a linear-time algorithm to find a maximum matching in a tree.


6-25. An edge cover of an undirected graph $ G=(V,E) $ is a set of edges such that each vertex in the graph is incident to at least one edge from the set. Give an efficient algorithm, based on matching, to find the minimum-size edge cover for $ G $.

(Solution 6.25)