# 算法代写 | comp2123 Solutions of Assignment 5

Problem 1. (10 points)
We are given a rooted tree T = (V, E) and its root u, i.e., a simple connected undi-
rected acyclic graph and a vertex u of this tree that we consider to be its root. We
want to compute the smallest set of vertices S  V such that every edge in E is
incident to some vertex in S.
Example:
u v w x
Vertex u is the root of the above tree. If we choose S = fvg, we indeed have the
property that every edge is incident to a vertex in S. Furthermore, there’s no smaller
set with this property. Picking S = fu,w, xg would also yield a set where every edge
is incident to a vertex in S, but it isn’t the smallest set. Picking S = fu,wg would
mean that edge (v, x) isn’t incident to any vertex in S.
We are given two algorithms for this problem:
degreeAlgorithm sorts the vertices of T by their degree and adds a vertex to S
if it’s incident to some edge that isn’t incident to any vertex in S.
BFSAlgorithm runs a breadth ﬁrst search from the root u. Then it compares the
size of the union of all vertices in even layers to the size of the union of all vertices
in odd layers and returns the smaller of the two sets.
1: function degreeAlgorithm(M)
2: S Æ
3: Sort vertices in T by their degree and rename such that deg(v1)  deg(v2)
 …  deg(vn)
4: for each vi in T do
5: if vi is incident to some edge e
6: and e isn’t incident to any vertex in S then
7: S S [ fvig
8: return S

1: function BFSAlgorithm(T, u)
2: layers, parent BFS(T, u)
3: even the union of all vertices in layers[i], where i is even
4: odd the union of all vertices in layers[i], where i is odd
5: if jevenj < joddj then
6: return even
7: else
8: return odd
Argue whether degreeAlgorithm always returns the correct answer by either
arguing its correctness (if you think it’s correct) or by providing a counterex-
ample (if you think it’s incorrect).
a)
Argue whether BFSAlgorithm always returns the correct answer by either
arguing its correctness (if you think it’s correct) or by providing a counterex-
ample (if you think it’s incorrect).
b)

Solution 1.
This algorithm is incorrect, for example on the tree below, rooted at t. It would
return fu, v,w, xg (sorted vertex order is v, u,w, x, t, y, z and while processing
v, u, w, and x they have an incident edge that isn’t incident to anything in S
yet), while the smallest set is fu,w, xg.
a)
This algorithm is also incorrect, for example on the tree below, rooted at u.
It would return fv, y, zg (both even and odd have the same size, so odd is
returned), while the smallest set is fv, xg. (Note that a single vertex isn’t a
counterexample, since the union of all even layers of the BFS algorithm is the
empty set, which is also the smallest set incident to every edge in this graph.)
b) E-mail: itcsdx@outlook.com  微信:itcsdx 