Graphs/Matching

Dietel Chapter 2: Matching on Graphs

Outline:

• Matching in bipartite graphs
• Matching in general graphs

Matching - defined as a set M of independent edges on a graph G

A matching matches vertices in a set U if every vertex in U is incident with an edge in M. (Recall from Graphs/Definitions that a vertex is incident with an edge e if v is in e, and two vertices are incident with an edge iff they are the endpoint of the edge. The notation for two vertices x and y being incident is xy.

Matching in Bipartite Graphs

Consider two partitions A and B on the graph G consisting of disjoint subsets (V,E). We call A and B a bipartition.

We wish to find various matchings in G.

Begin with arbitrary matchings, which will help to find matchings with maximum number of edges.

Consider an arbitrary vertex a in A that is unmatched. Now we construct an alternating path P that starts at a, and that contains alternating edges that are or are not in the matching edge set.

Then we can use that to turn M into a larger matching - if we take the symmetric difference of M and E(P) - the edges that are included in the alternating path - we essentially invert the labels of whether the edge is or is not in the matching set. If the path ends at an unmatched vertex of B, this will increase the size of the matching set by 1 because there will be 1 more unmatched edges than matched edges, and when we flip the labels, we end up with 1 more matched edge than unmatched edges.