4 - Matching

Summary

Recall that a matching of a graph G is a set S ⊂ E (G) such that ∣δ_G(v) ∩ S∣ ≤ 1, ∀ v ∈ V(G). Also, the matching S is perfect if ∣δ_G(v) ∩ S∣ = 1, ∀ v ∈ V(G). We have already studied matchings in bipartite graphs in some detail. König's Theorem provides a characterization of maximum-cardinality matchings for bipartite graphs (see the bipartite matching example, pp. 85, 100, and see p. 44). The total unimodularity of the vertex-edge incidence matrix of a bipartite graph yields a characterization of the characteristic vectors of matchings in bipartite graphs as extreme points of a polytope (see p. 44). The Matroid-Intersection Algorithms provide efficient methods for finding maximum-cardinality and maximum-weight matchings in bipartite graphs (see Chapter 3). In this chapter, an efficient direct algorithm is provided for finding a maximum-weight matching in a (complete) bipartite graph.

The study of matchings in nonbipartite graphs is more complicated.We will study an efficient algorithm for the problem of finding a maximum-cardinality matching in a general graph. Additionally, an inequality description of the convex hull of the characteristic vectors of matchings of a general graph is provided. Finally, some applications of minimum-weight matchings are described.

Augmenting Paths and Matroids

Let S be a matching of G. A path or cycle P of G is alternating with respect to S if the elements of P alternate, along the path or cycle, between elements of S and elements of E(G) \ S.