SKEDSOFT

Graph Theory

MATCHING THEORY: A matching in a graph is a set of edges with the property that no vertex is incident with more than one edge in the set. A vertex which is incident with an edge in the set is said to be saturated. A matching is perfect if and only if every vertex is saturated, that is ; if and only if every vertex is incident with precisely one edge of the matching.

Let G = (V, E) be a bipartite graph with V partitioned as X ∪ Y. (each edge of E has the form {x, y} with x ∈ X and y ∈ Y).

(i) A matching in G is a subset of E such that no two edges share a common vertex in X or Y.
(ii) A complete matching of X into Y is a matching in G such that every x ∈ X is the end point of an edge.

Let G = (V, E) be bipartite with V partitioned as X ∪ Y. A maximal matching in G is one that matches as many vertices in X as possible with the vertices in Y.
Let G = (V, E) be a bipartite graph where V is partitioned as X ∪ Y. If A ⊆ X, then δ(A) = | A | – | R(A) | is called the deficiency of A. The deficiency of graph G, denoted δ(G), is given by δ(G) = max {δ(A)/A ⊆ X}.

For example, in the graph shown on the left in Fig. (4.85)
(i) the single edge bc is a matching which saturates b and c, but neither a nor d ;
(ii) the set {bc, bd} is not a matching because vertex b belongs to two edges ;
(iii) the set {ab, cd} is a perfect matching.

Edge set {ab, cd} is a perfect matching in the graph on the left. In the graph on the right, edge set {u1, v2, u2v4, u3v1} is a matching which is not perfect.
Note that, if a matching is perfect, the vertices of the graph can be partitioned into two sets of equal size and the edges of the matching provide a one-to-one correspondence between these sets. In the graph on the left in Fig. (4.85), for instance, the edges of the perfect matching {ab, cd} establish a oneto- one correspondence between {a, c} and {b, d} : a → b, c → d. In the graph on the right of Fig. (4.85).
(i) the set of edges {u1v2, u2v4, u3v1} is a matching which is not perfect but which saturates v1 = {u1, u2, u3},
(ii) no matching can saturate v2 = {v1, v2, v3, v4} since such a matching would require four edges but then at least one ui would be incident with more than one edge.

In the figure to the right, if X = {u1, u2, u4}, then A(X) = {v3, v4}.
Since | X | ≤ | A(X) |, the workers in X cannot all find jobs for which they are qualified. There is no matching in this graph which saturates V1.

The bipartite graph shown in Fig. (4.87) has no complete matching. Any attempt to construct such a matching must include {x1, y1} and either {x2, y3} or {x3, y3}.
If {x2, y3} is included, there is no match for x3. Likewise, if {x3, y3} is included, we are not able to match x2.
If A = {x1, x2, x3} ⊆ X, then R(A) = {y1, y3}. With | A | = 3 > 2 = | R(A) |, it follows that no complete matching can exist.