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