Matching (graph theory)

The theory for finding matchings in graphs is in discrete mathematics an extensive subspecialty that is classified in the graph theory.

The following situation is considered here: Given a set of things, and these things information about which of them could be assigned to each other. A matching ( in the literature sometimes pairing) is then defined as such a selection from the possible mappings, which assigns no thing more than once.

The most frequently asked questions in this situation are then the following:

The theory about the matching examines the most efficient solution methods of these problems, classifies them according to their " difficulty " with the methods of complexity theory and establishes relationships of these problems to each other and forth to other problems in mathematics.

• 4.1 set of Tutte
• 4.2 Algorithm of Edmonds

Definitions

The same graph with a perfect (as maximum ) matching

The problem described above can be formalized as follows. Given a finite, undirected graph. A set is ( valid ) matching if no two edges have a node in common. A matching is called

For the weighted matching problem, a cost function plays a role. A valid matching is, then ...

Historical

As one of the earliest systematic studies of matching an article by Julius Petersen is mentioned that " The theory of regular graphs " wrote 1891. He examined a decomposition problem from algebra, which David Hilbert had made ​​in 1889, by formulating it as a graph problem. Ultimately, he proved the following fact:

The fact ( 2), known as a set of Petersen, can be formulated as a slight generalization of the Euler circuit problem. [A 2]

In retrospect, appear Petersen's arguments with which he proved the above, complicated and cumbersome. Upon further investigation, for example by Brahana 1917, Errera in 1922 and Frink 1926 and summarily Kőnig 1936 but many methods of modern graph theory have been developed or first formulated systematically. Petersen's approach was then 1950 and finally transferred from Bäbler 1938 1952 and 1954 as well as Gallai 1950 Belck to other Tutte regular graphs.

In modern textbooks and lectures Petersen immerse original results, if any, usually on only as inferences from the results of Tutte and Hall. In the book by Diestel the first statement set the marriage theorem of Hall follows. The second statement is returned to the set of Tutte.

Bipartite matchings

One of these early results relates bipartite graphs that have proven to as a very natural and from today's perspective, the practice of central special case. Kőnig and Egervary both studied independently the bipartite matching problem and the vertex cover problem and found out that both problems are equivalent in the following sense:

This phrase is usually attributed Kőnig or called min-max theorem and duality theorem. Both proved the statement for finite graphs. Aharoni proved 1984, the statement for uncountably infinite graphs. An elementary proof of ( 3) can be found in Lovasz & Plummer 43, which was adopted by most textbooks. Bondy & Murty 200 leads the pack on a result of linear programming back: Is the incidence matrix of the graph can then be conceived as a maximum matching solutions of the following integer linear program:

Here, the one vector consisting of all ones. The program of the vertex cover problem has the following form:

These programs have a so-called primal- dual form. For programs of this form is shown in the theory of linear programs that they agree in their optima. For bipartite graphs can also easily show that is " totally unimodular " which is a criterion for the existence of an optimal solution of the programs of entries is in the theory of integer linear programs only, ie exactly those vectors which are also for a matching or can represent a vertex cover. This primal- dual approach to linear programs seems at first to have little to do with the matching theory, but turns out to be one of the most useful approaches for efficient calculation of matching, particularly in the weighted case out.

There are a variety of phrases that are at the rate of Kőnig equivalent. Among the set of Birkhoff and von Neumann, the set of Dilworth and the Max -Flow Min -Cut Theorem for bipartite graphs. For the matching theory most interesting is the following condition, the Hall 1935 stated to characterize bipartite graphs with perfect matching. This characterization theorem is also equivalent to the set of Kőnig.

Quickly from (4 ) it follows that can be exactly all regular graph - factoring under the bipartite graph and the statement ( 1) of Petersen can be elegantly traced to this conclusion. A generalization of this result provides a formula for the size of a maximum matching, the so-called Kőnig -Ore formula:

Solution method

Input with any matching 1 repeat 2 Seeking improving path 3 If found: along Augmentiere. 4 until Search verbesserndem path was unsuccessful Output with maximum matching Many of the following concepts play in almost all solution process of matching problems play a role. If a graph is given with a matching, then is called a node of free ( in the literature also unpaired, exposed, available ... ) if he is no edge in the incident. Otherwise, the node is called saturated. A path in is called alternating if it contains edges alternately on and off. If the path begins and ends in a free node, ie, the path of improving or even augmentierend. The last term comes from the fact that, by [A 3] provides a larger matching. The following fundamental result of Berge in 1957 motivated the study of augmenting paths.

These terms correspond exactly to the language that is used in the treatment of flows in networks. This is no coincidence, because matching problems can be formulated in the language of network theory and solved by the method developed there. In the bipartite case, this reduction, as the following example shows, even almost trivial.

• Examples

The same graph has been improved along, now has a perfect matching.

Given a graph with node set. Construct a network. Here, and. Moreover, the continuation of the cost function that has all new edges with inf [A 4].

With the set of mountains can also be equal to an algorithm (I) for finding maximum matchings specify. Because everyone improving path to a given matching matcht another node and maximum node are to match on, the number of loop iterations is limited by asymptotically. A very naive method to find -improving paths represent so-called graph represents scans, such as a breadth-first search ( BFS) with a term of. Further, because the graph is bipartite, and thus the method specified in.

One of the earliest contributions to compute maximum matchings, which goes beyond the above mentioned naive method, was the algorithm of Hopcroft and Karp 1973. The basic idea follows the algorithm of Dinic, at every stage, where the algorithm according to an improving path searches (line 2), the shortest possible paths and, if possible " multiple simultaneous " searches.

Alt, Blum, Mehlhorn & Paul 1991 suggest an improvement of Hopcroft and Karp, by applying a scanning method for adjacency matrices by Cheriyan, Hagerup, and Mehlhorn 1990. A simple description of the method is also found in Burkard, Dell'Amico & Martello 47 ff spring and Motwani in 1991 have proposed a method based on the decomposition of bipartite cliques in and thus achieve an asymptotic running time of. A method that is not based on the idea of ​​augmenting paths, but so-called "strong spanning trees " used to have Balinski & Gonzalez proposed in 1991 and thus achieve a term of.

General case

Set of Tutte

While characterizations of matchings and efficient algorithms for determining were found relatively quickly after the formulation of matching as a problem, it took until 1947 to Tutte a characterization for matching formulate and could prove in general graphs. For this deep result can be all discussed so far relatively easy to derive. Tutte uses the simple fact that a component with an odd number of nodes can not have a perfect matching in a graph. So if a node-set can be found that more odd components has as nodes, then have a perfect matching of each such component is at least one node with a node are matched and can not be. It turns out that the existence of such a quantity graph describes not only without perfect matching, but characterized:

Such a set is called Tutte - quantity and the condition in (5 ) is called a Tutte's condition. That it is necessary for the existence of perfect matching, has been outlined and there is now much evidence that the condition is sufficient: Tutte's original proof formulated the problem as a matrix problem and used the idea of ​​pfaff between determinant. Elementary Abzählargumente were released relatively quickly thereafter, as generalized in Maunsell 1952, 1952 Tutte, Gallai 1963 Halton 1966 or Balinski 1970. Other evidence, such as Gallai in 1963, Anderson 1971 or marten 1973 set (4 ) of Hall systematically. Furthermore, there is evidence from the perspective of graph theory, which regarded the structure of graphene, which themselves have no perfect matching, but if an edge is added, the resulting graph such. This approach is taken by about 1972 or Hetyei Lovász 1975.

Algorithm of Edmonds

The first polynomial time algorithm for the classical matching problem is created by Jack Edmonds (1965). The basic structure of the method is the same algorithm (I ): You look for improving paths and is a maximum matching size, if no such can be found. To find an improving path, arises here but more difficult than in the bipartite case, because some new cases may occur. Edmonds search method designed by and by an alternating forest. This is a cycle-free graph with as many connected components as there are free nodes. Each free node is the root of a tree and is constructed so that for all other nodes of the uniquely determined - path is an alternating path. A node is called in then inside or odd, if and otherwise outside or straight. (Be the distance function here, so give the length of the uniquely determined - path to )

It is sufficient to reduce the view of the construction of an alternate tree. If this construction finds no augmenting path, it is reinitialized with a new free nodes and all edges already considered to be ignored. If there is no free node more, then there is no augmenting path. This alternating tree constructed Edmonds by starting adds or ignored by a free node by one, all edges. This following cases can occur for a new edge ( already belong to the tree ):

Flowers can, in contrast to the case can not be ignored. The node that connects the flower to the tree, can not fit into the scheme of internal and external nodes. The obvious idea, " both inside and outside " to treat him as leads to an incorrect algorithm. Treatment of flowers with contraction is adjacent to the approach of mountains, the central idea of Edmonds ' algorithm and the basis for many subsequent methods. Bipartite graphs containing no odd cycles and therefore no flowers. Edmonds ' algorithm is therefore reduced in the bipartite case, the method of Munkres.

One can see that the method outlined by Edmonds has a cost of. In case Edmonds reinitializes the search and therefore discards the already paid search effort. Gabow 1976 and Lawler have proposed a naive implementation that does not reject the search effort and achieved a term of. The example already follows this method.

• Example to Edmonds

The algorithm starts at the free node and with the alternating tree that contains only this node.

Consider edge. is an external node, and neither lie in and be added to the case.

Are once again on the case, the couple, and added.

The reduced graph.

The further reduced graph

From the free node is found, which closes in the augmenting path on the case. The foot lifter this path initially forms in which also lies already in itself.