Midterm 2 Solutions
Problem 1. Provide the following information: Your name; Your SID number; Your
section number (and/or your TA name); Name of the person on your left (if any); Name of
the person on your right (if a
...
Midterm 2 Solutions
Problem 1. Provide the following information: Your name; Your SID number; Your
section number (and/or your TA name); Name of the person on your left (if any); Name of
the person on your right (if any).
Solutions
The correct spelling of the TA’s names are Scott Aaronson, Shyam Lakshmin, Iordanis (Jordan)
Kerenidis, Joseph (Joe) Polastre, Beini Zhou.
We gave full credit as long as you could spell your own name. (And we were not too strict
in checking that, either.) Common mistakes involved the spelling of Beini’s and Jordan’s
last names.
Problem 2. Consider a undirected graph G = (V; E) with nonnegative weights w(i; j) ‚
0 on its edges (i; j) 2 E. Let s be a node in G. Assume you have computed the shortest
paths from s, and minimum spanning tree of the graph. Suppose we change the weights on
every edge by adding 1 to each of them. The new weights are w0(i; j) = w(i; j)+ 1 for every
(i; j) 2 E.
(a) Would the minimum spanning tree change due to the change in weights? Give
an example where it changes or prove that it cannot change.
(b) Would the shortest paths change due to the change in weights? Give an example
where it changes or prove that it cannot change.
Solutions
The first question was, if T is a minimum spanning tree of a graph G, and if every edge
weight of G is incremented by 1, is T still an MST of G? The answer is yes. The simplest
proof is that, if G has n vertices, then any spanning tree of G has n ¡ 1 edges. Therefore
incrementing each edge weight by 1 increases the cost of every spanning tree by a constant,
n ¡ 1. So any spanning tree with minimal cost in the original graph also has minimal cost
in the new graph.
There are alternative proofs that amount to more complicated ways of saying the same
thing. For example: assume by way of contradiction that T is not an MST of the new
graph. Then there is some other spanning tree of G, call it Tb 6= T, with lower cost on the
new graph. Given a cut (R; S) of G, T has exactly one edge e and Tb has exactly one edge
eb crossing the cut. Suppose eb 6= e and eb has lower cost than e. Then by replacing e
[Show More]