Matching

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.

Contents

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 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, that is, M is maximal if it is not a proper subset of any other matching in graph G. In other words, a matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M.

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. Note that every maximum matching must be maximal, but not every maximal matching must be maximum.

A perfect matching is a matching which matches 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 maximum and hence maximal. In some literature, the term complete matching is used.

Given a matching M,

One can prove that a matching is maximum if and only if it does not have any augmenting path. (This result is sometimes called Berge's Lemma).

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 are inserted with value zero. Finding such a matching is known as the assignment problem. It can be solved by using a modified shortest path search in the augmenting path algorithm. If the Bellman-Ford algorithm is used, the running time becomes O(V^2 E), or the edge cost can be shifted with a potential to achieve O(V^2 \log(V) + V E) running time with the Dijkstra algorithm and Fibonacci heap. The remarkable Hungarian algorithm solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. The original approach of this algorithm need O(V^2E) running time, but it could be improved to O(V^2 \log(V) + V E) time with extensive use of priority queues.

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, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.

Notes

A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. If a graph has near-perfect matchings that omit each one of its vertices, it is a factor-critical graph.

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 Jack 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 (see Permanent). However, a remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time. Also, for bipartite graphs, the problem 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.

Matching problem is a special case of a more general problem called f-Factor problem.[1] A graph G=(V,E) has an f-Factor if and only if, G has a subgraph G', where the degree of each node v in G' is f(v). If f(v)=1 for all vertices, f-Factor problem reduces to matching problem. Hence matching problem is also referred to as 1-Factor problem.

In chemistry, a Kekulé structure of an aromatic compound consists of a perfect matching of its carbon skeleton, showing the locations of double bonds in the chemical structure. These structures are named after Friedrich August Kekulé von Stradonitz, who showed that benzene (in graph theoretical terms, a 6-vertex cycle) can be given such a structure.[2]

In 1971, Haruo Hosoya defined topological index (a graph invariant) as the total number of matchings of a graph plus 1[3]. The Hosoya index is often used in computer chemistry investigations for organic compounds. [4] [5]

Properties

A graph G with n vertices having no isolated vertex the matching number + edge covering number = n[6]

A graph with n vertices and a perfect matching has a matching number of n/2.

A maximal matching is at least half the size of a maximum matching

Let A and B be two maximal matchings. Each edge in A/B can be adjacent to at most 2 edges in B\A because B is a matching. Since each edge in B\A is adjacent to an edge in A\B by maximality, we see that

|A \setminus B| \le 2|B \setminus A|.

Further we get that

|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.

Let M be a maximal matching and let M^* be a maximum matching. Apply the above with A=M^* and B=M to get

2|M| \ge |M^*|.

See also

References

  1. ↑ 1.0 1.1 1.2 West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 0-13-014400-2 , chapter 3.
  2. ↑ See, e.g., Trinajstić, Nenad; Klein, Douglas J.; Randić, Milan (1986), "On some solved and unsolved problems of chemical graph theory", International Journal of Quantum Chemistry 30 (S20): 699–742, doi:10.1002/qua.560300762 .
  3. ↑ Hosoya H., Bull. Chem. Soc. Japan, 44, 1971, 2332
  4. ↑ Hosoya H., The Topological Index Z Before and After 1971, Internet Electronic Journal of Molecular Design, 2002, 1, 428–442. ISSN 1538–6414, http://www.biochempress.com
  5. ↑ Internet Electronic Journal of Molecular Design, Special issue dedicated to Professor Haruo Hosoya on the occasion of the 65th birthday, 2003, 2. ISSN 1538–6414, http://www.biochempress.com
  6. ↑ Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2: 133–138 .

Additional reading

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26". Introduction to Algorithms (second edition ed.). MIT Press and McGraw-Hill. pp. 643–700. ISBN 0-262-53196-8. 
  2. ^  András Frank (2004). On Kuhn's Hungarian Method - A tribute from Hungary. Technical Report Egerváry Research Group.
  3. ^ Michael L. Fredman and Robert E. Tarjan (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM (ACM Press) 34 (3): 595–615. doi:10.1145/28869.28874. ISSN 0004-5411. 
  4. S. J. Cyvin and Ivan Gutman (1988). Kekule Structures in Benzenoid Hydrocarbons. Springer-Verlag. 

External links