Graphs/Matching

Dietel Chapter 2: Matching on Graphs

Outline:

• Matching in bipartite graphs
• Matching in general graphs

Definition of Matching

A matching on a graph $G=(V,E)$ is a set of M independent edges.

A matching of $UsubseteqV$ (meaning U is either a subset of V or is equal to V) if each vertex in U is incident with an edge in the matching M. The vertices in U are matched by 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.

Suppose we have a subgraph H that is on G, $H\subseteq G$ . We are interested in finding a subgraph H such that the edges of H, E(H), form a matching of all the vertices in G. In this case, H is a 1-factor of G. The problem of finding such a subgraph H is the same as finding a spanning tree.

Matching in Bipartite Graphs

Consider two partitions A and B of the vertices of a graph G consisting of disjoint subsets, i.e., $G=(V,E)$. We call A and B a bipartition.

We wish to find matchings on the graph G. In particular, we wish to find a matching with as many edges as possible.

To do that, we can start with arbitrary matchings. We can use any given matching to find additional matchings, and use this to create a procedure to find matchings with a 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 given vertex in A, which we denote a, and that contains alternating edges that are alternatively in, and 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.

When searching for large matchings, alternating paths are important. The algorithmic problem of finding large matchings reduces to the problem of augmenting paths.

Outline of Remainder

This book has just completely left algorithms behind, and is solely concerned with the mathematics of graphs. This makes it hard to get through. From this point forward we'll be making some brief notes of the outlines of concepts Dietel covers, but not spending much time going through the details. Too many other things to focus on.

Matching in bipartite graphs:

• Maximum cardinality of a matching in G is equal to minimum cardinality of a vertex cover (Konig 1931)
• Necessary and sufficient conditions for existence of a 1-factor? Marriage condition - every subset of A must have enough neighbors in B.
• Marriage theorem: G contains a matching of A if and only if $|N(S)|\geq |S|\quad \forall S\subseteq A$
• Corollary: if G is k-regular with k >= 1, then G has a 1-factor.
• The marriage theorem is one of the most frequently applied graph theorems
• Can recast problems of bipartite matching to apply the marriage theorem
• Theorem: every regular graph of positive even degree has a 2-factor. (Petersen 1891)

Matching in general graphs:

• Tutte's condition: split graph into its odd components, each of which can be "shrunk" down to a single vertex. Then each odd component will send an edge out to another subgraph.
• This is a necessary condition for the existence of a 1-factor, but it is also sufficient.
• Theorem: a grpah G has a 1-factor if and only if number of odd components of G - S is less than the size of S, for all $S\subseteq V(G)$ (Tutte 1947)
• Corollary: every bridgeless cubic graph has a 1-factor. (Recall cubic graphs are 3-connected graphs, i.e., each vertex on the graph has 3 edges.)
• Gallai-Edmonds matching theorem

Path covers:

• Revisiting Konig's duality theorem for bipartite graphs
• The theorem gives the number of disjoint directed paths needed to cover the vertices of G
• But how many paths in a given directed graph suffice to cover its entire vertex set?
• Theorem: Every directed graph G has a path cover by at most alpha(G) paths, where alpha(G) is the maximum cardinality of an independent set of vertices in G (Gallai and Milgram 1960)
• Corollary: in every finite partially ordered set the minimum number of chains covering P is equal to the maximum cardinality of an antichain in P. (Whatever that means.)

Note:

• Lovasz and Plummer, Matching Theory, Annals of Discrete Math, 29, North Holland 1986.
• Hall's marriage theorem, proved in 1935, remains a commonly-applied graph theoretic result. It proves the general case of partition sets of different sizes. The special case where both partition sets have the same size was proved by Frobenius (1917) in a paper on determinants.