Matching (graph theory)

Perfect pairing is a redirect to this article. for the concept of the non-degenerate bilinear form from linear algebra see degenerate bilinear form .

The theory of finding matchings in graphs is an extensive sub-area in discrete mathematics that is classified in graph theory .

The following situation is considered: A set of things is given and information about these things about which of them can be assigned to one another. A matching (sometimes also a pairing in the literature ) is then defined as such a selection from the possible assignments that no thing assigns more than once.

The most frequently asked questions in this situation are then:

1. How do you find a matching that assigns a maximum number of things to each other?
   This problem is the classic matching problem .
2. Is there a matching that assigns all things? If yes, how many?
   Such matchings are called perfect matching. The number of perfect matchings in a graph is usually noted. ${\displaystyle G}$ ${\displaystyle \Phi (G)}$
3. Assuming you could quantify “how important” (or “expensive”) the individual assignments would be: How do you find a matching that assigns a maximum number of things and has the greatest (or least) possible weight?
   This problem is called the weighted matching problem . Often no distinction is made between a maximization and a minimization task: By swapping the sign of all weights (costs) , both problems can be converted into one another without any significant effort.
4. Assume that you have exactly two classes of things and assume that you know that there are only possible assignments between these classes. Does this make problems 1-3 easier?
   This problem is called the bipartite (weighted) matching problem and is a much discussed special case.
5. Can other knowledge that one has about the structure of the possible assignments be used skillfully, similar to that in 4, to solve problems 1-3 more efficiently?

The theory of matchings examines the most efficient solution methods for these problems, classifies them according to their duration using the methods of complexity theory, and establishes relationships between these problems and other problems in mathematics .

Definitions

• 

  A simple graph with a non-expandable matching (maximum matching)

• 

  The same graph with a perfect (as well as largest possible) matching

The problem described above can be formalized as follows. Let a finite, undirected graph be given . A set is called matching if no two edges from a vertex have in common. A matching is called ${\displaystyle G=(V,E)}$ ${\displaystyle M\subseteq E}$ ${\displaystyle M}$

not expandable (maximum matching)

if there is no edge such that there is a matching. Compared to the following terms, maximum matchings are very easy to calculate. ${\displaystyle e\in E\setminus M}$ ${\displaystyle \{e\}\cup M}$

greatest possible (English maximum matching)

if the set has a maximum cardinality among all matchings of . Maximum matchings are maximum. The thickness of a maximum matching is called the matching number and is also noted. ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle \nu (G)}$

Perfect

if true, d. H. when every knot has been matched. Perfect matchings are maximum matchings and therefore also maximum. Perfect matchings can be understood as 1-factors of a graph , i.e. 1-regular spanning subgraphs . Following this view, one also speaks of factorizable graphs if they have a 1-factor. ${\displaystyle 2\cdot |M|=|V|}$

Definitions (weighted matching problem)

A cost function plays a role for the weighted matching problem . A matching is called ${\displaystyle c\colon E\to \mathbb {R} }$

maximum

if at most among all matchings of is. ${\displaystyle c(M):=\sum _{e\in M}c(e)}$ ${\displaystyle G}$

minimum maximum

if is minimal among all maximal matchings. ${\displaystyle c(M)}$

properties

In any graph without isolated nodes , the sum of the matching matching number and the edge coverage number is equal to the number of nodes. If there is a perfect match, both the matching number and the edge coverage number are the same . ${\displaystyle {\tfrac {|V|}{2}}}$

If and are two non-expandable matchings, then and . This is because every edge in can be adjacent to at most two edges in , because there is a matching. In addition, each edge in borders on an edge in because it cannot be expanded. Therefore applies ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|\leq 2\cdot |B|}$ ${\displaystyle |B|\leq 2\cdot |A|}$ ${\displaystyle B\setminus A}$ ${\displaystyle A\setminus B}$ ${\displaystyle A}$ ${\displaystyle A\setminus B}$ ${\displaystyle B\setminus A}$ ${\displaystyle B}$

${\displaystyle |A\setminus B|\leq 2\cdot |B\setminus A|}$

It follows

${\displaystyle |A|=|(A\cap B)\cup (A\setminus B)|=|A\cap B|+|A\setminus B|\leq 2\cdot |A\cap B|+2\cdot |B\setminus A|=2\cdot (|B\cap A|+|B\setminus A|)=2\cdot |(B\cap A)\cup (B\setminus A)|=2\cdot |B|}$

so . ${\displaystyle |A|\leq 2\cdot |B|}$

For example, if the graph is a path with 3 edges and 4 nodes , the size of a minimum maximum matching is 1 and the size of a perfect matching is 2.

Combinatorics

The following table shows the number of matchings with edges for certain graphs : ${\displaystyle k}$

Number of matchings with k edges
complete graph ${\displaystyle K_{n}}$	${\displaystyle {\frac {n!}{(2\cdot k)!!\cdot (n-2\cdot k)!}}={\frac {n!}{2^{k}\cdot k!\cdot (n-2\cdot k)!}}}$
fully bipartite graph ${\displaystyle K_{n,n}}$	${\displaystyle k!\cdot {\binom {n}{k}}^{2}={\frac {(n!)^{2}}{k!\cdot ((n-k)!)^{2}}}}$
Circle graph ${\displaystyle C_{n}}$	${\displaystyle {\frac {n}{n-k}}\cdot {\binom {n-k}{k}}={\frac {n\cdot (n-k-1)!}{k!\cdot (n-2\cdot k)!}}}$
Path graph ${\displaystyle P_{n}}$	${\displaystyle {\binom {n-k}{k}}={\frac {(n-k)!}{k!\cdot (n-2\cdot k)!}}}$

Historical

Sylvester gave an example for statement (2) that shows that it is no longer true for graphs with three or more bridges : a 3- regular graph with 16 nodes , three bridges and no perfect matching.

One of the earliest systematic studies of matchings is an article by Julius Petersen , who wrote in 1891 on "The theory of regular graphs". He investigated a decomposition problem from algebra that David Hilbert had posed in 1889 by formulating it as a graph problem. Ultimately, he proved the following:

For all numbers , every regular graph can be decomposed into disjoint factors. (1) ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle 2k}$ ${\displaystyle 2}$

Every cubic , connected graph with fewer than three bridges has a perfect matching. (2)

Fact (2), known as Petersen's theorem , can also be formulated as a slight generalization of the Euler's circle problem.

In retrospect, Petersen's arguments used to prove the above seem complicated and cumbersome. In the further investigation by Brahana 1917, Errera 1922 and Frink 1926 as well as in summary by Kőnig 1936 many methods of modern graph theory were developed or first formulated systematically. Petersen's approach was then transferred to other regular graphs by Bäbler in 1938, 1952 and 1954, as well as by Gallai in 1950, Belck in 1950 and finally Tutte.

In modern textbooks and lectures, Petersen's original results appear, if at all, mostly only as conclusions from the results of Tutte or Hall. In Diestel's book, the first statement follows from Hall's marriage sentence . The second statement is traced back to Tutte's sentence.

Bipartite matchings

One of these early results concerns bipartite graphs , which subsequently turned out to be a very natural and, from today's point of view, a central special case in practice. Kőnig and Egerváry both independently investigated the bipartite matching problem and the node coverage problem and found that both problems are equivalent in the following sense:

The size of a minimum node coverage and a maximum matching match on bipartite graphs. (3)

This theorem is mostly ascribed to Kőnig or called the Min-Max theorem or the duality theorem . Both proved the statement for finite graphs. In 1984 Aharoni proved the statement for uncountably infinite graphs. An elementary proof of (3) can be found in Lovász & Plummer 43, which has been adopted from most textbooks. Bondy & Murty 200 reduces the theorem to a result of linear programming : If the incidence matrix is the graph , then maximum matchings can be understood as solutions of the following integral linear program: ${\displaystyle A}$ ${\displaystyle G}$

${\displaystyle \max ex{\text{ unter }}Ax\leq 1\land x\geq 0}$

It is the one vector consisting of all ones. The program of the node coverage problem has the following form: ${\displaystyle e}$

${\displaystyle \min ye{\text{ unter }}yA\geq 1\land y\geq 0}$

These programs have a so-called primal-dual form. For programs of this shape it is shown in the theory of linear programs that they agree in their optima. For bipartite graphs it can also easily be shown that it is totally unimodular , which in the theory of integer linear programs is a criterion for the existence of an optimal solution of the programs with entries only off (and thus in this special case even off ), i.e. exactly those vectors that can also stand for a matching or for a node overlap . This primal-dual approach of the linear programs initially seems to have little to do with matching theory, but turns out to be one of the most fruitful approaches for the efficient calculation of matchings, especially in the weighted case. ${\displaystyle A}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \left\{0,1\right\}}$

There are quite a number of theorems equivalent to König's theorem. Among the set of Birkhoff and von Neumann , the set of Dilworth and the max-flow min-cut theorem for bipartite graphs . Most interesting for matching theory is the following condition that Hall stated in 1935 to characterize bipartite graphs with perfect matching. This characterization theorem is also equivalent to König's theorem.

A bipartite graph with nodes partitions and wlog has iff a perfect matching if for every choice of nodes applies: . Where is the neighborhood set of . (4) ${\displaystyle S{\dot {\cup }}T}$ ${\displaystyle |S|\geq |T|}$ ${\displaystyle H\subseteq S}$ ${\displaystyle |N(H)|\geq |H|}$ ${\displaystyle N(H)}$ ${\displaystyle H}$

From (4) it quickly follows that among the bipartite graphs exactly all regular graphs - can be factored and Petersen's statement (1) can elegantly be traced back 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: ${\displaystyle 1}$

${\displaystyle \nu (G)=|S|-\max _{H\subseteq S}\{|H|-|N(H)|\}}$

Solution method

Algorithm (I)

Eingabe ${\displaystyle G}$ mit einem beliebigen Matching ${\displaystyle M}$ 1. repeat 2. suche verbessernden Pfad ${\displaystyle P}$ 3. Falls gefunden: Augmentiere ${\displaystyle M}$ entlang ${\displaystyle P}$. 4. until Suche nach verbesserndem Pfad war erfolglos Ausgabe ${\displaystyle G}$ mit maximum Matching ${\displaystyle M}$

Many of the following concepts play a role in almost all methods of solving matching problems. Is a graph with a matching given, is called a node of free (in the literature unpaired, exposed, available ...) if it no edge in is incident. Otherwise the knot is called saturated. A path in is called alternating if it contains alternating edges out and out . If this path begins and ends in a free node, the path is called improving or augmenting. The last designation comes from the fact that by a greater matching than delivers. The following basic result from Berge 1957 motivates the study of augmenting paths. ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle M^{c}}$ ${\displaystyle P}$ ${\displaystyle M\oplus P}$ ${\displaystyle M}$

A matching is if and maximum when there is no improving path in respect there. ${\displaystyle G}$ ${\displaystyle M}$

These terms correspond exactly to the language that is also used when dealing with rivers in networks . This is no coincidence, because matching problems can be formulated in the language of network theory and solved with the methods developed there. In the bipartite case, as the following example shows, this reduction is almost trivial. Given a graph with a set of nodes . Construct a network . There is and . In addition, the continuation of the cost function , the all new edge with proven. ${\displaystyle G}$ ${\displaystyle V(G)=S{\dot {\cup }}T}$ ${\displaystyle N=(G',u,\sigma ,\tau )}$ ${\displaystyle V(G')=V(G)\cup \{\sigma ,\tau \}}$ ${\displaystyle E(G')=E(G)\cup \{(\sigma ,s):s\in S\}\cup \{(t,\tau ):t\in T\}}$ ${\displaystyle u}$ ${\displaystyle c}$Inf

With Berge's theorem , an algorithm (I) for finding maximum matchings can also be specified. Because every improving path matches a further node for a given matching and a maximum of nodes are to be matched, the number of loop passes is asymptotically limited . So-called graph scans , such as a breadth first search (BFS) with a duration of . Furthermore , because the graph is bipartite and thus the given method is in . ${\displaystyle {\tfrac {n}{2}}}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n+m)}$ ${\displaystyle m\in {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

One of the earliest contributions to computing maximum matchings that goes beyond the naive method cited above was the algorithm by Hopcroft and Karp 1973. The basic idea follows the algorithm of Dinic (with which the problem can be solved with the same asymptotic running time ), which in every phase where the algorithm is looking for an improving path (line 2), the shortest possible paths and, if possible, “several at the same time” searches.

Alt, Blum, Mehlhorn & Paul 1991 propose an improvement on Hopcroft & Karp by using a scanning method for adjacency matrices according to Cheriyan, Hagerup, and Mehlhorn 1990. A simple description of the method can also be found in Burkard, Dell'Amico & Martello 47 ff. Feder and Motwani 1991 proposed a method based on the decomposition of into bipartite cliques and thus achieve an asymptotic term of . A method that is not based on the idea of ​​augmenting paths , but uses so-called "strong spanning trees ", was proposed by Balinski & Gonzalez in 1991 and thus achieved a duration of . ${\displaystyle G}$ ${\displaystyle {\mathcal {O}}({\sqrt {n}}m\log(n^{2}/m)/\log n)}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

General case

Set of Tutte

→ Main article : Tutte's sentence

While characterizations of matchings and efficient algorithms for determining were found relatively quickly after the formulation of matchings as a problem, it was not until 1947 that Tutte was able to formulate and prove a characterization for perfect matchings in general graphs . From this deep-seated result, all of the previously discussed results can be derived comparatively easily. Tutte uses the simple fact that a component with an odd number of nodes in a graph cannot have a perfect matching. If a set of nodes can be found in such a way that it has more odd components than nodes , then at least one node would have to be matched with a node from each such component for perfect matching , and that cannot be the case. It turns out that the existence of such a set of graphs without perfect matching not only describes, but characterizes: ${\displaystyle S}$ ${\displaystyle G-S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

A graph has a perfect matching if and only if for any amount applies: . ( gives the number of odd components of a graph.) (5) ${\displaystyle G}$ ${\displaystyle T\subseteq V(G)}$ ${\displaystyle c(G-T)\leq |T|}$ ${\displaystyle c}$

Such a set is called the Tutte set and the condition in (5) is called the Tutte condition. That it is necessary for the existence of perfect matching has already 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's determinant . Elementary counting arguments were published relatively quickly afterwards, as in Maunsell 1952, Tutte 1952, Gallai 1963, Halton 1966 or Balinski 1970. Other proofs such as Gallai 1963, Anderson 1971 or Marder 1973 systematically generalize Hall's theorem (4). There is also evidence from the perspective of graph theory that looks at the structure of graphs that do not have a perfect matching themselves, but if an edge is added, the resulting graph has one. Hetyei 1972 and Lovász 1975 follow this approach. ${\displaystyle T}$

It is not enough to first look for and contract all the flowers and then do a breadth-first search . The priority of the case distinctions plays a role in the correctness of the algorithm . In this example the contracted graph does not contain an augmenting path , but the output graph does .

Edmonds algorithm

The first polynomial time algorithm for the classic matching problem comes from Jack Edmonds (1965). The basic structure of the method corresponds to algorithm (I): It searches for improving paths and returns a maximum matching if none can be found. Finding an improving path turns out to be more difficult here than in the bipartite case, because some new cases can arise. Edmond's search method gradually constructs an alternating forest . This is a circle-free graph with as many connected components as there are free nodes . Every free node is the root of a tree and is constructed in such a way that the uniquely determined - path is an alternating path for all other nodes . A node in is then called inside or odd, if and otherwise outside or even. Let the distance function be in here , so give the length of the uniquely determined - -path. ${\displaystyle F}$ ${\displaystyle r_{i}}$ ${\displaystyle T\subset F}$ ${\displaystyle F}$ ${\displaystyle v\in F}$ ${\displaystyle r_{i}}$ ${\displaystyle v}$ ${\displaystyle v\in F}$ ${\displaystyle \operatorname {d} (r_{i},v)\equiv 1\mod 2}$ ${\displaystyle \operatorname {d} }$ ${\displaystyle T}$ ${\displaystyle r_{i}}$ ${\displaystyle v}$

It is sufficient to reduce the consideration to the construction of an alternating tree . If this construction does not find an augmenting path , it is reinitialized with a new free node and all edges already considered are ignored. If there is no longer any free node, then there is no augmenting path either. Edmonds constructs this alternating tree by gradually adding or ignoring all edges starting from a free node. The following cases can occur for a new edge ( already belongs to the tree): ${\displaystyle e=uv}$ ${\displaystyle u}$

1. If there is an inner node, only edges can be added to because it should be alternated. This edge is clearly given by. ${\displaystyle u}$ ${\displaystyle e\in M}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle (u~\operatorname {match} (u))}$
2. If there is an outside knot, then  ... ${\displaystyle u}$ ${\displaystyle v}$
   1. be free and not yet in . Then the - path is augmenting. ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle v}$
   2. be paired and neither nor is in . Then and can be added to. ${\displaystyle v}$ ${\displaystyle \operatorname {match} (v)}$ ${\displaystyle T}$ ${\displaystyle v}$ ${\displaystyle \operatorname {match} (v)}$ ${\displaystyle T}$
   3. already contained in as an inner node. This closes a straight circle. These edges can be ignored. ${\displaystyle T}$ ${\displaystyle e}$
   4. already be included in as an outer node. Then completes an odd alternating circle ; a so-called blossom. Edmonds pulls the knots in into a pseudo knot along with the incidences of all the knots . (This operation can also be described as “forming the quotient graph ” ) It then reinitializes the search in and specifies a method for lifting an augmenting path found there to an augmenting path in . ${\displaystyle T}$ ${\displaystyle e}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle b}$ ${\displaystyle B}$ ${\displaystyle G'=G/B}$ ${\displaystyle G'}$ ${\displaystyle P'}$ ${\displaystyle P}$ ${\displaystyle G}$

Unlike Fall , flowers can not be ignored. The knot that connects the flower to the tree cannot be classified in the scheme of inner and outer knots. The obvious idea of ​​treating it as "both inside and outside" leads to a wrong algorithm. The treatment of flowers with contraction is, along with Berge's approach, the central idea of ​​Edmonds' algorithm and the basis of many later methods. Bipartite graphs do not contain any odd circles and therefore no flowers. Edmonds 'algorithm is therefore reduced to Munkres' method in the bipartite case. ${\displaystyle 3}$

One can see that the method outlined by Edmonds has an expense of . In this case, Edmonds reinitializes the search and discards the search effort already made. Gabow 1976 and Lawler proposed a naive implementation that does not discard the search effort and achieves a runtime of . The example already follows this method. ${\displaystyle {\mathcal {O}}(n^{4})}$ ${\displaystyle 2.4}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

• Example at Edmonds
• 

  The reduced graph . ${\displaystyle G'=G/B}$

• 

  ${\displaystyle G'}$with another flower . ${\displaystyle B'}$

• 

  The further reduced graph ${\displaystyle G''=G'/B'}$

• 

  From the free node is found, which closes in the augmenting path after the fall . The lifting of this path initially delivers in , but it is already in itself. ${\displaystyle b'}$ ${\displaystyle 9}$ ${\displaystyle 2.1}$ ${\displaystyle G''}$ ${\displaystyle P''=(1~2~b'~9)}$ ${\displaystyle P=(1~2~3~5~6~7~8~9)}$ ${\displaystyle G'}$ ${\displaystyle G}$

literature

• L. Lovász, M. D Plummer: Matching Theory  (= Annals of Discrete Mathematics), 1st edition, Elsevier Science and Akadémiai Kiadó Budapest, Budapest 1986, ISBN 0-444-87916-1 .
• Reinhard Diestel: Graph Theory , 3rd, revised. and exp. A .. Edition, Springer, Berlin, 2006, ISBN 3-540-21391-0 .
• Dieter Jungnickel: Graphs, Networks and Algorithms  (= Algorithms and Computation in Mathematics), 3rd edition, Volume 5, Springer, 2007, ISBN 978-3-540-72779-8 .
• Qinglin Roger Yu, Guizhen Liu: Graph Factors and Matching Extensions , 1st edition, Springer, Beijing 2009, ISBN 3-540-93951-2 .
• Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency  (= Algorithms and Combinatorics), Volume A. Springer, Amsterdam 2003, ISBN 3-540-44389-4 .
• Adrian Bondy, USR Murty: Graph Theory  (= Graduate Texts in Mathematics). Springer, 2008, ISBN 1-84996-690-7 .
• Rainer Burkard, Mauro Dell'Amico, Silvano Martello: Assignment Problems (Revised reprint) . Society for Industrial and Applied Mathematics, Philadelphia 2012, ISBN 978-1-61197-222-1 .
• David S. Johnson: Network Flows and Matching: First Dimacs Implementation Challenge . American Mathematical Society, 1993, ISBN 0-8218-6598-6 .
• Eugene Lawler: Combinatorial Optimization: Networks and Matroids . Dover Publications, Rocquencourt 1976, ISBN 0-03-084866-0 .

Historical

• Dénes Kőnig: Theory of finite and infinite graphs - combinatorial topology of line complexes.  (= Teubner Archive for Mathematics), 1st edition 1986th edition, Teubner Verlagsgesellschaft, Leipzig 1936, ISBN 3-322-00303-5 .
• Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson: Graph Theory 1736-1936 . Oxford University Press, USA, 1999, ISBN 0-19-853916-9 .

Web links

Commons : Matching  - collection of images, videos and audio files

Individual evidence

1. ↑ Yu & Liu 4.
2. ^ Wolfram MathWorld: Matching
3. ↑ ^{a b} Lovász & Plummer xi.
4. ↑ Yu & Liu 3.
5. ↑ Julius Petersen: The theory of regular graphs . In: Acta Mathematica . 15, 1891, pp. 193-220. doi : 10.1007 / BF02392606 .
6. ↑ David Hilbert : On the finiteness of the invariant system for binary basic forms . In: Mathematical Annals . 33, No. 2, 1889, pp. 223-226.
7. ↑ ^{a b c} Reinhard Diestel: Graph Theory , 3rd, revised. and exp. A .. Edition, Springer, Berlin, 2006, ISBN 3-540-21391-0 , p. 43.
8. ↑ Henry Roy Brahana: A Proof of Petersen's Theorem . In: The Annals of Mathematics . 19, No. 1, 1917, ISSN  0003-486X , pp. 59-63. doi : 10.2307 / 1967667 .
9. ^ Alfred Errera: Une demonstration du théorème de Petersen . In: Mathesis . 36, 1922, pp. 56-61.
10. ↑ Orrin Frink: A Proof of Petersen's Theorem . In: The Annals of Mathematics . 27, No. 4, 1926, ISSN  0003-486X , pp. 491-493. doi : 10.2307 / 1967699 .
11. ↑ Dénes Kőnig: Theory of finite and infinite graphs; combinatorial topology of the route complexes. 1936.
12. ↑ Fridolin Bäbler: On the decomposition of regular route complexes of odd order . In: Commentarii Mathematici Helvetici . 10, No. 1, 1938, ISSN  0010-2571 , pp. 275-287. doi : 10.1007 / BF01214296 .
13. ↑ Fridolin Bäbler: Comments on a work by Mr. R. Cantoni. . In: Commentarii Mathematici Helvetici . 26, 1952, ISSN  0010-2571 , pp. 117-118.
14. ↑ Fridolin Bäbler: About Petersen's decomposition theorem . In: Commentarii Mathematici Helvetici . 28, No. 1, 1954, ISSN  0010-2571 , pp. 155-161. doi : 10.1007 / BF02566927 .
15. ^ Tibor Gallai: On factorization of graphs . In: Acta Mathematica Academiae Scientiarum Hungaricae . 1, 1950, ISSN  0236-5294 , pp. 133-153.
16. ↑ Hans-Boris Belck: Regular factors of graphs. . In: Journal for Pure and Applied Mathematics (Crelles Journal) . 1950, No. 188, 1950, ISSN  0075-4102 , pp. 228-252. doi : 10.1515 / crll.1950.188.228 .
17. ↑ Reinhard Diestel: Graph Theory , 3rd, revised. and exp. A .. Edition, Springer, Berlin, 2006, ISBN 3-540-21391-0 , p. 45.
18. ^ Ron Aharoni: Kőnig's Duality Theorem for Infinite Bipartite Graphs . In: Journal of the London Mathematical Society . s2-29, No. 1, 1984, ISSN  0024-6107 , pp. 1-12. doi : 10.1112 / jlms / s2-29.1.1 .
19. ^ Lovász & Plummer 5-40.
20. ^ Notes on a lecture by Robert D. Borgersen: Equivalence of seven major theorems in combinatorics. (PDF; 66 kB). November 26, 2004.
21. ↑ K. Jacobs: The marriage rate . In: Selecta Mathematica I . 1969, pp. 103-141.
22. ^ Philip Hall: On representatives of subsets . In: Journal of London Mathematics Society . 10, 1935, pp. 26-30.
23. ↑ Jungnickel 216.
24. ↑ Yu & Liu 9.
25. ^ Bondy & Murty 422.
26. ↑ Claude Berge: Two theorems in graph theory . In: Proceedings of the National Academy of Sciences . 43, No. 9, September 15, 1957, pp. 842-844.
27. ↑ For didactic reasons very much simplified according to Burkard, Dell'Amico & Martello 38. In the reference, the method for finding an improving path is given in much more detail.
28. ^ John E. Hopcroft, Richard M. Karp: An Algorithm for Maximum Matchings in Bipartite Graphs ${\displaystyle n^{5/2}}$ . In: SIAM Journal on Computing . 2, No. 4, 1973, ISSN  0097-5397 , pp. 225-231. doi : 10.1137 / 0202019 .
29. ^ Shimon Even, Robert E. Tarjan: Network flow and testing graph connectivity . In: SIAM Journal on Computing . 4, No. 4, 1975, ISSN  0097-5397 , pp. 507-518. doi : 10.1137 / 0204043 .
30. ^ H. Alt, N. Blum, K. Mehlhorn, M. Paul: Computing a maximum cardinality matching in a bipartite graph in time ${\displaystyle {\mathcal {O}}(n^{1.5}{\sqrt {m/\log n}})}$ . In: Information Processing Letters . 37, No. 4, 1991, ISSN  0020-0190 , pp. 237-240. doi : 10.1016 / 0020-0190 (91) 90195-N .
31. ↑ Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn: Can a maximum flow be computed in time? ${\displaystyle {\mathcal {O}}(nm)}$. In: Automata, Languages ​​and Programming , Volume 443. Springer-Verlag, Berlin / Heidelberg 1990, ISBN 3-540-52826-1 , pp. 235-248.
32. ↑ Tomás Feder: Clique partitions, graph compression and speeding-up algorithms . In: Proceedings of the twenty-third annual ACM symposium on Theory of Computing . ACM, pp. 123-133. ISBN 0-89791-397-3 doi : 10.1145 / 103418.103424
33. ↑ M. L Balinski, J. Gonzalez: Maximum matchings in bipartite graphs via strong spanning trees . In: Networks . 21, No. 2, 1991, ISSN  1097-0037 , pp. 165-179. doi : 10.1002 / net.3230210203 .
34. ↑ ^{a b} W. T Tutte: The factorization of linear graphs . In: Journal of the London Mathematical Society . 1, No. 2, 1947, p. 107.
35. ^ Lovász & Plummer 84.
36. ↑ FG Maunsell: A note on Tutte's paper “The factorization of linear graphs” . In: Journal of the London Mathematical Society . 1, No. 1, 1952, p. 127.
37. ^ WT Tutte: The factors of graphs . In: Classic Papers in Combinatorics . 1987, pp. 164-178.
38. ^ ^{A b} T. Gallai: New proof of Tutte's theorem, Magyar Tud . In: Akad. Kutató Int. Kozl . 8, 1963, pp. 135-139.
39. ↑ John H. Halton: A Combinatorial Proof of a Theorem of Tutte . In: Mathematical Proceedings of the Cambridge Philosophical Society . 62, No. 04, 1966, pp. 683-684. doi : 10.1017 / S0305004100040342 .
40. ^ ML Balinski: On perfect matchings . In: SIAM Review . 12, 1970, pp. 570-572.
41. ↑ I. Anderson: Perfect matchings of a graph . In: Journal of Combinatorial Theory, Series B . 10, No. 3, 1971, pp. 183-186.
42. ^ W. Mader: 1-factors of graphs . In: Mathematical Annals . 201, No. 4, December 1973, ISSN  0025-5831 , pp. 269-282. doi : 10.1007 / BF01428195 .
43. ↑ G. Hetyei: A new proof of a factorization theorem . In: Acta Acad. Pedagogue. Civitate Pécs Ser. 6 Math. Phys. Chem. Tech . 16, 1972, pp. 3-6.
44. ^ L. Lovasz: Three short proofs in graph theory . In: Journal of Combinatorial Theory, Series B . 19, No. 3, 1975, pp. 269-271.
45. ↑ Jungnickel 409.
46. ^ J. Edmonds: Paths, trees, and flowers . In: Canadian Journal of mathematics . 17, No. 3, 1965, pp. 449-467. doi : 10.4153 / CJM-1965-045-4 .
47. ↑ Jungnickel 396.
48. ↑ Consider this example from Jungnickel 398.
49. ↑ This idea was found in U. Pape, D. Conradt: Maximal Matching in Graphs . In: Selected Operations Research Software in FORTRAN 1979, ISBN 3-486-23911-2 , pp. 103-114. suggested. Jungnickel 399 has a counterexample that goes back to Christian Fremuth-Paeger.
50. ↑ Harold N. Gabow: An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs . In: Journal of the ACM . 23, No. 2, April 1976, ISSN  0004-5411 , pp. 221-234. doi : 10.1145 / 321941.321942 .

Remarks

1. ↑ Note the difference between a maximum element and a maximum . This will be discussed in more detail in the formalization .
2. ↑ It is not known whether Petersen was familiar with the work of Euler in 1736 on this problem ( Lovász & Plummer xi ).
3. ↑ notes the symmetrical difference . ${\displaystyle \oplus }$
4. ↑ Programming languages ​​that Infdo not support the concept can instead assign an absurdly large number to the artificial edges. is sufficient in any case. ${\displaystyle \textstyle \sum _{e\in E(G)}c(e)}$