Matching

From Wikipedia, the free encyclopedia

This article is about mathematical matchings. For other senses of this word, see matching (disambiguation).

In the mathematical discipline of graph theory a matching or edge independent set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.

1 Definition
2 Matchings in bipartite graphs
3 Notes
4 Properties
5 See also
6 References

[edit] Definition

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

We say that a vertex is matched if it is incident to an edge in the matching. Otherwise the vertex is unmatched.

A maximum matching is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number of a graph is the size of a maximum matching.

A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching. In other words, a matching M of a graph G is maximal if every edge in G has non-empty intersection with at least one edge in M. Note that every maximum matching must be maximal, but not every maximal matching must be maximum.

A perfect matching is a matching which covers all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching. Every perfect matching is both maximum and maximal.

Given a matching M,

an alternating path is a path in which the edges belong alternatively to the matching and not to the matching.
an augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.

One can prove that a matching is maximum if and only if it does not have any augmenting path.

[edit] Matchings in bipartite graphs

Matching problems are often concerned with bipartite graphs. Finding a maximum bipartite matching^[1] (often called a maximum cardinality bipartite matching) in a bipartite graph $G = (V = (X, Y), E)$ is perhaps the simplest problem. The augmenting path algorithm finds it by finding an augmenting path from each $x \in X$ to $Y$ and adding it to the matching if it exists. As each path can be found in $O (E)$ time, the running time is $O (V E)$ . This solution is equivalent to adding a super source $s$ with edges to all vertices in $X$ , and a super sink $t$ with edges from all vertices in $Y$ , and finding a maximal flow from $s$ to $t$ . All edges with flow from $X$ to $Y$ then constitute a maximum matching. An improvement over this is the Hopcroft-Karp algorithm, which runs in $O(\sqrt{V} E)$ time.

In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching^[1] is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges inserted with value zero. Finding such a matching is known as the assignment problem. You can solve it by using a modified shortest path search in the augmenting path algorithm. If you use the Bellman-Ford algorithm, the running time becomes $O (V 2 E)$ . (You cannot use Dijkstras algorithm, as you get negative weight edges from $Y$ to $X$ .) The more specialised Hungarian algorithm solves the assignment problem in $O (V 3)$ time.

König's theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover. Via this result, the minimum vertex cover problem and maximum independent set problem may be solved in polynomial time for bipartite graphs.

[edit] Notes

Some people also allow graphs with an odd number of vertices to have a "perfect" matching. These matchings have exactly one unmatched vertex.

The marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.

There is a polynomial time algorithm to find a maximum matching in a graph that is not bipartite; it is due to Edmonds, is called the paths, trees, and flowers method, and uses bidirected edges.

A related problem is, given a graph G, to determine the number of perfect matchings in G. This problem is #P Complete. For bipartite graphs, it can be approximately solved in polynomial time. That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines, with high probability, the number of perfect matchings M within an error of at most εM.

[edit] Properties

for a graph G with n vertices having no isolated vertex the matching number + edge covering number = n (Tibor Gallai 1959)
a graph with n vertices and a perfect matching has a matching number of n/2

[edit] See also

[edit] References

Gallai, Tibor. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.3: Maximum bipartite matching, pp.664–669.
↑ West, Douglas Brent [1996] (1999). “3”, Introduction to Graph Theory, 2nd edition, Prentice Hall. ISBN 0-13-014400-2.