CS代写 | CS 344: Design and Analysis of Computer Algorithms Midterm Exam #2 Solutions


Problem 1.
(a) Suppose G = (V;E) is any undirected graph and (S; V S) is a cut with zero cut edges in G. Prove
that if we pick two arbitrary vertices u 2 S and v 2 V n S, and add a new edge (u; v), in the resulting
graph, there is no cycle that contains the edge (u; v). (12:5 points)
Solution. Suppose towards a contradiction that there is a cycle C that contains the edge (u; v). This
means that there is a path P from u to v that does not use the edge (u; v) in this cycle. Since this
path starts at u 2 S and ends in v 2 V n S, there should be an edge e in this path that goes from S to
V n S. This means that the cut (S; V n S) has at least one cut edge, a contradiction.

(b) Suppose G = (V;E) is an undirected graph with weight we on each edge e. Prove that if the weight
of some edge f is strictly larger than weight of all other edges in some cycle in G, then no minimum
spanning tree (MST) of G contains the edge f.
(Note that to prove this statement, it is not enough to say that some speci c algorithm for MST never
picks this edge f; you have to prove no MST of G can contain this edge). (12:5 points)
Solution. Suppose towards a contradiction that there is some MST T that contains the edge f.
Consider the graph T f which contains two connected components S1 and S2 (we removed an edge
from a tree). Since f is the heaviest edge of some cycle in G, there is an edge e that also connects C1
and C2 and we < wf . Now consider the graph T f + e which we claim is a tree: it has n 1 edges
and it is connected because we connected S1 and S2 via the edge e again. So T f + e is a spanning
tree with weight strictly less than T, contradicting the fact that T was a MST. So no MST of G can
contain the edge f.