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作业君