Matching (Graphentheorie)

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 eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugerodnet 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 finde ich 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 Anzah der perfekten Matchings in einem Graphen $G$ wird meistens mit $\Phi (G)$ notiert.
3. Angenommen, ich könnte quantifizieren „wie wichtig“ (oder „teuer“) mir die einzelnen Zuordnungen wären: Wie finde ich ein 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 ich bei allen Gewichten (Kosten) das Vorzeichen vertausche kann ich beide Probleme ohne nennenswerten Aufwand ineinander überführen.
4. Angenommen, ich hätte genau zwei Klassen von Dingen und angenommen, ich wüsste, dass es ausschließlich zwischen diesen Klassen mögliche Zuordnungen gibt. Werden die Probleme 1-3 dadurch einfacher?
   Dises Problem heißt Bipartites (gewichtetes) Matchingproblem und ist ein viel diskutierter Spezialfall.
5. Kann ich anderes Wissen, das ich über die Struktur der möglichen Zuordnungen habe, ä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 „Schwierigkeit“ mit den Methoden der Komplexitätstheorie und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her.

Formalisierung

• 
  Ein einfacher Graph mit einem maximalen Matching
• 
  Der selbe Graph mit einem perfekten Matching

Das oben beschriebene Problem lässt sich wie folgt formalisieren. Gegeben ein endlicher, ungerichteter Graph $G=(V,E)$. Ein gültiges Matching ist dann eine Menge $M\subseteq E$ derart, dass für alle Knoten $v\in V$ gilt: $\operatorname {d} elta(v)\cap M\leq 1$. ($\operatorname {d} elta(v)$ notiert die Menge der zu $v$ inzidenten Kanten aus $E$) Ein gültiges Matching heißt …

maximal

falls es keine Kante $e\in E$ derart gibt, dass $a\cup M$ ein gültiges Matching ist. Maximale Matchings sind im Vergleich zu den folgenden Begriffen sehr einfach zu berechnen.

maximum

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

perfekt

falls für alle $v\in V$ gilt: $\operatorname {d} elta(v)\cap M=1$. 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 sprechen manche Personen auch von faktorisierbaren Graphen, wenn sie Graphen meinen, die einen 1-Faktor besitzen. Beide Sprechweisen sind etwa gleich weit verbreitet.

Für das gewichtete Matchingproblem spielt eine Kostenfunktion $c:E\to \mathbb {R}$ eine Rolle. Ein gültiges Matching heißt dann …

von maximalen Gewicht

falls $c(M):=\sum _{e\in M}c(e)$ maximal unter allen gültigen Matchings von $G$ ist.

minimal maximum

falls $c(M)$ minimal unter allen maximum Matchings ist.

Historisches

Sylvester gab für Aussage (2) ein Beispiel an, das zeigt, dass sie für Graphen mit drei oder mehr Brücken nicht mehr stimmt: Ein 3-regulärer Graph mit 16 Knoten, drei Brücken und keinem perfekten Matching.

Als eine der frühesten systematischen Untersuchungen von Matchings wird ein Artikel von Petersen angeführt, der 1891 über Die Theorie de reguldren Graphen schrieb. Er untersuchte ein Zerlegungsproblem aus der Algebra, das Hilbert 1889 gestellt hatte, indem er es als Graphenproblem formulierte. Letzlich bewies er darin folgendes:

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

Jeder $3$-reguläre, zusammenhängende Graph mit weniger als drei Brücken besitzt ein perfektes Matching. (2)

Die Tatsache (2) lässt sich auch als eine leichte Verallgemeinerung des Eulerkreisproblems formulieren.

Rückblickend erscheinen Pettersens 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 Graphenheorie 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 moderen Lehrbüchern und Vorlesungen tauchen Petersens ursprüngliche Resultate, wenn überhaupt, meist nur noch als Folgerungen aus den Resultaten von Tutte oder Hall auf.

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 fande 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 geannt. 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 $A$ die Inzidenzmatrix des Graphen $G$, dann lassen sich maximum Matchings als Lösungen von folgendem ganzzahligen linearen Programm auffassen:

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

Dabei ist $e$ der Vektor aus lauter Einsen. Das Programm des Knotenüberdeckungsproblems hat folgende Gestalt:

$\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 $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 $\{0,1\}$ 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 Knotenpartitionenen $S{\dot {\cup }}T$ und o.B.d.A $|S|\geq |T|$ hat genau dann ein perfektes Matching, wenn für jede Auswahl von Knoten $H\subseteq T$ gilt: $|N(H)|\geq |T|$. Dabei ist $N(H)$ die Nachbarschaftsmenge von $H$. (4)

Aus (4) folgt schnell, dass sich unter den bipartiten Grapgen genau alle regulären Graphen $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:

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

Lösungsverfahren

Algorithmus (I)

Eingabe $G$ mit einem beliebigen Matching $M$ 1. repeat 2. suche verbessenden Pfad $P$ 3. Falls gefunden: Augmentiere $M$ entlang $P$. 4. untill Suche nach verbesserndem Pfad war erfolglos Ausgabe $G$ mit maximum Matching $M$

Viele der folgenden Konzepte spielen in fast allen Lösungsverfahren von Matchingproblemen eine Rolle. Ist ein Graph $G$ mit einem Matching $M$ gegeben, dann heißt ein Knoten von $G$ frei (In der Literatur auch ungepaart, exponiert, verfügbar …) falls er zu keiner Kante in $M$ inzident ist. Andernfalls heißt der Knoten gesättigt. Ein Pfad $P$ in $G$ heißt alternierend, falls dieser abwechselnd Kanten aus $M$ und aus $M^{c}$ enthält. Falls diser Pfad in einem freien Knoten beginnt und endet, heißt der Pfad verbessernd oder auch augmentierend. Die letzte Bezeichnung kommt von der Tatsache, dass $P$ durch $M\oplus P$ ein größeres Matching als $M$ liefert. Folgendes grundlegendes Resultat von Bergeh 1957 motiviert das Studium von augmentierenden Pfaden.

Ein Matching ist genau dann maximum, wenn es keinen verbessernden Pfad in $G$ bezüglich $M$ gibt.

Diese Bezeichnungen entsprechen genau der Sprache, die auch bei der Behandlung von Flüssen in Netzwerken gebraucht wird. Das ist kein Zufall, denn Matchingprobleme lassen sich in der Sprache der Netzwerktheorie formulieren und mit den dort entwickelten Verfahren lösen. Im bipartiten Fall ist diese Zurückführung, wie das folgende Beispiel zeigt, sogar fast trivial.

• Beispiele
• Ein einfacher Graph mit einem maximalen Matching. Hier sind die Knoten mit den Labels $1$ und $5$ exponiert. Der Pfad $(1~3~2)$ ist ein alternierender Pfad und $(1~3~2~4~6~5)$ ist ein verbessernder Pfad.
  Ein einfacher Graph mit einem maximalen Matching. Hier sind die Knoten mit den Labels $1$ und $5$ exponiert. Der Pfad $(1~3~2)$ ist ein alternierender Pfad und $(1~3~2~4~6~5)$ ist ein verbessernder Pfad.
• Derselbe Graph, der entang $(1~3~2~4~6~5)$ verbessert wurde hat jetzt ein perfektes Matching.
  Derselbe Graph, der entang $(1~3~2~4~6~5)$ verbessert wurde hat jetzt ein perfektes Matching.
• 
  Reduktion vom bipartiten Matchingproblem auf Max-Flow. Gegeben ein Graph $G$ mit Knotenmenge $V(G)=S{\dot {\cup }}T$. Konstruiere ein Netzwerk $N=(G',u,\sigma ,\tau )$. Dabei ist $V(G')=V(G)\cup \{\sigma ,\tau \}$ und $E(G')=E(G)\cup \{(\sigma ,s):s\in S\}\cup \{(t,\tau ):t\in T\}$. Außerdem ist $u$ die Fortsetzung von der Kostenfunktion $c$, die alle neuen Kanten mit Inf belegt.

Mit dem Satz von Berge lässt sich auch gleich ein Algorithmus (I) zum Finden von maximum Matchings angeben. Weil jeder verbessernde Pfad ein zu einem gegebenen Matching einen weiteren Knoten matcht und maximal ${\frac {n}{2}}$ Knoten zu matchen sind, beschränkt sich die Zahl der Schleifendurchläufe asymptotisch durch ${\mathcal {O}}(n)$. Eine sehr Naïve Methode zum Finden verbessernder Pfade stellen sogenante Graph Scans dar, etwa eine Breitensuche (BFS) mit einer Laufzeit von ${\mathcal {O}}(n+m)$. Ferner ist $m\in {\mathcal {O}}(n^{2})$, weil der Graph bipartit ist und damit ist die angegebene Methode in ${\mathcal {O}}(n^{3})$

Einer der frühesten Beiträge zum berechnen von maximum Matchings, der über die oben angeführte naïve Methode hinausgeht, war der Algorithmus von Hopcroft und Karp 1973. Die Grundidee folgt dem Algorithmus von Dinic, der in jeder Phase, wo der Algorithmus nach einem verbessernden Pfad sucht, (Zeile 2) möglichst kurze Pfade und nach Möglichkeit „mehrere gleichzeitig“ sucht.

Alt, Blum, Mehlhorn & Paul 1991 schlagen eine Verbesserung von Hopcroft & Karp vor, indem sie ein Scanningverfahren für Adjazenzmatrizen nach Cheriyan, Hagerup, and Mehlhorn 1990 anwenden. Eine einfache Beschriebung der Methode findet sich auch in Burkard, Dell’Amico & Martello 47 ff. Feder und Motwani 1991 haben eine Methode vorgeschlagen, die auf der Zerlegung von $G$ in bipartite Cliquen beruht und erreichen damit eine asymptotische Laufzeit von ${\mathcal {O}}({\sqrt {n}}m\log(n^{2}/m)/\log n)$. Eine Methode die nicht auf der Idee augmentierender Pfade beruht, sondern sogenannte „starken Spannbäume“ benutzt, haben Balinski & Gonzalez 1991 vorgeschlagen und erreichen damit eine Laufzeit von ${\mathcal {O}}(n^{3})$,

Allgemeiner Fall

Während Charakterisierungen von Matchings und effiziente Algorithmen zum Bestimmen relativ schnell nach der Formulierung von Matchings als Problem gefunden wurden, dauerte es bis 1947 bis Tutte eine Charakterisierung für Matchings in allgemeinen Graphen formulieren und Beweisen konnte. Aus diesem tiefliegenden Resultat lassen sich alle bisher besrochenen vergleichsweise leicht herleiten. Tutte benutzt die einfache Tatsache, dass eine Komponente mit ungerader Knotenzahl in einem Graphen kein perfektes Matching haben kann. Wenn also eine Knotenmenge $S$ gefunden so gefunden werden kann, dass $G-S$ mehr ungerade Komponenten als $S$ Knoten hat, dann müsste für ein perfektes Matching aus jeder solcher Komponente wenigstens ein Knoten mit einem Knoten aus $S$ gematcht werden und das kann nicht sein. Es stellt sich heraus, dass die Existenz einer solchen Menge $S$ graphen ohne perfektes Matching nicht nur beschreibt, sondern charakterisiert:

Ein Graph $G$ hat genau dann ein perfektes Matching, wenn für jede Menge $T\subseteq V(G)$ gilt: $c(G-T)\leq T$. ($c$ gibt die Anzahl der ungeraden Komponenten eines Graphen an.) (5)

Eine solche Menge $T$ heißt Tutte-Menge und die Bedingung in (5) heißt Tutte-Bedingung. Dass sie notwendig für die Existenz perfekter Matching ist, wurde schon skizziert und es gibt mitlerweile viele Beweise dafür, dass die Bedingung hinreichend ist: Tuttes ursprünglicher Beweis formulierte das Problem als ein Matrix-Problem und benutzte die Idee der Pfaffschen Determinante. Elementare Abzählargumente wurden relativ rasch danach veröffentlicht, wie in Maunsell 1952, Tutte 1952, Gallai 1963, Halton 1966 oder Balinski 1970. Andere Beweise, wie Gallai 1963, Anderson 1971 oder Marder 1973 verallgemeinern den Satz (4) von Hall systematisch. Ferner gibt es Beweise aus der Perspektive der Graphentheorie, die die Struktur von Graphen betrachten, die selbst kein Perfektes Matching besitzen, doch falls eine Kante ergänzt wird hat der resultierende Graph ein solches. Diesen Ansatz verfolgen etwa Hetyei 1972 oder Lovász 1975.

Es genügt nicht, erst alle Blüten zu suchen und zu kontrahieren und dann eine Breitensuche zu fahren. Die Priorität der Fallunterscheidungen spielt eine Rolle für die Korrektheit des Algorithmus'. In diesem Beispiel enthält der kontrahierte Graph keinen augmentierenden Pfad, wohl aber der Ausgangsgraph.

Algorithmus von Edmonds

Der erste Polynomialzeitalgorithmus für das klassische Matchingproblem stammt von Edmonds 1965. Die Grundstruktur der Methode entspricht Algorithmus (I): Sie sucht verbessernde Pfade und gibt ein maximum Matching zurück, falls kein solcher gefunden werden kann. Einen verbessernden Pfad zu finden, stellt sich hier aber als ein schwieriger heraus als im bipartiten Fall, weil einige neue Fälle auftreten können. Edmonds Suchmethode konstruiert nach und nach einen alternierenden Wald; Das ist ein kreisfreier Graph $F$ mit so vielen Zusammenhangskomponenten, wie es freie Knoten gibt. Jeder freie Knoten ist Wurzel $r_{i}$ eines Baumes $T\subset F$ und $F$ ist so kostruiert, dass für alle anderen Knoten $v\in F$ der eindeutig bestimmte $r_{i}$-$v$-Pfad ein alternierender Pfad ist. Ein Knoten in $v\in F$ heißt dann innen oder gerade, falls $\operatorname {d} (r_{i},v)\equiv 1\mod 2$ und andernfalls außen oder ungerade. ($\operatorname {d}$ sei hier die Distanzfunktion in $T$; gebe also die Länge des eindeutig bestimmten $r_{i}$-$v$-Pfades an)

Es genügt die Betrachtung auf die Konstruktion eines alternierenden Baumes zu reduzieren. Falls diese Konstruktion keinen augmentierenden Pfad findet, wird sie mit einem neuen freien Knoten reinitialisiert und alle bereits betrachteten Kanten werden Ignoriert. Falls kein freier Knoten mehr existiert, dann existiert auch kein augmentierender Pfad. Diesen alternierenden Baum konstruiert Edmonds, idnem er ausgehend von einem freien Knoten nach und nach alle Kanten hinzufügt oder ignoriert. Dabei können für eine neue Kante $e=uv$ ($u$ gehöre bereits zum Baum) folgende Fälle auftreten:

1. Wenn $u$ ein innerer Knoten ist, können nur Kanten $e\in M$ zu $T$ hinzugefügt werden, weil $T$ alternierend werden soll. Diese Kante ist eindeutig durch $(u~\operatorname {match} (u))$ gegeben.
2. Falls $u$ ein äußerer Knoten ist, dann kann $v$ …
   1. frei sein und noch nicht in $T$. Dann ist der $r$-$v$ Pfad augmentierend.
   2. gepaart sein und weder $v$ noch $\operatorname {match} (v)$ ist in $T$. Dann können $v$ und $\operatorname {match} (v)$ zu $T$ hinzugefügt werden.
   3. bereits in $T$ als äußerer Knoten enthalten sein. Damit schließt als $e$ einen geraden Kreis. Diese Kanten können ignoriert werden.
   4. bereits in $T$ als ein innerer Knoten enthalten sein. Dann schließt $e$ einen ungeraden alternienden Kreis $B$; eine sogenannte Blüte. Edmonds zieht die Knoten in $B$ zu einem Pseudoknoten $b$ zusammen mit den Inzidenzen aller Knoten aus $B$. (Diese Operation lässt sich auch beschreiben als „Bildung des Quotientengraphen” $G'=G/B$) Er reinitialisiert dann die Suche in $G'$ und gibt ein Verfahren an, einen dort gefundenen augmentierenden Pfad $P'$ zu einem augmentierenden Pfad $P$ in $G$ zu liften.

Blüten könen, anders als Fall $3$ weder nicht werden. Der Knoten der die Blüte mit dem Baum verbindet lässt sich in das Schema der inneren und äußeren Knoten nicht einordnen. Die naheliegende Idee, ihn als „sowohl innen als auch außen“ zu behandeln führt zu einem falschen Algorithmus. Die Behandlung von Blüten mit Kontraktion ist neben dem Ansatz von Berge die zentrale Idee von Edmonds' Algorithmus und Grundlage vieler späterer Verfahren. Bipartite Graphen enthalten keine ungeraden Kreise und damit auch keine Blüten. Edmonds' Algorithmus reduziert sich daher im bipartiten Fall auf die Methode von Munkres.

Man kenn ablesen, dass die skizzierte Methode von Edmonds einen Aufwand von ${\mathcal {O}}(n^{4})$ hat. In Fall $2.4$ reinitialisiert Edmods die Suche und verwirft damit den bereits geleisteten Suchaufwand. Gabow 1976 und Lawler haben eine naïve Implementierung vorgeschlagen, die den Suchaufwand nicht verwirft und eine Laufzeit von ${\mathcal {O}}(n^{3})$ erreicht. Das Beispiel folgt bereits dieser Methode.

• Beispiel zu Edmonds
• Sei folgender Graph $G$ mit freien Knoten $1$ und $9$ gegeben.
  Sei folgender Graph $G$ mit freien Knoten $1$ und $9$ gegeben.
• Der Algorithmus startet beim freien Knoten $1$ und mit dem alternierenden Baum, der nur diesen Knoten enthält.
  Der Algorithmus startet beim freien Knoten $1$ und mit dem alternierenden Baum, der nur diesen Knoten enthält.
• $G$ bleibt unverändert.
  $G$ bleibt unverändert.
• Betrachte Kante $(1~2)$. $1$ ist ein innerer Knoten und weder $2$ noch $3$ liegen in $T$ und werden nach Fall $2.2$ hinzugefügt.
  Betrachte Kante $(1~2)$. $1$ ist ein innerer Knoten und weder $2$ noch $3$ liegen in $T$ und werden nach Fall $2.2$ hinzugefügt.
• $G$ bleibt unverändert.
  $G$ bleibt unverändert.
• $5$ und $6$ sowie $4$ und $14$ werden wie eben nach Fall $2.2$ hinzugefügt. $(4~6)$ schließt einen geraden Kreis und wird nach $2.3$ ignoriert. Die Kante $(4~5)$ kann nach Fall $1.1$ ignoriert werden.
  $5$ und $6$ sowie $4$ und $14$ werden wie eben nach Fall $2.2$ hinzugefügt. $(4~6)$ schließt einen geraden Kreis und wird nach $2.3$ ignoriert. Die Kante $(4~5)$ kann nach Fall $1.1$ ignoriert werden.
• $G$ bleibt unverändert.
  $G$ bleibt unverändert.
• Erneut werden nach Fall $2.2$ die Paare $13~12$, $10~11$ und $7~6$ hinzugefügt.
  Erneut werden nach Fall $2.2$ die Paare $13~12$, $10~11$ und $7~6$ hinzugefügt.
• $G$ zieht eine Blüte zusammen.
  $G$ zieht eine Blüte zusammen.
• $13~10$ wird nach Fall $1.1$ ignoriert und $12~10$ nach Fall $2.3$. $12~11$ schließt eine Blüte $B$.
  $13~10$ wird nach Fall $1.1$ ignoriert und $12~10$ nach Fall $2.3$. $12~11$ schließt eine Blüte $B$.
• 
  Der reduzierte Graph $G'=G/B$.
• $b~7$ wird nach $2.3$ ignoriert.
  $b~7$ wird nach $2.3$ ignoriert.
• 
  $G'$ mit einer weiteren Blüte $B'$.
• $b~8$ schließt wieder eine Blüte $B'$. Blüten können auch Pseudoknoten enthalten.
  $b~8$ schließt wieder eine Blüte $B'$. Blüten können auch Pseudoknoten enthalten.
• 
  Der weiter reduzierte Graph $G''=G'/B'$
• 
  Von $b'$ wird der freie Knoten $9$ gefunden, der nach Fall $2.1$ in $G''$ den augmentierenden Pfad $P''=(1~2~b'~9)$ schließt. Die Liftung dieses Pfades liefert $P=(1~2~3~5~6~7~8~9)$ zunächst in $G'$, der aber auch schon in $G$ selbst liegt.

Literatur

• L. Lovász, M. D Plummer: Matching Theory (= Annals of Discrete Mathemetics). 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. 
• Qinglin Roger Yu, Guizhen Liu: Graph Factors and Matching Extensions. 1. Auflage. Springer, Beijing 2009, ISBN 3-540-93951-2. 
• Alexander Schrijver: Combinatorial Optimization – Polyherda and Efficiency (= Algorithms and Combinatorics. A). Springer, Amsterdam 2003, ISBN 3-540-44389-4. 
• Adrian Bondy, U.S.R. Murty: Graph Theory (= Graduate Texts in Mathematics). Springer, 2008, ISBN 1-84996-690-7 (springer.com). 
• Rainer Burkard, Mauro Dell'Amico, Silvano Martello: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia 2009, ISBN 978-0-89871-663-4 (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. 
• Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson: Graph Theory 1736-1936. Oxford University Press, USA, 1999, ISBN 0-19-853916-9. 

Einzelnachweise

Ankermungen