Name:Date:MA 515, Linear Programmingand Combinatorial OptimizationFall 2008, Final ExamThere are 150 possible points. You are not allowed to use your book ornotes.12Problem 1: (30 points) First, describe the main themes of this courseand their interactions. Second, choose a theorem that you feel excellentlyrepresents these themes and do the following:(1) State the theorem;(2) Give an example of the theorem in action; and(3) Explain why you chose this theorem, specifically addressing how itrelates to the main themes you described in the first part.3Problem 2: (40 points) Consider the following five contexts in whichwe have a “max=min” result.(1) Linear programming(2) Greedy algorithm for matroids(3) Matroid intersection(4) Bipartite matchings(5) Matchings in general graphsChoose four of these and make a precise statement of the “max=min” resultin each case. Sketch the proof for one of these, indicating clearly which oneyou have chosen.4Complete four of the following five problems, each worth 20points.Problem 3a: Consider the following matrix:A :=−1 −1 −1 01 0 0 −10 1 0 00 0 1 1Let M be the linear matroid determined by A. Provide a description of thematroid polytope for M as an H-polytope, and use linear programming tofind a maximal independent set in M .5Problem 3b: Construct a graph G on 6 vertices with 9 edges. Assign toeach of these edges a distinct positive weight. Choose a specific vertex, labelit v, and use Dijkstra’s algorithm to find all minimum-weight v − w-dipathsin G.6Problem 3c: Let G be a planar graph. Take any planar embedding ofG and form the planar dual G∗. Prove that the graphic matroid of G∗isthe dual of the graphic matroid of G.7Problem 3d: Let G be a graph with no loops and no multiple edges.Prove that a matching S of G is of maximum cardinality if and only if Ghas no augmenting path with respect to S.8Problem 3e: Given two matroids M1and M2on a common groundset E and an independent set S ∈ I(M1) ∩ I(M2), define the bipartiteaugmentation digraph for S and explain its role in the Cardinality Matroid-Intersection
View Full Document