程序代写案例-MA428
MA428 (Combinatorial Optimisation) Seminar 5
Summative assessment 1. This is due at 12pm noon UK time on Tuesday the 2nd of
March.
ˆ You must submit this assignment on time. There will be no extensions under any
circumstances such as technical problems or illness or any other problems. Any assign-
ment not submitted on time will receive the mark of 0. Therefore, aim to submit it
well in advance just in case there are any issues.
ˆ This assessment is 5% of your final mark. If you do not make a serious attempt
on this assessment then you cannot complete your degree. This means that
if you submit it after the deadline, even though you will get a 0 mark, you
can still get your degree. If you do not submit it by the end of Lent Term
or submit a blank page, this does not count as a serious attempt and then
you get an incomplete, which means you cannot get your degree. So make
a serious attempt!
ˆ There will be a submission link on Moodle.
ˆ Create one pdf file with all your solutions. Upload this one file on Moodle.
ˆ Do not put your name anywhere on the file or in the name of the file. The file must be
named with your candidate number and you must put your candidate number at the
front page of the pdf file.
ˆ You will be marked for correctness, presentation and clarity.
ˆ You can handwrite or type your solutions. If handwritten make sure they are legible.
ˆ There is no page limit but you will be marked down if you provide endless pages of
material that is not relevant to the question.
ˆ If you have any clarification questions either email me or submit a query on the anony-
mous forum.
ˆ You may use any results that we have covered in lecture or seminar. If you use some-
thing else then you must prove it.
Summative Assessment 1
1. (i) Find a maximum matching and a minimum vertex cover in the following graph.
You can use any method you like; you can also do it by inspection and you do not
need to show your work on how you found the maximum matching and minimum
vertex cover. But you must explain with a simple argument why your matching
and vertex cover are optimal.
(ii) For the maximum matching that you found in part (i) find the corresponding vertex
cover according to Ko¨nig’s theorem. For this part show all your work.
2. (a) Let x be an integral s-t-flow in a given network D = (V,A) with integral capacities
ua, source s ∈ V and sink t ∈ V .
Prove that there exist directed paths P1, P2, . . . , Pk, all from s to t, and values
λ1, λ2, . . . , λk, all positive and integer, so that
xa =

1≤i≤k:a∈A(Pi)
λi.
I.e., we can think of decomposing the flow into paths, with λi denoting how much
flow we send along path Pi.
(Hint: proceed by induction on value(x).)
(b) This “path decomposition” need not be unique. Give an example where two differ-
ent choices of paths and values work.
3. Let G = (V1 ∪ V2, E) be a bipartite graph (all edges have one endpoint in V1 and one
endpoint in V2). Prove that if C and C
′ are both vertex covers of G, then
(
V1 ∩ (C ∩
C ′)
) ∪ (V2 ∩ (C ∪ C ′)) is also a vertex cover.
4. Let G = (V1 ∪ V2, E) be a bipartite graph (all edges have one endpoint in V1 and one
endpoint in V2). For every set S ⊆ V1, let N(S) denote the set of nodes in V2 which are
adjacent to at least one node in S.
Prove that G has a matching of size |V1| if and only if for every subset S ⊆ V1, |N(S)| ≥
|S|.
(Hint: use Ko¨nig’s theorem.)
5. The bin packing problem is the following. We are given “bins” of size B, and a sequence
of item sizes a1, a2, . . . , an such that ai > 0. The bin packing problem asks for the smallest
number of bins needed to fit all the items, given that a bin can only contain a set of items
S ⊆ {1, 2, . . . , n} whose total size ∑i∈S ai is not larger than B. Suppose B/3 < ai ≤ B
for all i = 1, . . . , n. Formulate this problem as one of the problems we have studied so
far. Comment on possible algorithms to solve this problem.
Page 2
6. Give an efficient algorithm to determine if a given graph G = (V,E) is bipartite or not.
Show that your algorithm is correct, and give a reasonable upper bound on its running
time.
Page 3

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie