Name:Date:Time Begun:Time Ended:MA 515 Linear Programmingand Combinatorial OptimizationFall 2008, Exam 2This exam is a take-home exam. There are 120 possible points. You areallowed two hours to complete it and are not allowed to use your book ornotes. You may not use separate blocks of time totalling two hours; you areto take this exam in a single two-hour block of time. You should return thisexam to the instructor by the start of class on Friday, Nov 21, 2008.You are not to discuss any aspect of this exam with anyone until afterclass on Friday, Nov 21, 2008.12Prove one of the following two theorems, each worth 20 points.Problem 1a: State and prove Hall’s theorem. Be detailed. You mayassume that K¨onig’s theorem is true.Problem 1b: State the weighted greedy algorithm for weighted matroidsand prove that it produces maximum weight independent sets. Be detailed.3Complete five of the following six problems, each worth 20points.Problem 2a: Prove or disprove: If the linear programmax cTxAx ≤ bx ≥ 0is unbounded, then there is a subscript k such that the linear programmax xkAx ≤ bx ≥ 0is unbounded.4Problem 2b: Prove that the vertex-edge incidence matrix for a graphG, with no loops or multiple edges, is totally unimodular.5Problem 2c: Given a graphic matroid M, prove directly that the fol-lowing holds:X ∈ C(M ), Y ∈ C(M), X 6= Y, e ∈ X∩Y =⇒ ∃Z ⊂ (X∪Y )−e s.t. Z ∈ C(M ).6Problem 2d: Prove that the Fano matroid is not graphic.7Problem 2e: Provide an example of an edge-weighted graph with 8 edgesand 5 vertices. Use the greedy algorithm on the associated graphic matroidto find a maximum weight spanning tree. Show each step of the algorithm.8Problem 2f: Give a complete proof that the dual of a linear matroid isa linear matroid. You may assume any theorems from linear algebra thatyou find useful but not any homework problems from this