• Document: Solutions to Problem Set 2
  • Size: 155.02 KB
  • Uploaded: 2019-04-16 23:41:02
  • Status: Successfully converted

Some snippets from your converted document:

Massachusetts Institute of Technology 18.453: Combinatorial Optimization Michel X. Goemans 2017 Spring Solutions to Problem Set 2 2-3 Let U be any minimizer in the Tutte-Berge formula. Let K1 , · · · , Kk be the connected components of G \ U . Show that, for any maximum matching M , we must have that (a) M contains exactly b |K2i | c edges from G[Ki ] (the subgraph of G induced by the vertices in Ki ), i.e., G[Ki ] is perfectly matched for the even com- ponents Ki and near-perfectly matched for the odd components. (b) Each vertex u ∈ U is matched to a vertex v in an odd component Ki of G \ U. (c) The only unmatched vertices must be in odd components Ki of G \ U . Let U be a minimizer set and M be a maximum matching. Note that each edge in M is either an edge of some G[Ki ] or it is adjacent to some vertex in U . Also note that the number of edges injM adjacent k to U is at most |U | and the number of edges in M |Ki | from G[Ki ] is at most 2 . It follows that: k X |M | = |[M ∩ {e ∈ E : e adjacent to some v ∈ U }]| + |M ∩ E(G[Kk ])| i=1 k   X |Ki | 1 ≤ |U | + = (|V | + |U | − o(G \ U )) = |M |, i=1 2 2 where the last equality holds because M is maximum and U is minimizer to the Tutte- Berge formula. The previous formula implies that all the inequalities are equalities (if some of them is strict, we would have a contradiction). In particular we have that: |[M ∩ {e ∈ E : e adjacent to some v ∈ U }]| = |U |,   |Ki | and for every i, |M ∩ E(G[Kk ])| = . 2 j |Uk| edges adjacent to some vertex in U , and for every i, M (a) So M has exactly contains exacly |K2i | edges from G[Ki ]. In particular, G[Ki ] is perfectly matched for even components Ki and near-perfect matched for odd components. (b) From the previous analysis, every vertex u in U is matched to some vertex in G\U . Since all the vertices of the even components are already matched, u must be matched to some vertex in an odd component Ki of G \ U . Solutions to Problem Set 2 2017 Spring 2 (c) Finally, since all the vertices in U are matched to some vertex outside U , and all the vertices in each even component are perfectly matched, we obtain that the only unmatched vertices must be in odd components of G \ U . 2-6 Show that any 3-regular 2-edge-connected graph G = (V, E) (not necessarily bipartite) has a perfect matching. (A 2-edge-connected graph has at least 2 edges in every cutset; a cutset being the edges between S and V \ S for some vertex set S.) We will use the Tutte-Berge formula. Let U ⊆ V , and let W be any connected component of odd size of G\U . Because G is 3-regular, there is an odd number of edges between W and U (this follows by just counting the edges incident to a vertex of W , and observing that the edges inside W will be counted twice). Moreover, those edges are a cutset. Thus, that cutset has at least 3 edges. Because this is happening for every connected component of odd size, the 3-regularity of G implies that |U | ≥ o(G \ U ). In other words, by the Tutte-Berge formula, maxM |M | = |V |/2. P3 Consider S = {(1, 0, 1), (0, 1, 1), (1, 1, 1)} ⊆ R3 . Describe lin(S), aff(S), cone(S) and conv(S) (as a polyhedron, in terms of the linear equalities/inequalities). (1) lin(S) = R3 . (2) aff(S) = {(x, y, z) ∈ R3 : z = 1}. (3) cone(S) = {(x, y, z) ∈ R3 : z ≥ x ≥ 0, z ≥ y ≥ 0, z ≤ x + y}. (4) conv(S) = {(x, y, z) ∈ R3 : z = 1, 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, x + y ≥ 1}. P4 Let G = (V, E) be a bipartite graph having a perfect matching. Consider the set M ⊆ RE of the incidence vectors of all perfect matchings of G. We have seen a description of conv(M ) as a system of linear inequalities/equalities. Give a description (a

Recently converted files (publicly available):