Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird.

Folgende Situation wird dabei betrachtet: Gegeben sei eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugeordnet werden könnten. Ein Matching (in der Literatur manchmal auch Paarung) ist dann als eine solche Auswahl aus den möglichen Zuordnungen definiert, die kein Ding mehr als einmal zuordnet.

Die am häufigsten gestellten Fragen in dieser Situation sind dann die folgenden:

1. Wie findet man ein Matching, das eine maximale Anzahl an Dingen einander zuordnet?
   Dieses Problem ist das klassische Matchingproblem.
2. Gibt es ein Matching, das alle Dinge zuordnet? Wenn ja, wie viele?
   Solche Matchings heißen perfektes Matching. Die Anzahl der perfekten Matchings in einem Graphen ${\displaystyle G}$ wird meistens mit ${\displaystyle \Phi (G)}$ notiert.
3. Angenommen, man könnte quantifizieren „wie wichtig“ (oder „teuer“) die einzelnen Zuordnungen wären: Wie findet man dann ein Matching, das eine maximale Zahl von Dingen zuordnet und dabei ein möglichst großes (oder kleines) Gewicht hat?
   Dieses Problem heißt gewichtetes Matchingproblem. Zwischen einer Maximierungs- und einer Minimierungsaufgabe wird hier oftmals nicht unterschieden: Indem man bei allen Gewichten (Kosten) das Vorzeichen vertauscht, kann man beide Probleme ohne nennenswerten Aufwand ineinander überführen.
4. Angenommen, man hätte genau zwei Klassen von Dingen und angenommen, man wüsste, dass es ausschließlich zwischen diesen Klassen mögliche Zuordnungen gibt. Werden die Probleme 1–3 dadurch einfacher?
   Dieses Problem heißt bipartites (gewichtetes) Matchingproblem und ist ein viel diskutierter Spezialfall.
5. Kann man anderes Wissen, das man über die Struktur der möglichen Zuordnungen hat, ähnlich wie in 4 geschickt benutzen, um die Probleme 1–3 effizienter zu lösen?

Die Theorie um die Matchings untersucht möglichst effiziente Lösungsverfahren dieser Probleme, klassifiziert diese nach ihrer Laufzeit mit den Methoden der Komplexitätstheorie und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her.

Definitionen

• Ein einfacher Graph mit einem nicht erweiterbaren Matching (maximal matching)
• Derselbe Graph mit einem perfekten (wie auch größtmöglichen) Matching

Das oben beschriebene Problem lässt sich wie folgt formalisieren. Gegeben sei ein endlicher, ungerichteter Graph ${\displaystyle G=(V,E)}$. Eine Menge ${\displaystyle M\subseteq E}$ heißt Matching, wenn keine zwei Kanten aus ${\displaystyle M}$ einen Knoten gemeinsam haben. Ein Matching heißt

nicht erweiterbar (engl. maximal matching)

falls es keine Kante ${\displaystyle e\in E\setminus M}$ derart gibt, dass ${\displaystyle \{e\}\cup M}$ ein Matching ist. Maximale Matchings sind im Vergleich zu den folgenden Begriffen sehr einfach zu berechnen.

größtmöglich (engl. maximum matching)

falls ${\displaystyle M}$ als Menge eine maximale Kardinalität unter allen Matchings von ${\displaystyle G}$ hat. Maximum-Matchings sind maximal. Die Mächtigkeit eines Maximum-Matchings wird Matchingzahl genannt und mit ${\displaystyle \nu (G)}$ notiert.

perfekt

falls ${\displaystyle 2\cdot |M|=|V|}$ gilt, d. h. wenn jeder Knoten gematcht wurde. Perfekte Matchings sind Maximum-Matchings und damit auch maximal. Perfekte Matchings können als 1-Faktoren eines Graphen, das heißt 1-reguläre aufspannende Teilgraphen, aufgefasst werden. Dieser Auffassung folgend spricht man auch von faktorisierbaren Graphen, wenn sie einen 1-Faktor besitzen.

Eigenschaften

In jedem Graphen ohne isolierte Knoten ist die Summe der übereinstimmenden Matchingzahl und der Kantenüberdeckungszahl gleich der Anzahl der Knoten. Wenn es ein perfektes Matching gibt, sind sowohl die Matchingzahl als auch die Kantenüberdeckungszahl gleich ${\displaystyle {\tfrac {|V|}{2}}}$.

Wenn ${\displaystyle A}$ und ${\displaystyle B}$ zwei nicht erweiterbare Matchings sind, dann gilt ${\displaystyle |A|\leq 2\cdot |B|}$ und ${\displaystyle |B|\leq 2\cdot |A|}$. Das liegt daran, dass jede Kante in ${\displaystyle B\setminus A}$ höchstens mit zwei Kanten in ${\displaystyle A\setminus B}$ benachbart sein kann, weil ${\displaystyle A}$ ein Matching ist. Außerdem grenzt jede Kante in ${\displaystyle A\setminus B}$ an eine Kante in ${\displaystyle B\setminus A}$, weil ${\displaystyle B}$ nicht erweiterbar ist. Daher gilt

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

Daraus folgt

${\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|}$

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

Wenn der Graph zum Beispiel ein Pfad mit 3 Kanten und 4 Knoten ist, beträgt die Größe eines minimalen maximalen Matchings 1 und die Größe eines perfekten Matchings beträgt 2.

Kombinatorik

Die Anzahl der Matchings mit ${\displaystyle k}$ Kanten für bestimmte Graphen zeigt die folgende Tabelle:

Anzahl der Matchings mit k Kanten
vollständiger 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)!}}}$
vollständig bipartiter Graph ${\displaystyle K_{n,n}}$	${\displaystyle k!\cdot {\binom {n}{k}}^{2}={\frac {(n!)^{2}}{k!\cdot ((n-k)!)^{2}}}}$
Kreisgraph ${\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)!}}}$
Pfadgraph ${\displaystyle P_{n}}$	${\displaystyle {\binom {n-k}{k}}={\frac {(n-k)!}{k!\cdot (n-2\cdot k)!}}}$

Historisches

Als eine der frühesten systematischen Untersuchungen von Matchings wird ein Artikel von Julius Petersen angeführt, der 1891 über „Die Theorie der regulären graphs“ schrieb. Er untersuchte ein Zerlegungsproblem aus der Algebra, das David Hilbert 1889 gestellt hatte, indem er es als Graphenproblem formulierte. Letztlich bewies er darin folgendes:

Für alle Zahlen ${\displaystyle k\in \mathbb {N} }$ kann jeder ${\displaystyle 2k}$-reguläre Graph in disjunkte ${\displaystyle 2}$-Faktoren zerlegt werden. (1)

Jeder kubische, zusammenhängende Graph mit weniger als drei Brücken besitzt ein perfektes Matching. (2)

Die Tatsache (2), bekannt als Satz von Petersen, lässt sich auch als eine leichte Verallgemeinerung des Eulerkreisproblems formulieren.

Rückblickend erscheinen Petersens Argumente, mit denen er das Obige bewies, kompliziert und umständlich. Bei der weiteren Untersuchung etwa durch Brahana 1917, Errera 1922 und Frink 1926 sowie zusammenfassend durch Kőnig 1936 wurden aber viele Methoden der modernen Graphentheorie entwickelt oder zuerst systematisch formuliert. Petersens Denkansatz wurde dann von Bäbler 1938 1952 und 1954 sowie von Gallai 1950, Belck 1950 und schließlich Tutte auf andere reguläre Graphen übertragen.

In modernen Lehrbüchern und Vorlesungen tauchen Petersens ursprüngliche Resultate, wenn überhaupt, meist nur noch als Folgerungen aus den Resultaten von Tutte oder Hall auf. Im Buch von Diestel folgt die erste Aussage aus dem Heiratssatz von Hall. Die zweite Aussage wird auf den Satz von Tutte zurückgeführt.

Bipartite Matchings

Eines dieser frühen Resultate betrifft bipartite Graphen, die sich in der Folge als ein sehr natürlicher und aus heutiger Sicht für die Praxis zentraler Spezialfall herausgestellt haben. Kőnig und Egerváry untersuchten beide unabhängig voneinander das bipartite Matchingproblem und das Knotenüberdeckungsproblem und fanden dabei heraus, dass beide Probleme in dem folgenden Sinn äquivalent sind:

Die Größe einer minimalen Knotenüberdeckung und eines maximum-Matching stimmen auf bipartiten Graphen überein. (3)

Dieser Satz wird meistens Kőnig zugeschrieben oder Min-Max-Theorem bzw. Dualitätssatz genannt. Beide bewiesen die Aussage für endliche Graphen. Aharoni bewies 1984 die Aussage für überabzählbar unendliche Graphen. Ein elementarer Beweis von (3) findet sich in Lovász & Plummer 43, der von den meisten Lehrbüchern übernommen wurde. Bondy & Murty 200 führt den Satz auf ein Resultat der linearen Programmierung zurück: Ist ${\displaystyle A}$ die Inzidenzmatrix des Graphen ${\displaystyle G}$, dann lassen sich maximum Matchings als Lösungen von folgendem ganzzahligen linearen Programm auffassen:

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

Dabei ist ${\displaystyle e}$ der Einsvektor bestehend aus lauter Einsen. Das Programm des Knotenüberdeckungsproblems hat folgende Gestalt:

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

Diese Programme haben eine sogenannte primal-dual-Gestalt. Für Programme von dieser Gestalt wird in der Theorie der linearen Programme gezeigt, dass sie in ihren Optima übereinstimmen. Für bipartite Graphen lässt sich außerdem leicht zeigen, dass ${\displaystyle A}$ total unimodular ist, was in der Theorie der ganzzahligen linearen Programme ein Kriterium für die Existenz einer optimalen Lösung der Programme mit Einträgen nur aus ${\displaystyle \mathbb {Z} }$ (und damit in diesem speziellen Fall sogar aus ${\displaystyle \left\{0,1\right\}}$) ist, also genau solchen Vektoren, die auch für ein Matching bzw. für eine Knotenüberdeckung stehen können. Dieser Primal-Dual-Ansatz der linearen Programme scheint zunächst wenig mit der Matching-Theorie zu tun zu haben, stellt sich aber als einer der fruchtbarsten Ansätze zur effizienten Berechnung von Matchings, insbesondere im gewichteten Fall, heraus.

Es gibt eine ganze Vielzahl von Sätzen, die zum Satz von König äquivalent sind. Darunter der Satz von Birkhoff und von Neumann, der Satz von Dilworth und das Max-Flow-Min-Cut-Theorem für bipartite Graphen. Für die Matchingtheorie am interessantesten ist folgende Bedingung, die Hall 1935 angab, um bipartite Graphen mit perfektem Matching zu charakterisieren. Dieser Charakterisierungssatz ist ebenfalls äquivalent zum Satz von König.

Ein bipartiter Graph mit Knotenpartitionen ${\displaystyle S{\dot {\cup }}T}$ und o.B.d.A ${\displaystyle |S|\geq |T|}$ hat genau dann ein perfektes Matching, wenn für jede Auswahl von Knoten ${\displaystyle H\subseteq S}$ gilt: ${\displaystyle |N(H)|\geq |H|}$. Dabei ist ${\displaystyle N(H)}$ die Nachbarschaftsmenge von ${\displaystyle H}$. (4)

Aus (4) folgt schnell, dass sich unter den bipartiten Graphen genau alle regulären Graphen ${\displaystyle 1}$-faktorisieren lassen und die Aussage (1) von Petersen lässt elegant auf diese Folgerung zurückführen. Eine Verallgemeinerung dieses Resultats liefert eine Formel für die Größe eines maximum Matchings, die sogenannte König-Ore Formel:

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

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}$

using System;

class Program
{
	// Diese Methode verwendet Tiefensuche und stellt fest, ob es ein Matching mit dem Knoten mit startIndex gibt
	bool BipartiteMatching(bool[,] bipartiteGraph, int startIndex, bool[] visitedIndexes, int[] matchedIndexes, int n)
	{
		for (int targetIndex = 0; targetIndex < n; targetIndex++) // for-Schleife, die alle Indexe der Zielknoten durchläuft
		{
			if (bipartiteGraph[startIndex, targetIndex] && !visitedIndexes[targetIndex]) // Wenn die Knoten mit startIndex und targetIndex im bipartiten Graphen verbunden sind und Zielknoten nicht besucht ist
			{
				visitedIndexes[targetIndex] = true; // Setzt den Zielknoten auf besucht
				
				// Wenn der Knoten mit targetIndex nicht zugeordnet ist, wird er dem Knoten mit startIndex zugeordnet. Wenn der Knoten mit targetIndex auf besucht gesetzt ist, wird er im rekursiven Aufruf nicht erneut zugeordnet.
				if (matchedIndexes[targetIndex] == -1 || BipartiteMatching(bipartiteGraph, matchedIndexes[targetIndex], visitedIndexes, matchedIndexes, n)) // Rekursiver Aufruf der Methode mit dem Nachbarknoten als Startknoten
				{
					matchedIndexes[targetIndex] = startIndex;
					return true;
				}
			}
		}
		return false;
	}
	
	// Diese Methode gibt die Matchingzahl des bipartiten Graphen zurück
	int GetMatchingNumber(bool[,] bipartiteGraph, int m, int n)
	{
		int[] matchedIndexes = new int[n]; // Array, das die Indexe der zugeordneten Knoten speichert
		for (int i = 0; i < n; ++i) // for-Schleife, die alle Indexe der Zielknoten durchläuft
		{
			matchedIndexes[i] = -1; // Setzt alle Knoten auf nicht zugeordnet
		}
		int matchingNumber = 0; // Zählt die Anzahl der Matchings
		for (int startIndex = 0; startIndex < m; startIndex++) // for-Schleife, die alle Indexe der Startknoten durchläuft
		{
			bool[] visitedIndexes = new bool[n]; // Array, das die Indexe der besuchten Knoten speichert
			for (int i = 0; i < n; ++i) // for-Schleife, die alle Indexe der Zielknoten durchläuft
			{
				visitedIndexes[i] = false; // Setzt alle Knoten auf nicht besucht
			}
			if (BipartiteMatching(bipartiteGraph, startIndex, visitedIndexes, matchedIndexes, n)) // Untersucht, ob es ein Matching mit dem Knoten mit startIndex gibt
			{
				matchingNumber++;
			}
		}
		return matchingNumber;
	}
	
	// Hauptmethode, die das Programm ausführt
	public static void Main()
	{
		// Erzeugt einen bipartiten Graphen
		bool[,] bipartiteGraph = new bool[,]
			{{false, true, true, false, false, false},
			{true, false, false, true, false, false},
			{false, false, true, false, false, false},
			{false, false, true, true, false, false},
			{false, false, false, false, false, false},
			{false, false, false, false, false, true}};
		Program program = new Program();
		Console.WriteLine("Die Matchingzahl des bipartiten Graphen ist " + program.GetMatchingNumber(bipartiteGraph, 6, 6) + "."); // Ausgabe auf der Konsole
		
		Console.ReadLine();
	}
}

Allgemeiner Fall

Literatur

• M. D. Plummer, L. Lovász: Matching Theory (= Annals of Discrete Mathematics). 1. Auflage. Elsevier Science und Akadémiai Kiadó Budapest, Budapest 1986, ISBN 0-444-87916-1. 
• Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. A. Auflage. Springer, Berlin, 2006, ISBN 3-540-21391-0 (diestel-graph-theory.com). 
• Dieter Jungnickel: Graphs, Networks and Algorithms (= Algorithms and Computation in Mathematics. Band 5). 3. Auflage. Springer, 2007, ISBN 978-3-540-72779-8. 
• Guizhen Liu, Qinglin Roger Yu: Graph Factors and Matching Extensions. 1. Auflage. Springer, Beijing 2009, ISBN 978-3-540-93951-1. 
• Alexander Schrijver: Combinatorial Optimization – Polyhedra and Efficiency (= Algorithms and Combinatorics. A). Springer, Amsterdam 2003, ISBN 3-540-44389-4. 
• U.S.R. Murty, Adrian Bondy: Graph Theory (= Graduate Texts in Mathematics). Springer, 2008, ISBN 978-1-84996-690-0 (springer.com). 
• Mauro Dell’Amico, Silvano Martello, Rainer Burkard: Assignment Problems (Revised reprint). Society for Industrial and Applied Mathematics, Philadelphia 2012, ISBN 978-1-61197-222-1 (assignmentproblems.com). 
• 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. 

Historisch

• Dénes Kőnig: Theorie der endlichen und unendlichen Graphen – kombinatorische Topologie der Streckenkomplexe. (= Teubner Archiv zur Mathematik). 1. Auflage 1986. Teubner Verlagsgesellschaft, Leipzig 1936, ISBN 3-322-00303-5. 
• E. Keith Lloyd, Robin J. Wilson, Norman L. Biggs: Graph Theory 1736–1936. Oxford University Press, USA, 1999, ISBN 0-19-853916-9. 

Weblinks

Einzelnachweise

1. ↑ Yu & Liu 4.
2. ↑ Wolfram MathWorld: Matching
3. 1 2 Lovász & Plummer xi.
4. ↑ Yu & Liu 3.
5. ↑ Julius Petersen: Die Theorie der regulären graphs. In: Acta Mathematica. 15. Jahrgang, 1891, S. 193–220, doi:10.1007/BF02392606. 
6. ↑ David Hilbert: Über die Endlichkeit des Invariantensystems für binäre Grundformen. In: Mathematische Annalen. 33. Jahrgang, Nr. 2, 1889, S. 223–226. 
7. 1 2 3 Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. A. Auflage. Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 43 (diestel-graph-theory.com). 
8. ↑ Henry Roy Brahana: A Proof of Petersen’s Theorem. In: The Annals of Mathematics. 19. Jahrgang, Nr. 1, 1917, ISSN 0003-486X, S. 59–63, doi:10.2307/1967667. 
9. ↑ Alfred Errera: Une demonstration du théorème de Petersen. In: Mathesis. 36. Jahrgang, 1922, S. 56–61. 
10. ↑ Orrin Frink: A Proof of Petersen’s Theorem. In: The Annals of Mathematics. 27. Jahrgang, Nr. 4, 1926, ISSN 0003-486X, S. 491–493, doi:10.2307/1967699. 
11. ↑ Dénes Kőnig: Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe. 1936. 
12. ↑ Fridolin Bäbler: Über die Zerlegung regulärer Streckenkomplexe ungerader Ordnung. In: Commentarii Mathematici Helvetici. 10. Jahrgang, Nr. 1, 1938, ISSN 0010-2571, S. 275–287, doi:10.1007/BF01214296. 
13. ↑ Fridolin Bäbler: Bemerkungen zu einer Arbeit von Herrn R. Cantoni. In: Commentarii Mathematici Helvetici. 26. Jahrgang, 1952, ISSN 0010-2571, S. 117–118 (digizeitschriften.de). 
14. ↑ Fridolin Bäbler: Über den Zerlegungssatz von Petersen. In: Commentarii Mathematici Helvetici. 28. Jahrgang, Nr. 1, 1954, ISSN 0010-2571, S. 155–161, doi:10.1007/BF02566927. 
15. ↑ Tibor Gallai: On factorization of graphs. In: Acta Mathematica Academiae Scientiarum Hungaricae. 1. Jahrgang, 1950, ISSN 0236-5294, S. 133–153. 
16. ↑ Hans-Boris Belck: Reguläre Faktoren von Graphen. In: Journal für die reine und angewandte Mathematik (Crelles Journal). 1950. Jahrgang, Nr. 188, 1950, ISSN 0075-4102, S. 228–252, doi:10.1515/crll.1950.188.228. 
17. ↑ Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. A. Auflage. Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 45 (diestel-graph-theory.com). 
18. ↑ Ron Aharoni: Kőnig’s Duality Theorem for Infinite Bipartite Graphs. In: Journal of the London Mathematical Society. s2-29. Jahrgang, Nr. 1, 1984, ISSN 0024-6107, S. 1–12, doi:10.1112/jlms/s2-29.1.1. 
19. ↑ Lovász & Plummer 5-40.
20. ↑ Notizen zu einem Vortrag von Robert D. Borgersen: Equivalence of seven major theorems in combinatorics. (PDF; 66 kB). November 26, 2004.
21. ↑ K. Jacobs: Der Heiratssatz. In: Selecta Mathematica I. 1969, S. 103–141. 
22. ↑ Philip Hall: On representatives of subsets. In: Journal of London Mathematics Society. 10. Jahrgang, 1935, S. 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. Jahrgang, Nr. 9, 15. September 1957, S. 842–844 (pnas.org [PDF]). 
27. ↑ Aus didaktischen Gründen sehr stark vereinfacht nach Burkard, Dell’Amico & Martello 38. In der Referenz ist die Methode zum Finden eines verbessernden Pfades wesentlich detaillierter angegeben.
28. ↑ John E. Hopcroft, Richard M. Karp: An ${\displaystyle n^{5/2}}$ Algorithm for Maximum Matchings in Bipartite Graphs. In: SIAM Journal on Computing. 2. Jahrgang, Nr. 4, 1973, ISSN 0097-5397, S. 225–231, doi:10.1137/0202019 (englisch). 
29. ↑ Shimon Even, Robert E. Tarjan: Network flow and testing graph connectivity. In: SIAM Journal on Computing. 4. Jahrgang, Nr. 4, 1975, ISSN 0097-5397, S. 507–518, doi:10.1137/0204043 (englisch). 
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. Jahrgang, Nr. 4, 1991, ISSN 0020-0190, S. 237–240, doi:10.1016/0020-0190(91)90195-N (englisch). 
31. ↑ Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn: Automata, Languages and Programming. Band 443. Springer-Verlag, Berlin/Heidelberg 1990, ISBN 3-540-52826-1, Can a maximum flow be computed in ${\displaystyle {\mathcal {O}}(nm)}$ time?, S. 235–248 (englisch). 
32. ↑ Tomás Feder, Rajeev Motwani: Clique partitions, graph compression and speeding-up algorithms. twenty-third annual ACM symposium on Theory of computing. In: Proceedings of the twenty-third annual ACM symposium on Theory of computing. ACM, New York 1991, ISBN 0-89791-397-3, S. 123–133, doi:10.1145/103418.103424 (englisch). 
33. ↑ M. L Balinski, J. Gonzalez: Maximum matchings in bipartite graphs via strong spanning trees. In: Networks. 21. Jahrgang, Nr. 2, 1991, ISSN 1097-0037, S. 165–179, doi:10.1002/net.3230210203 (englisch). 
34. ↑ GeeksforGeeks: Maximum Bipartite Matching
35. 1 2 W. T Tutte: The factorization of linear graphs. In: Journal of the London Mathematical Society. 1. Jahrgang, Nr. 2, 1947, S. 107. 
36. ↑ Lovász & Plummer 84.
37. ↑ F. G. Maunsell: A note on Tutte’s paper “The factorization of linear graphs”. In: Journal of the London Mathematical Society. 1. Jahrgang, Nr. 1, 1952, S. 127 (englisch). 
38. ↑ W. T. Tutte: The factors of graphs. In: Classic Papers in Combinatorics. 1987, S. 164–178 (englisch). 
39. 1 2 T. Gallai: Neuer Beweis eines Tutte’schen Satzes, Magyar Tud. In: Akad. Kutató Int. Közl. 8. Jahrgang, 1963, S. 135–139. 
40. ↑ John H. Halton: A Combinatorial Proof of a Theorem of Tutte. In: Mathematical Proceedings of the Cambridge Philosophical Society. 62. Jahrgang, Nr. 04, 1966, S. 683–684, doi:10.1017/S0305004100040342 (englisch). 
41. ↑ M. L. Balinski: On perfect matchings. In: SIAM Review. 12. Jahrgang, 1970, S. 570–572 (englisch). 
42. ↑ I. Anderson: Perfect matchings of a graph. In: Journal of Combinatorial Theory, Series B. 10. Jahrgang, Nr. 3, 1971, S. 183–186 (englisch). 
43. ↑ W. Mader: 1-Faktoren von Graphen. In: Mathematische Annalen. 201. Jahrgang, Nr. 4, Dezember 1973, ISSN 0025-5831, S. 269–282, doi:10.1007/BF01428195. 
44. ↑ G. Hetyei: A new proof of a factorization theorem. In: Acta Acad. Paedagog. Civitate Pécs Ser. 6 Math. Phys. Chem. Tech. 16. Jahrgang, 1972, S. 3–6 (englisch). 
45. ↑ L. Lovasz: Three short proofs in graph theory. In: Journal of Combinatorial Theory, Series B. 19. Jahrgang, Nr. 3, 1975, S. 269–271 (englisch). 
46. ↑ Jungnickel 409.
47. ↑ J. Edmonds: Paths, trees, and flowers. In: Canadian Journal of mathematics. 17. Jahrgang, Nr. 3, 1965, S. 449–467, doi:10.4153/CJM-1965-045-4 (englisch). 
48. ↑ Jungnickel 396.
49. ↑ Betrachte dieses Beispiel nach Jungnickel 398.
50. ↑ Diese Idee wurde in Oldenbourg U. Pape, D. Conradt: Ausgewählte Operations Research Software in FORTRAN. Oldenbourg 1979, ISBN 3-486-23911-2, Maximales Matching in Graphen, S. 103–114.  vorgeschlagen. Jungnickel 399 hat ein Gegenbeispiel, das auf Christian Fremuth-Paeger zurückgeht.
51. ↑ Harold N. Gabow: An Efficient Implementation of Edmonds’ Algorithm for Maximum Matching on Graphs. In: Journal of the ACM. 23. Jahrgang, Nr. 2, April 1976, ISSN 0004-5411, S. 221–234, doi:10.1145/321941.321942 (englisch). 

Anmerkungen

1. ↑ Beachte den Unterschied zwischen einem maximalen Element und einem Maximum. Bei der Formalisierung wird darauf genauer eingegangen.
2. ↑ Es ist nicht bekannt, ob Petersen mit den Arbeiten von Euler 1736 zu diesem Problem vertraut war (Lovász & Plummer xi).
3. ↑ ${\displaystyle \oplus }$ notiert die symmetrische Differenz.
4. ↑ Programmiersprachen, die das Konzept Inf nicht unterstützen, können die künstlichen Kanten stattdessen mit einer absurd großen Zahl belegen. ${\displaystyle \textstyle \sum _{e\in E(G)}c(e)}$ genügt in jedem Fall.