Wikipedia - Benutzerbeiträge [de]

Matching (Graphentheorie)

2017-01-19T13:21:40Z

Flowi: Algo von Dinic hat dieselbe Laufzeit wie Hopcroft-Karp auf Flussnetzwerken, wie sie beim bip. Matching auftreten (Quelle: Even&Tarjan, auch hinzugefügt)

{{Weiterleitungshinweis|Perfekte Paarung|für den Begriff der nicht-ausgearteten Bilinearform aus der linearen Algebra siehe [[ausgeartete Bilinearform]].}}
Die Theorie um das Finden von '''Matchings''' in Graphen ist in der [[Diskrete Mathematik|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 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:
# Wie findet man ein Matching, das eine maximale Anzahl<ref group="A">Beachte den Unterschied zwischen einem [[Maximales Element|maximalen Element]] und einem [[größtes Element|Maximum]]. Bei der [[#Formalisierung|Formalisierung]] wird darauf genauer eingegangen.</ref> an Dingen einander zuordnet? Dieses Problem ist das ''klassische Matchingproblem.''
# 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 <math>G</math> wird meistens mit <math>\Phi(G)</math> notiert.
# 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 (Zahl)|Vorzeichen]] vertauscht, kann man beide Probleme ohne nennenswerten Aufwand ineinander überführen.
# 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 ''[[Bipartiter Graph|bipartites]] (gewichtetes) Matchingproblem'' und ist ein viel diskutierter Spezialfall.
# 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 „Schwierigkeit“ mit den Methoden der [[Komplexitätstheorie]] und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her.

== Definitionen ==
<gallery class="float-right">
maximal-simple.svg|Ein einfacher Graph mit einem nicht erweiterbaren Matching (maximal matching)
perfect-simple.svg|Derselbe Graph mit einem perfekten (wie auch größtmöglichen) Matching
</gallery>
Das oben beschriebene Problem lässt sich wie folgt formalisieren. Gegeben sei ein endlicher, ungerichteter Graph <math>G=(V,E)</math>. Eine Menge <math>M\subseteq E</math> heißt (gültiges) Matching wenn keine zwei Kanten aus <math>M</math> einen Knoten gemeinsam haben. Ein Matching heißt
; nicht erweiterbar (engl. maximal matching): falls es keine Kante <math>e\in E\setminus M</math> derart gibt, dass <math>\{e\}\cup M</math> ein gültiges Matching ist. Maximale Matchings sind im Vergleich zu den folgenden Begriffen sehr einfach zu berechnen.
; größtmöglich (engl. maximum matching): falls <math>M</math> als Menge eine maximale Kardinalität unter allen gültigen Matchings von <math>G</math> hat. Maximum-Matchings sind maximal. Die Mächtigkeit eines Maximum-Matchings wird ''Matchingzahl'' genannt und mit <math>\nu(G)</math> notiert.
; perfekt: falls <math>2 \cdot | M | = | V |</math> gilt. Perfekte Matchings sind Maximum-Matchings (und damit auch maximal). Perfekte Matchings können als ''[[Graph Faktor|1-Faktoren]]'' eines Graphen, das heißt [[Regulärer Graph|1-reguläre]] aufspannende Teilgraphen, aufgefasst werden. Dieser Auffassung folgend spricht man auch von ''faktorisierbaren Graphen,'' wenn sie einen 1-Faktor besitzen. Beide Sprechweisen sind etwa gleich weit verbreitet.<ref>[[#Yu & Liu|Yu & Liu]] ''4.''</ref>

Für das gewichtete Matchingproblem spielt eine Kostenfunktion <math>c: E\to \mathbb{R}</math> eine Rolle. Ein gültiges Matching heißt dann …
; von maximalem Gewicht: falls <math>c(M) := \sum_{e\in M} c(e)</math> maximal unter allen gültigen Matchings von <math>G</math> ist.
; minimal maximal: falls <math>c(M)</math> minimal unter allen maximalen Matchings ist.

== Historisches ==
[[Datei:Sylvester counter.svg|mini|[[James Joseph Sylvester|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<ref name="ReferenceA">[[#Lovász & Plummer|Lovász & Plummer]] ''xi.''</ref><ref>[[#Yu & Liu|Yu & Liu]] ''3.''</ref> systematischen Untersuchungen von Matchings wird ein Artikel von [[Julius Peter Christian Petersen|Julius Petersen]] angeführt, der 1891 über „Die Theorie der regulären graphs“ schrieb.<ref>{{Cite journal
| volume = 15
| pages = 193–220
| last = Petersen
| first = Julius
| title = Die Theorie der regulären graphs
| journal = [[Acta Mathematica]]
| date = 1891
| doi = 10.1007/BF02392606
}}</ref> Er untersuchte ein Zerlegungsproblem aus der Algebra, das [[David Hilbert]] 1889<ref>{{Cite journal
| volume = 33
| issue = 2
| pages = 223–226
| last = Hilbert
| first = David
| authorlink = David Hilbert
| title = Über die Endlichkeit des Invariantensystems für binäre Grundformen
| journal = Mathematische Annalen
| date = 1889
}}</ref> gestellt hatte, indem er es als Graphenproblem formulierte.<ref name="ReferenceA" /> Letztlich bewies er darin folgendes:
: Für alle Zahlen <math>k\in \mathbb{N}</math> kann jeder <math>2k</math>-reguläre Graph in disjunkte <math>2</math>-Faktoren zerlegt werden. (1)
: Jeder [[Kubischer Graph|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 [[Eulerkreisproblem]]s formulieren.<ref group="A">Es ist nicht bekannt, ob Petersen mit den Arbeiten von [[Leonhard Euler|Euler]] 1736 zu diesem Problem vertraut war ([[#Lovász & Plummer|Lovász & Plummer]] ''xi'').</ref>

Rückblickend erscheinen Petersens Argumente, mit denen er das Obige bewies, kompliziert und umständlich.<ref name="Diestel-43">{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| pages = 43
| url = http://diestel-graph-theory.com/german/index.html
}}
</ref> Bei der weiteren Untersuchung etwa durch [[Henry Roy Brahana|Brahana]] 1917<ref>{{Cite journal
| doi = 10.2307/1967667
| issn = 0003-486X
| volume = 19
| issue = 1
| pages = 59–63
| last = Brahana
| first = Henry Roy
| title = A Proof of Petersen’s Theorem
| journal = The Annals of Mathematics
| date = 1917
}}</ref>, [[Alfred Errera|Errera]] 1922<ref>{{Cite journal
| volume = 36
| pages = 56–61
| last = Errera
| first = Alfred
| title = Une demonstration du théorème de Petersen
| journal = Mathesis
| date = 1922
}}</ref> und [[Orrin Frink|Frink]] 1926<ref>{{Cite journal
| doi = 10.2307/1967699
| issn = 0003-486X
| volume = 27
| issue = 4
| pages = 491–493
| last = Frink
| first = Orrin
| title = A Proof of Petersen’s Theorem
| journal = The Annals of Mathematics
| date = 1926
}}</ref> sowie zusammenfassend durch [[Dénes Kőnig|Kőnig]] 1936<ref>{{Cite book
| last = Kőnig
| first = Dénes
| title = Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
| date = 1936
}}</ref> wurden aber viele Methoden der modernen Graphentheorie entwickelt oder zuerst systematisch formuliert. Petersens Denkansatz wurde dann von [[Fridolin Bäbler|Bäbler]] 1938<ref>{{Cite journal
| doi = 10.1007/BF01214296
| issn = 0010-2571
| volume = 10
| issue = 1
| pages = 275–287
| last = Bäbler
| first = Fridolin
| title = Über die Zerlegung regulärer Streckenkomplexe ungerader Ordnung
| journal = Commentarii Mathematici Helvetici
| date = 1938
}}</ref> 1952<ref>{{Cite journal
| issn = 0010-2571
| volume = 26
| pages = 117–118
| last = Bäbler
| first = Fridolin
| title = Bemerkungen zu einer Arbeit von Herrn R. Cantoni.
| journal = Commentarii Mathematici Helvetici
| date = 1952
| url = http://www.digizeitschriften.de/dms/img/?PPN=GDZPPN002055910
}}</ref> und 1954<ref>{{Cite journal
| doi = 10.1007/BF02566927
| issn = 0010-2571
| volume = 28
| issue = 1
| pages = 155–161
| last = Bäbler
| first = Fridolin
| title = Über den Zerlegungssatz von Petersen
| journal = Commentarii Mathematici Helvetici
| date = 1954
}}</ref> sowie von [[Tibor Gallai|Gallai]] 1950<ref>{{Cite journal
| issn = 0236-5294
| volume = 1
| pages = 133–153
| last = Gallai
| first = Tibor
| title = On factorization of graphs
| journal = Acta Mathematica Academiae Scientiarum Hungaricae
| date = 1950
}}</ref>, [[Hans-Boris Belck|Belck]] 1950<ref>{{Cite journal
| doi = 10.1515/crll.1950.188.228
| issn = 0075-4102
| volume = 1950
| issue = 188
| pages = 228–252
| last = Belck
| first = Hans-Boris
| title = Reguläre Faktoren von Graphen.
| journal = Journal für die reine und angewandte Mathematik (Crelles Journal)
| date = 1950
}}</ref> 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.<ref name="Diestel-43" /> Die zweite Aussage wird auf den Satz von Tutte zurückgeführt.<ref>{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| pages = 45
| url = http://diestel-graph-theory.com/german/index.html
}}</ref>

== Bipartite Matchings ==
Eines dieser frühen Resultate betrifft [[Bipartiter Graph|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. [[Ron Aharoni|Aharoni]] bewies 1984 die Aussage für [[überabzählbar]] unendliche Graphen.<ref>{{Cite journal
| doi = 10.1112/jlms/s2-29.1.1
| issn = 0024-6107
| volume = s2-29
| issue = 1
| pages = 1–12
| last = Aharoni
| first = Ron
| title = Kőnig’s Duality Theorem for Infinite Bipartite Graphs
| journal = Journal of the London Mathematical Society
| date = 1984
}}</ref> Ein elementarer Beweis von (3) findet sich in [[#Lovász & Plummer|Lovász & Plummer]] ''43,'' der von den meisten Lehrbüchern übernommen wurde. [[#Bondy & Murty|Bondy & Murty]] ''200'' führt den Satz auf ein Resultat der [[Lineares Programm|linearen Programmierung]] zurück: Ist <math>A</math> die [[Inzidenzmatrix]] des Graphen <math>G</math>, dann lassen sich maximum Matchings als Lösungen von folgendem ganzzahligen linearen Programm auffassen:
:<math>\max ex \text{ unter } Ax\le 1 \land x\ge 0</math>
Dabei ist <math>e</math> der [[Einsvektor]] bestehend aus lauter Einsen. Das Programm des Knotenüberdeckungsproblems hat folgende Gestalt:
:<math>\min ye \text{ unter } yA\ge 1 \land y\ge 0</math>
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 <math>A</math> [[Total unimodulare Matrix|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 <math>\mathbb{Z}</math> (und damit in diesem speziellen Fall sogar aus <math>\left\{0, 1\right\}</math>) 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.<ref>[[#Lovász & Plummer|Lovász & Plummer]] ''5-40.''</ref><ref>Notizen zu einem Vortrag von Robert D. Borgersen: ''[http://www.robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics.]'' (PDF; 66 kB). November 26, 2004.</ref><ref>{{Cite journal
| pages = 103–141
| last = Jacobs
| first = K.
| title = Der Heiratssatz
| journal = Selecta Mathematica I
| date = 1969
}}</ref> 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 [[Philip Hall|Hall]] 1935<ref>{{Cite journal
| volume = 10
| pages = 26–30
| last = Hall
| first = Philip
| title = On representatives of subsets
| journal = Journal of London Mathematics Society
| date = 1935
}}</ref> angab, um bipartite Graphen mit perfektem Matching zu charakterisieren. Dieser Charakterisierungssatz ist ebenfalls äquivalent zum Satz von Kőnig.
: Ein bipartiter Graph mit Knotenpartitionen <math>S\dot{\cup} T</math> und [[Ohne Beschränkung der Allgemeinheit|o.B.d.A]] <math>|S|\ge |T|</math> hat [[Bikonditional|genau dann]] ein perfektes Matching, wenn für jede Auswahl von Knoten <math>H\subseteq S</math> gilt: <math>|N(H)|\ge |H|</math>. Dabei ist <math>N(H)</math> die [[Nachbarschaftsmenge]] von <math>H</math>. (4)
Aus (4) folgt schnell, dass sich unter den bipartiten Graphen genau alle regulären Graphen <math>1</math>-faktorisieren lassen<ref>[[#Jungnickel|Jungnickel]] ''216.''</ref> und die Aussage (1) von Petersen lässt elegant auf diese Folgerung zurückführen.<ref name="Diestel-43" /> Eine Verallgemeinerung dieses Resultats liefert eine Formel für die Größe eines maximum Matchings, die sogenannte ''Kőnig-Ore'' Formel:<ref>[[#Yu & Liu|Yu & Liu]] ''9.''</ref><ref>[[#Bondy & Murty|Bondy & Murty]] ''422.''</ref>
:<math>\nu(G)= |S| - \max_{H\subseteq S}\{|H|-|N(H)|\}</math>

=== Lösungsverfahren ===
{| class="float-right" style="width:30%" |
|+'''Algorithmus (I)''' 
|
'''Eingabe''' <math>G</math> mit einem beliebigen Matching <math>M</math>
1. '''repeat'''
2. suche verbessernden Pfad <math>P</math>
3. Falls gefunden: Augmentiere <math>M</math> entlang <math>P</math>.
4. '''until''' Suche nach verbesserndem Pfad war erfolglos
'''Ausgabe''' <math>G</math> mit maximum Matching <math>M</math>
|}
Viele der folgenden Konzepte spielen in fast allen Lösungsverfahren von Matchingproblemen eine Rolle. Ist ein Graph <math>G</math> mit einem Matching <math>M</math> gegeben, dann heißt ein Knoten von <math>G</math> ''frei'' (in der Literatur auch ''ungepaart, exponiert, verfügbar'' …) falls er zu keiner Kante in <math>M</math> inzident ist. Andernfalls heißt der Knoten ''gesättigt.'' Ein Pfad <math>P</math> in <math>G</math> heißt ''alternierend,'' falls dieser abwechselnd Kanten aus <math>M</math> und aus <math>M^c</math> enthält. Falls dieser Pfad in einem freien Knoten beginnt und endet, heißt der Pfad ''verbessernd'' oder auch ''augmentierend.'' Die letzte Bezeichnung kommt von der Tatsache, dass <math>P</math> durch <math>M\oplus P</math><ref group="A"><math>\oplus</math> notiert die [[symmetrische Differenz]].</ref> ein größeres Matching als <math>M</math> liefert. Folgendes grundlegendes Resultat von [[Claude Berge|Berge]] 1957<ref>{{Cite journal
| volume = 43
| issue = 9
| pages = 842–844
| last = Berge
| first = Claude
| title = Two theorems in graph theory
| journal = Proceedings of the National Academy of Sciences of the United States of America
| date = 1957-09-15
| url = http://www.pnas.org/content/43/9/842.full.pdf
}}</ref> motiviert das Studium von augmentierenden Pfaden.
: Ein Matching ist genau dann Maximum, wenn es keinen verbessernden Pfad in <math>G</math> bezüglich <math>M</math> gibt.
Diese Bezeichnungen entsprechen genau der Sprache, die auch bei der Behandlung von [[Flüsse und Schnitte in Netzwerken|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.
Gegeben ein Graph <math>G</math> mit Knotenmenge <math>V(G)=S\dot{\cup}T</math>. Konstruiere ein [[Flüsse und Schnitte in Netzwerken#Netzwerk|Netzwerk]] <math>N=(G',u,\sigma,\tau)</math>. Dabei ist <math>V(G')=V(G) \cup \{\sigma,\tau \}</math> und <math>E(G')= E(G)\cup\{(\sigma,s) : s\in S\} \cup \{(t,\tau): t\in T\} </math>. Außerdem ist <math>u</math> die Fortsetzung von der Kostenfunktion <math>c</math>, die alle neuen Kanten mit <code>Inf</code><ref group="A">Programmiersprachen, die das Konzept <code>Inf</code> nicht unterstützen, können die künstlichen Kanten stattdessen mit einer absurd großen Zahl belegen. <math>\textstyle \sum_{e\in E(G)} c(e)</math> genügt in jedem Fall.</ref> belegt.

Mit dem Satz von Berge lässt sich auch gleich ein Algorithmus (I) zum Finden von maximum Matchings angeben.<ref>Aus didaktischen Gründen sehr stark vereinfacht nach [[#Burkard, Dell’Amico & Martello|Burkard, Dell’Amico & Martello]] ''38.'' In der Referenz ist die Methode zum Finden eines verbessernden Pfades wesentlich detaillierter angegeben.</ref> Weil jeder verbessernde Pfad zu einem gegebenen Matching einen weiteren Knoten matcht und maximal <math>\tfrac{n}{2}</math> Knoten zu matchen sind, beschränkt sich die Zahl der Schleifendurchläufe [[Asymptotische Laufzeit|asymptotisch]] durch <math>\mathcal{O}(n)</math>. Eine sehr naive Methode zum Finden verbessernder Pfade stellen sogenannte [[Suchverfahren in Graphen|Graph Scans]] dar, etwa eine Breitensuche (BFS) mit einer Laufzeit von <math>\mathcal{O}(n+m)</math>. Ferner ist <math>m\in \mathcal{O}(n^2)</math>, weil der Graph bipartit ist und damit ist die angegebene Methode in <math>\mathcal{O}(n^3)</math>.

Einer der frühesten Beiträge zum Berechnen von Maximum-Matchings, der über die oben angeführte naive Methode hinausgeht, war der [[Algorithmus von Hopcroft und Karp]] 1973.<ref>{{Cite journal
| doi = 10.1137/0202019
| issn = 0097-5397
| volume = 2
| issue = 4
| pages = 225–231
| last = Hopcroft
| first = John E.
| coauthors = Richard M. Karp
| title = An <math>n^{5/2}</math> Algorithm for Maximum Matchings in Bipartite Graphs
| journal = SIAM Journal on Computing
| date = 1973
}}</ref> Die Grundidee folgt dem [[Algorithmus von Dinic]] (mit dem das Problem mit derselben asymptotischen Laufzeit gelöst werden kann <ref>{{Cite journal
| doi = 10.1137/0204043
| issn = 0097-5397
| volume = 4
| issue = 4
| pages = 507–518
| last = Even
| first = Shimon
| coauthors = Robert E. Tarjan
| title = Network flow and testing graph connectivity
| journal = SIAM Journal on Computing
| date = 1975
}}</ref>), 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<ref>{{Cite journal
| doi = 10.1016/0020-0190(91)90195-N
| issn = 0020-0190
| volume = 37
| issue = 4
| pages = 237–240
| last = Alt
| first = H.
| coauthors = N. Blum, K. Mehlhorn, M. Paul
| title = Computing a maximum cardinality matching in a bipartite graph in time <math>\mathcal{O}(n^{1.5}\sqrt{m/\log n})</math>
| journal = Information Processing Letters
| date = 1991
}}</ref> schlagen eine Verbesserung von Hopcroft & Karp vor, indem sie ein Scanningverfahren für [[Adjazenzmatrizen]] nach Cheriyan, Hagerup, and Mehlhorn 1990<ref>{{Cite book
| publisher = Springer-Verlag
| isbn = 3-540-52826-1
| volume = 443
| pages = 235–248
| last = Cheriyan
| first = Joseph
| coauthors = Torben Hagerup, Kurt Mehlhorn
| title = Automata, Languages and Programming
| chapter = Can a maximum flow be computed in <math>\mathcal{O}(nm)</math> time?
| location = Berlin/Heidelberg
| date = 1990
}}</ref> anwenden. Eine einfache Beschreibung der Methode findet sich auch in [[#Burkard, Dell’Amico & Martello|Burkard, Dell’Amico & Martello]] ''47 ff.'' Feder und Motwani 1991<ref>{{Cite conference
| publisher = ACM
| doi = 10.1145/103418.103424
| isbn = 0-89791-397-3
| pages = 123–133
| last = Feder
| first = Tomás
| coauthors = Rajeev Motwani
| title = Clique partitions, graph compression and speeding-up algorithms
| booktitle = Proceedings of the twenty-third annual ACM symposium on Theory of computing
| location = New York
| date = 1991
}}</ref> haben eine Methode vorgeschlagen, die auf der Zerlegung von <math>G</math> in bipartite [[Clique (Graphentheorie)|Cliquen]] beruht und erreichen damit eine asymptotische Laufzeit von <math>\mathcal{O}( \sqrt{n} m \log(n^2 /m)/ \log n)</math>. Eine Methode, die ''nicht'' auf der Idee augmentierender Pfade beruht, sondern sogenannte „starke [[Spannbaum|Spannbäume]]“ benutzt, haben Balinski & Gonzalez 1991<ref>{{Cite journal
| doi = 10.1002/net.3230210203
| issn = 1097-0037
| volume = 21
| issue = 2
| pages = 165–179
| last = Balinski
| first = M. L
| coauthors = J. Gonzalez
| title = Maximum matchings in bipartite graphs via strong spanning trees
| journal = Networks
| date = 1991
}}</ref> vorgeschlagen und erreichen damit eine Laufzeit von <math>\mathcal{O}(n^3)</math>.

== Allgemeiner Fall ==
=== Satz von Tutte ===
{{Hauptartikel|Satz von Tutte}}

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<ref name="tutte">{{Cite journal
| volume = 1
| issue = 2
| pages = 107
| last = Tutte
| first = W. T
| title = The factorization of linear graphs
| journal = Journal of the London Mathematical Society
| date = 1947
}}</ref> eine Charakterisierung für perfekte Matchings in allgemeinen Graphen formulieren und beweisen konnte. Aus diesem tiefliegenden Resultat lassen sich alle bisher besprochenen vergleichsweise leicht herleiten.<ref>[[#Lovász & Plummer|Lovász & Plummer]] ''84.''</ref> Tutte benutzt die einfache Tatsache, dass eine Komponente mit ungerader Knotenzahl in einem Graphen kein perfektes Matching haben kann. Wenn also eine Knotenmenge <math>S</math> so gefunden werden kann, dass <math>G-S</math> mehr ungerade Komponenten als <math>S</math> Knoten hat, dann müsste für ein perfektes Matching aus jeder solcher Komponente wenigstens ein Knoten mit einem Knoten aus <math>S</math> gematcht werden und das kann nicht sein. Es stellt sich heraus, dass die Existenz einer solchen Menge <math>S</math> Graphen ohne perfektes Matching nicht nur beschreibt, sondern charakterisiert:

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

Eine solche Menge <math>T</math> heißt ''Tutte-Menge'' und die Bedingung in (5) heißt ''Tutte-Bedingung.'' Dass sie [[Notwendige Bedingung|notwendig]] für die Existenz perfekter Matching ist, wurde schon skizziert und es gibt mittlerweile 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 [[Pfaffsche Determinante|pfaffschen Determinante]].<ref name="tutte" /> [[Elementare Mathematik|Elementare]] Abzählargumente wurden relativ rasch danach veröffentlicht, wie in Maunsell 1952,<ref>{{Cite journal
| volume = 1
| issue = 1
| pages = 127
| last = Maunsell
| first = F. G.
| title = A note on Tutte’s paper “The factorization of linear graphs”
| journal = Journal of the London Mathematical Society
| date = 1952
}}</ref> Tutte 1952,<ref>{{Cite journal
| pages = 164–178
| first = W. T.
| last = Tutte
| title = The factors of graphs
| journal = Classic Papers in Combinatorics
| date = 1987
}}</ref> Gallai 1963,<ref name="gallai">{{Cite journal
| volume = 8
| pages = 135–139
| last = Gallai
| first = T.
| title = Neuer Beweis eines Tutte’schen Satzes, Magyar Tud
| journal = Akad. Kutató Int. Közl
| date = 1963
}}</ref> Halton 1966<ref>{{Cite journal
| doi = 10.1017/S0305004100040342
| volume = 62
| issue = 04
| pages = 683–684
| last = Halton
| first = John H.
| title = A Combinatorial Proof of a Theorem of Tutte
| journal = Mathematical Proceedings of the Cambridge Philosophical Society
| date = 1966
}}</ref> oder Balinski 1970.<ref>{{Cite journal
| volume = 12
| pages = 570–572
| last = Balinski
| first = M. L.
| title = On perfect matchings
| journal = SIAM Review
| date = 1970
}}</ref> Andere Beweise, wie Gallai 1963,<ref name="gallai" /> Anderson 1971<ref>{{Cite journal
| volume = 10
| issue = 3
| pages = 183–186
| last = Anderson
| first = I.
| title = Perfect matchings of a graph
| journal = Journal of Combinatorial Theory, Series B
| date = 1971
}}</ref> oder Marder 1973<ref>{{Cite journal
| doi = 10.1007/BF01428195
| issn = 0025-5831
| volume = 201
| issue = 4
| pages = 269–282
| last = Mader
| first = W.
| title = 1-Faktoren von Graphen
| journal = Mathematische Annalen
| date = 1973-12
}}</ref> 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<ref>{{Cite journal
| volume = 16
| pages = 3–6
| last = Hetyei
| first = G.
| title = A new proof of a factorization theorem
| journal = Acta Acad. Paedagog. Civitate Pécs Ser. 6 Math. Phys. Chem. Tech
| date = 1972
}}</ref> oder Lovász 1975.<ref>{{Cite journal
| volume = 19
| issue = 3
| pages = 269–271
| last = Lovasz
| first = L.
| title = Three short proofs in graph theory
| journal = Journal of Combinatorial Theory, Series B
| date = 1975
}}</ref>
[[Datei:Blossom Counter.svg|mini|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.<ref>[[#Jungnickel|Jungnickel]] ''409.''</ref> In diesem Beispiel enthält der kontrahierte Graph keinen augmentierenden Pfad, wohl aber der Ausgangsgraph.]]

=== Algorithmus von Edmonds ===
Der erste [[Polynomialzeit]]algorithmus für das klassische Matchingproblem stammt von [[Jack Edmonds]] (1965).<ref>{{Cite journal
| doi = 10.4153/CJM-1965-045-4
| volume = 17
| issue = 3
| pages = 449–467
| last = Edmonds
| first = J.
| title = Paths, trees, and flowers
| journal = Canadian Journal of mathematics
| date = 1965
}}</ref> 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 schwieriger heraus als im bipartiten Fall, weil einige neue Fälle auftreten können. Edmonds Suchmethode konstruiert nach und nach einen ''alternierenden [[Wald (Graphentheorie)|Wald]].'' Das ist ein kreisfreier Graph <math>F</math> mit so vielen Zusammenhangskomponenten wie es freie Knoten gibt. Jeder freie Knoten ist [[Wurzel (Graphentheorie)|Wurzel]] <math>r_i</math> eines [[Baum (Graphentheorie)|Baumes]] <math>T\subset F</math> und <math>F</math> ist so konstruiert, dass für alle anderen Knoten <math>v\in F</math> der eindeutig bestimmte <math>r_i</math>-<math>v</math>-Pfad ein alternierender Pfad ist. Ein Knoten in <math>v\in F</math> heißt dann ''innen'' oder ''ungerade,'' falls <math>\operatorname{d}(r_i,v)\equiv 1\mod 2</math> und andernfalls ''außen'' oder ''gerade.'' <math>\operatorname{d}</math> sei hier die Distanzfunktion in <math>T</math>, gebe also die Länge des eindeutig bestimmten <math>r_i</math>-<math>v</math>-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. Existiert kein freier Knoten mehr, dann existiert auch kein augmentierender Pfad. Diesen alternierenden Baum konstruiert Edmonds, indem er ausgehend von einem freien Knoten nach und nach alle Kanten hinzufügt oder ignoriert. Dabei können für eine neue Kante <math>e=uv</math> (<math>u</math> gehöre bereits zum Baum) folgende Fälle auftreten:

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

Blüten können, anders als bei Fall <math>3</math>, nicht ignoriert werden.<ref>Betrachte [[:Datei:Blossoms can't be ignored.svg|dieses Beispiel]] nach [[#Jungnickel|Jungnickel]] ''398.''</ref> 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.<ref>Diese Idee wurde in {{Cite book
| isbn = 3-486-23911-2
| pages = 103–114
| last = Pape
| first = U.
| coauthors = D. Conradt
| title = Ausgewählte Operations Research Software in FORTRAN
| chapter = Maximales Matching in Graphen
| location = Oldenbourg
| date = 1979
}} vorgeschlagen. [[#Jungnickel|Jungnickel]] ''399'' hat ein Gegenbeispiel, das auf Christian Fremuth-Paeger zurückgeht.</ref> 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 kann ablesen, dass die skizzierte Methode von Edmonds einen Aufwand von <math>\mathcal{O}(n^4)</math> hat. In Fall <math>2.4</math> reinitialisiert Edmonds die Suche und verwirft damit den bereits geleisteten Suchaufwand. [[Harold N. Gabow|Gabow]] 1976<ref>{{Cite journal
| doi = 10.1145/321941.321942
| issn = 0004-5411
| volume = 23
| issue = 2
| pages = 221–234
| last = Gabow
| first = Harold N.
| title = An Efficient Implementation of Edmonds’ Algorithm for Maximum Matching on Graphs
| journal = Journal of the ACM
| date = 1976-04
}}</ref> und [[#Lawler|Lawler]] haben eine naive Implementierung vorgeschlagen, die den Suchaufwand nicht verwirft und eine Laufzeit von <math>\mathcal{O}(n^3)</math> erreicht. Das Beispiel folgt bereits dieser Methode.

<gallery perrow="2" caption="Beispiel zu Edmonds" widths="300%">
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-t2.svg<math>5</math> und<math>6</math> sowie <math>4</math> und <math>14</math> werden wie eben nach Fall <math>2.2</math> hinzugefügt. <math>(6~4)</math> schließt einen geraden Kreis und wird nach <math>2.3</math> ignoriert. Die Kante <math>(4~5)</math> kann nach Fall <math>1.1</math> ignoriert werden.
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-0.svg<math>G</math> zieht eine Blüte zusammen.
Edmonds-example-t4.svg<math>13~10</math> wird nach Fall <math>1</math> ignoriert und <math>12~10</math> nach Fall <math>2.3</math>. <math>12~11</math> schließt eine Blüte <math>B</math>.
Edmonds-example-1.svg|Der reduzierte Graph <math>G'=G/B</math>.
Edmonds-example-t5.svg<math>b~7</math> wird nach <math>2.3</math> ignoriert.
Edmonds-example-2.svg<math>G'</math> mit einer weiteren Blüte <math>B'</math>.
Edmonds-example-t5.svg<math>b~8</math> schließt wieder eine Blüte <math>B'</math>. Blüten können auch Pseudoknoten enthalten.
Edmonds-example-3.svg|Der weiter reduzierte Graph <math>G''=G'/B'</math>
Edmonds-example-t7.svg|Von <math>b'</math> wird der freie Knoten <math>9</math> gefunden, der nach Fall <math>2.1</math> in <math>G''</math> den augmentierenden Pfad <math>P''=(1~2~b'~9)</math> schließt. Die Liftung dieses Pfades liefert <math>P=(1~2~3~5~6~7~8~9)</math> zunächst in <math>G'</math>, der aber auch schon in <math>G</math> selbst liegt.
</gallery>

== Literatur ==
{{Anker|Lovász & Plummer}}
*{{Cite book
| edition = 1
| publisher = Elsevier Science und Akadémiai Kiadó Budapest
| isbn = 0-444-87916-1
| last = Lovász
| first = L.
| coauthors = M. D Plummer
| title = Matching Theory
| location = Budapest
| series = Annals of Discrete Mathematics
| date = 1986
}}
*{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| url = http://diestel-graph-theory.com/german/index.html
}}{{Anker|Jungnickel}}
*{{Cite book
| edition = 3
| publisher = Springer
| isbn = 978-3-540-72779-8
| volume = 5
| last = Jungnickel
| first = Dieter
| title = Graphs, Networks and Algorithms
| series = Algorithms and Computation in Mathematics
| date = 2007
}}{{Anker|Yu & Liu}}
*{{Cite book
| edition = 1
| publisher = Springer
| isbn = 3-540-93951-2
| last = Yu
| first = Qinglin Roger
| coauthors = Guizhen Liu
| title = Graph Factors and Matching Extensions
| location = Beijing
| date = 2009
}}{{Anker|Schrijver}}
*{{Cite book
| publisher = Springer
| isbn = 3-540-44389-4
| volume = A
| last = Schrijver
| first = Alexander
| title = Combinatorial Optimization – Polyhedra and Efficiency
| location = Amsterdam
| series = Algorithms and Combinatorics
| date = 2003
}}{{Anker|Bondy & Murty}}
*{{Cite book
| publisher = Springer
| isbn = 1-84996-690-7
| last = Bondy
| first = Adrian
| coauthors = U.S.R. Murty
| title = Graph Theory
| series = Graduate Texts in Mathematics
| date = 2008
| url = http://blogs.springer.com/bondyandmurty/
}}{{Anker|Burkard, Dell’Amico & Martello}}
*{{Cite book
| publisher = Society for Industrial and Applied Mathematics
| isbn = 978-1-61197-222-1
| last = Burkard
| first = Rainer
| coauthors = Mauro Dell’Amico, Silvano Martello
| title = Assignment Problems (Revised reprint)
| location = Philadelphia
| date = 2012
| url = http://www.assignmentproblems.com/
}}{{Anker|Johnson}}
*{{Cite book
| publisher = American Mathematical Society
| isbn = 0-8218-6598-6
| last = Johnson
| first = David S.
| title = Network Flows and Matching: First Dimacs Implementation Challenge
| date = 1993
}}{{Anker|Lawler}}
*{{Cite book
| publisher = Dover Publications
| isbn = 0-03-084866-0
| last = Lawler
| first = Eugene
| title = Combinatorial Optimization: Networks and Matroids
| location = Rocquencourt
| date = 1976
}}
; Historisch:{{Anker|Kőnig}}
*{{Cite book
| edition = 1. Auflage 1986
| publisher = Teubner Verlagsgesellschaft
| isbn = 3-322-00303-5
| last = Kőnig
| first = Dénes
| title = Theorie der endlichen und unendlichen Graphen – kombinatorische Topologie der Streckenkomplexe.
| location = Leipzig
| series = Teubner Archiv zur Mathematik
| date = 1936
}}{{Anker|Biggs, Lloyd & Wilson}}
*{{Cite book
| publisher = Oxford University Press, USA
| isbn = 0-19-853916-9
| last = Biggs
| first = Norman L.
| coauthors = E. Keith Lloyd, Robin J. Wilson
| title = Graph Theory 1736–1936
| date = 1999
}}

== Weblinks ==
{{Commonscat|Matching (graph theory)|Matching}}

== Einzelnachweise ==
<references />

== Anmerkungen ==
<references group="A" />

{{Normdaten|TYP=s|GND=4831446-8}}

[[Kategorie:Grundbegriff (Graphentheorie)]]

Matching (Graphentheorie)

2017-01-19T13:18:28Z

Flowi: Bei der Laufzeit von Alt et al. (im Quellenverzeichnis) war der Faktor sqrt(m / log(n)) fälschlicherweise im Exponenten (Quelle: ibid)

{{Weiterleitungshinweis|Perfekte Paarung|für den Begriff der nicht-ausgearteten Bilinearform aus der linearen Algebra siehe [[ausgeartete Bilinearform]].}}
Die Theorie um das Finden von '''Matchings''' in Graphen ist in der [[Diskrete Mathematik|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 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:
# Wie findet man ein Matching, das eine maximale Anzahl<ref group="A">Beachte den Unterschied zwischen einem [[Maximales Element|maximalen Element]] und einem [[größtes Element|Maximum]]. Bei der [[#Formalisierung|Formalisierung]] wird darauf genauer eingegangen.</ref> an Dingen einander zuordnet? Dieses Problem ist das ''klassische Matchingproblem.''
# 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 <math>G</math> wird meistens mit <math>\Phi(G)</math> notiert.
# 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 (Zahl)|Vorzeichen]] vertauscht, kann man beide Probleme ohne nennenswerten Aufwand ineinander überführen.
# 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 ''[[Bipartiter Graph|bipartites]] (gewichtetes) Matchingproblem'' und ist ein viel diskutierter Spezialfall.
# 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 „Schwierigkeit“ mit den Methoden der [[Komplexitätstheorie]] und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her.

== Definitionen ==
<gallery class="float-right">
maximal-simple.svg|Ein einfacher Graph mit einem nicht erweiterbaren Matching (maximal matching)
perfect-simple.svg|Derselbe Graph mit einem perfekten (wie auch größtmöglichen) Matching
</gallery>
Das oben beschriebene Problem lässt sich wie folgt formalisieren. Gegeben sei ein endlicher, ungerichteter Graph <math>G=(V,E)</math>. Eine Menge <math>M\subseteq E</math> heißt (gültiges) Matching wenn keine zwei Kanten aus <math>M</math> einen Knoten gemeinsam haben. Ein Matching heißt
; nicht erweiterbar (engl. maximal matching): falls es keine Kante <math>e\in E\setminus M</math> derart gibt, dass <math>\{e\}\cup M</math> ein gültiges Matching ist. Maximale Matchings sind im Vergleich zu den folgenden Begriffen sehr einfach zu berechnen.
; größtmöglich (engl. maximum matching): falls <math>M</math> als Menge eine maximale Kardinalität unter allen gültigen Matchings von <math>G</math> hat. Maximum-Matchings sind maximal. Die Mächtigkeit eines Maximum-Matchings wird ''Matchingzahl'' genannt und mit <math>\nu(G)</math> notiert.
; perfekt: falls <math>2 \cdot | M | = | V |</math> gilt. Perfekte Matchings sind Maximum-Matchings (und damit auch maximal). Perfekte Matchings können als ''[[Graph Faktor|1-Faktoren]]'' eines Graphen, das heißt [[Regulärer Graph|1-reguläre]] aufspannende Teilgraphen, aufgefasst werden. Dieser Auffassung folgend spricht man auch von ''faktorisierbaren Graphen,'' wenn sie einen 1-Faktor besitzen. Beide Sprechweisen sind etwa gleich weit verbreitet.<ref>[[#Yu & Liu|Yu & Liu]] ''4.''</ref>

Für das gewichtete Matchingproblem spielt eine Kostenfunktion <math>c: E\to \mathbb{R}</math> eine Rolle. Ein gültiges Matching heißt dann …
; von maximalem Gewicht: falls <math>c(M) := \sum_{e\in M} c(e)</math> maximal unter allen gültigen Matchings von <math>G</math> ist.
; minimal maximal: falls <math>c(M)</math> minimal unter allen maximalen Matchings ist.

== Historisches ==
[[Datei:Sylvester counter.svg|mini|[[James Joseph Sylvester|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<ref name="ReferenceA">[[#Lovász & Plummer|Lovász & Plummer]] ''xi.''</ref><ref>[[#Yu & Liu|Yu & Liu]] ''3.''</ref> systematischen Untersuchungen von Matchings wird ein Artikel von [[Julius Peter Christian Petersen|Julius Petersen]] angeführt, der 1891 über „Die Theorie der regulären graphs“ schrieb.<ref>{{Cite journal
| volume = 15
| pages = 193–220
| last = Petersen
| first = Julius
| title = Die Theorie der regulären graphs
| journal = [[Acta Mathematica]]
| date = 1891
| doi = 10.1007/BF02392606
}}</ref> Er untersuchte ein Zerlegungsproblem aus der Algebra, das [[David Hilbert]] 1889<ref>{{Cite journal
| volume = 33
| issue = 2
| pages = 223–226
| last = Hilbert
| first = David
| authorlink = David Hilbert
| title = Über die Endlichkeit des Invariantensystems für binäre Grundformen
| journal = Mathematische Annalen
| date = 1889
}}</ref> gestellt hatte, indem er es als Graphenproblem formulierte.<ref name="ReferenceA" /> Letztlich bewies er darin folgendes:
: Für alle Zahlen <math>k\in \mathbb{N}</math> kann jeder <math>2k</math>-reguläre Graph in disjunkte <math>2</math>-Faktoren zerlegt werden. (1)
: Jeder [[Kubischer Graph|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 [[Eulerkreisproblem]]s formulieren.<ref group="A">Es ist nicht bekannt, ob Petersen mit den Arbeiten von [[Leonhard Euler|Euler]] 1736 zu diesem Problem vertraut war ([[#Lovász & Plummer|Lovász & Plummer]] ''xi'').</ref>

Rückblickend erscheinen Petersens Argumente, mit denen er das Obige bewies, kompliziert und umständlich.<ref name="Diestel-43">{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| pages = 43
| url = http://diestel-graph-theory.com/german/index.html
}}
</ref> Bei der weiteren Untersuchung etwa durch [[Henry Roy Brahana|Brahana]] 1917<ref>{{Cite journal
| doi = 10.2307/1967667
| issn = 0003-486X
| volume = 19
| issue = 1
| pages = 59–63
| last = Brahana
| first = Henry Roy
| title = A Proof of Petersen’s Theorem
| journal = The Annals of Mathematics
| date = 1917
}}</ref>, [[Alfred Errera|Errera]] 1922<ref>{{Cite journal
| volume = 36
| pages = 56–61
| last = Errera
| first = Alfred
| title = Une demonstration du théorème de Petersen
| journal = Mathesis
| date = 1922
}}</ref> und [[Orrin Frink|Frink]] 1926<ref>{{Cite journal
| doi = 10.2307/1967699
| issn = 0003-486X
| volume = 27
| issue = 4
| pages = 491–493
| last = Frink
| first = Orrin
| title = A Proof of Petersen’s Theorem
| journal = The Annals of Mathematics
| date = 1926
}}</ref> sowie zusammenfassend durch [[Dénes Kőnig|Kőnig]] 1936<ref>{{Cite book
| last = Kőnig
| first = Dénes
| title = Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
| date = 1936
}}</ref> wurden aber viele Methoden der modernen Graphentheorie entwickelt oder zuerst systematisch formuliert. Petersens Denkansatz wurde dann von [[Fridolin Bäbler|Bäbler]] 1938<ref>{{Cite journal
| doi = 10.1007/BF01214296
| issn = 0010-2571
| volume = 10
| issue = 1
| pages = 275–287
| last = Bäbler
| first = Fridolin
| title = Über die Zerlegung regulärer Streckenkomplexe ungerader Ordnung
| journal = Commentarii Mathematici Helvetici
| date = 1938
}}</ref> 1952<ref>{{Cite journal
| issn = 0010-2571
| volume = 26
| pages = 117–118
| last = Bäbler
| first = Fridolin
| title = Bemerkungen zu einer Arbeit von Herrn R. Cantoni.
| journal = Commentarii Mathematici Helvetici
| date = 1952
| url = http://www.digizeitschriften.de/dms/img/?PPN=GDZPPN002055910
}}</ref> und 1954<ref>{{Cite journal
| doi = 10.1007/BF02566927
| issn = 0010-2571
| volume = 28
| issue = 1
| pages = 155–161
| last = Bäbler
| first = Fridolin
| title = Über den Zerlegungssatz von Petersen
| journal = Commentarii Mathematici Helvetici
| date = 1954
}}</ref> sowie von [[Tibor Gallai|Gallai]] 1950<ref>{{Cite journal
| issn = 0236-5294
| volume = 1
| pages = 133–153
| last = Gallai
| first = Tibor
| title = On factorization of graphs
| journal = Acta Mathematica Academiae Scientiarum Hungaricae
| date = 1950
}}</ref>, [[Hans-Boris Belck|Belck]] 1950<ref>{{Cite journal
| doi = 10.1515/crll.1950.188.228
| issn = 0075-4102
| volume = 1950
| issue = 188
| pages = 228–252
| last = Belck
| first = Hans-Boris
| title = Reguläre Faktoren von Graphen.
| journal = Journal für die reine und angewandte Mathematik (Crelles Journal)
| date = 1950
}}</ref> 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.<ref name="Diestel-43" /> Die zweite Aussage wird auf den Satz von Tutte zurückgeführt.<ref>{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| pages = 45
| url = http://diestel-graph-theory.com/german/index.html
}}</ref>

== Bipartite Matchings ==
Eines dieser frühen Resultate betrifft [[Bipartiter Graph|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. [[Ron Aharoni|Aharoni]] bewies 1984 die Aussage für [[überabzählbar]] unendliche Graphen.<ref>{{Cite journal
| doi = 10.1112/jlms/s2-29.1.1
| issn = 0024-6107
| volume = s2-29
| issue = 1
| pages = 1–12
| last = Aharoni
| first = Ron
| title = Kőnig’s Duality Theorem for Infinite Bipartite Graphs
| journal = Journal of the London Mathematical Society
| date = 1984
}}</ref> Ein elementarer Beweis von (3) findet sich in [[#Lovász & Plummer|Lovász & Plummer]] ''43,'' der von den meisten Lehrbüchern übernommen wurde. [[#Bondy & Murty|Bondy & Murty]] ''200'' führt den Satz auf ein Resultat der [[Lineares Programm|linearen Programmierung]] zurück: Ist <math>A</math> die [[Inzidenzmatrix]] des Graphen <math>G</math>, dann lassen sich maximum Matchings als Lösungen von folgendem ganzzahligen linearen Programm auffassen:
:<math>\max ex \text{ unter } Ax\le 1 \land x\ge 0</math>
Dabei ist <math>e</math> der [[Einsvektor]] bestehend aus lauter Einsen. Das Programm des Knotenüberdeckungsproblems hat folgende Gestalt:
:<math>\min ye \text{ unter } yA\ge 1 \land y\ge 0</math>
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 <math>A</math> [[Total unimodulare Matrix|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 <math>\mathbb{Z}</math> (und damit in diesem speziellen Fall sogar aus <math>\left\{0, 1\right\}</math>) 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.<ref>[[#Lovász & Plummer|Lovász & Plummer]] ''5-40.''</ref><ref>Notizen zu einem Vortrag von Robert D. Borgersen: ''[http://www.robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics.]'' (PDF; 66 kB). November 26, 2004.</ref><ref>{{Cite journal
| pages = 103–141
| last = Jacobs
| first = K.
| title = Der Heiratssatz
| journal = Selecta Mathematica I
| date = 1969
}}</ref> 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 [[Philip Hall|Hall]] 1935<ref>{{Cite journal
| volume = 10
| pages = 26–30
| last = Hall
| first = Philip
| title = On representatives of subsets
| journal = Journal of London Mathematics Society
| date = 1935
}}</ref> angab, um bipartite Graphen mit perfektem Matching zu charakterisieren. Dieser Charakterisierungssatz ist ebenfalls äquivalent zum Satz von Kőnig.
: Ein bipartiter Graph mit Knotenpartitionen <math>S\dot{\cup} T</math> und [[Ohne Beschränkung der Allgemeinheit|o.B.d.A]] <math>|S|\ge |T|</math> hat [[Bikonditional|genau dann]] ein perfektes Matching, wenn für jede Auswahl von Knoten <math>H\subseteq S</math> gilt: <math>|N(H)|\ge |H|</math>. Dabei ist <math>N(H)</math> die [[Nachbarschaftsmenge]] von <math>H</math>. (4)
Aus (4) folgt schnell, dass sich unter den bipartiten Graphen genau alle regulären Graphen <math>1</math>-faktorisieren lassen<ref>[[#Jungnickel|Jungnickel]] ''216.''</ref> und die Aussage (1) von Petersen lässt elegant auf diese Folgerung zurückführen.<ref name="Diestel-43" /> Eine Verallgemeinerung dieses Resultats liefert eine Formel für die Größe eines maximum Matchings, die sogenannte ''Kőnig-Ore'' Formel:<ref>[[#Yu & Liu|Yu & Liu]] ''9.''</ref><ref>[[#Bondy & Murty|Bondy & Murty]] ''422.''</ref>
:<math>\nu(G)= |S| - \max_{H\subseteq S}\{|H|-|N(H)|\}</math>

=== Lösungsverfahren ===
{| class="float-right" style="width:30%" |
|+'''Algorithmus (I)''' 
|
'''Eingabe''' <math>G</math> mit einem beliebigen Matching <math>M</math>
1. '''repeat'''
2. suche verbessernden Pfad <math>P</math>
3. Falls gefunden: Augmentiere <math>M</math> entlang <math>P</math>.
4. '''until''' Suche nach verbesserndem Pfad war erfolglos
'''Ausgabe''' <math>G</math> mit maximum Matching <math>M</math>
|}
Viele der folgenden Konzepte spielen in fast allen Lösungsverfahren von Matchingproblemen eine Rolle. Ist ein Graph <math>G</math> mit einem Matching <math>M</math> gegeben, dann heißt ein Knoten von <math>G</math> ''frei'' (in der Literatur auch ''ungepaart, exponiert, verfügbar'' …) falls er zu keiner Kante in <math>M</math> inzident ist. Andernfalls heißt der Knoten ''gesättigt.'' Ein Pfad <math>P</math> in <math>G</math> heißt ''alternierend,'' falls dieser abwechselnd Kanten aus <math>M</math> und aus <math>M^c</math> enthält. Falls dieser Pfad in einem freien Knoten beginnt und endet, heißt der Pfad ''verbessernd'' oder auch ''augmentierend.'' Die letzte Bezeichnung kommt von der Tatsache, dass <math>P</math> durch <math>M\oplus P</math><ref group="A"><math>\oplus</math> notiert die [[symmetrische Differenz]].</ref> ein größeres Matching als <math>M</math> liefert. Folgendes grundlegendes Resultat von [[Claude Berge|Berge]] 1957<ref>{{Cite journal
| volume = 43
| issue = 9
| pages = 842–844
| last = Berge
| first = Claude
| title = Two theorems in graph theory
| journal = Proceedings of the National Academy of Sciences of the United States of America
| date = 1957-09-15
| url = http://www.pnas.org/content/43/9/842.full.pdf
}}</ref> motiviert das Studium von augmentierenden Pfaden.
: Ein Matching ist genau dann Maximum, wenn es keinen verbessernden Pfad in <math>G</math> bezüglich <math>M</math> gibt.
Diese Bezeichnungen entsprechen genau der Sprache, die auch bei der Behandlung von [[Flüsse und Schnitte in Netzwerken|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.
Gegeben ein Graph <math>G</math> mit Knotenmenge <math>V(G)=S\dot{\cup}T</math>. Konstruiere ein [[Flüsse und Schnitte in Netzwerken#Netzwerk|Netzwerk]] <math>N=(G',u,\sigma,\tau)</math>. Dabei ist <math>V(G')=V(G) \cup \{\sigma,\tau \}</math> und <math>E(G')= E(G)\cup\{(\sigma,s) : s\in S\} \cup \{(t,\tau): t\in T\} </math>. Außerdem ist <math>u</math> die Fortsetzung von der Kostenfunktion <math>c</math>, die alle neuen Kanten mit <code>Inf</code><ref group="A">Programmiersprachen, die das Konzept <code>Inf</code> nicht unterstützen, können die künstlichen Kanten stattdessen mit einer absurd großen Zahl belegen. <math>\textstyle \sum_{e\in E(G)} c(e)</math> genügt in jedem Fall.</ref> belegt.

Mit dem Satz von Berge lässt sich auch gleich ein Algorithmus (I) zum Finden von maximum Matchings angeben.<ref>Aus didaktischen Gründen sehr stark vereinfacht nach [[#Burkard, Dell’Amico & Martello|Burkard, Dell’Amico & Martello]] ''38.'' In der Referenz ist die Methode zum Finden eines verbessernden Pfades wesentlich detaillierter angegeben.</ref> Weil jeder verbessernde Pfad zu einem gegebenen Matching einen weiteren Knoten matcht und maximal <math>\tfrac{n}{2}</math> Knoten zu matchen sind, beschränkt sich die Zahl der Schleifendurchläufe [[Asymptotische Laufzeit|asymptotisch]] durch <math>\mathcal{O}(n)</math>. Eine sehr naive Methode zum Finden verbessernder Pfade stellen sogenannte [[Suchverfahren in Graphen|Graph Scans]] dar, etwa eine Breitensuche (BFS) mit einer Laufzeit von <math>\mathcal{O}(n+m)</math>. Ferner ist <math>m\in \mathcal{O}(n^2)</math>, weil der Graph bipartit ist und damit ist die angegebene Methode in <math>\mathcal{O}(n^3)</math>.

Einer der frühesten Beiträge zum Berechnen von Maximum-Matchings, der über die oben angeführte naive Methode hinausgeht, war der [[Algorithmus von Hopcroft und Karp]] 1973.<ref>{{Cite journal
| doi = 10.1137/0202019
| issn = 0097-5397
| volume = 2
| issue = 4
| pages = 225–231
| last = Hopcroft
| first = John E.
| coauthors = Richard M. Karp
| title = An <math>n^{5/2}</math> Algorithm for Maximum Matchings in Bipartite Graphs
| journal = SIAM Journal on Computing
| date = 1973
}}</ref> 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<ref>{{Cite journal
| doi = 10.1016/0020-0190(91)90195-N
| issn = 0020-0190
| volume = 37
| issue = 4
| pages = 237–240
| last = Alt
| first = H.
| coauthors = N. Blum, K. Mehlhorn, M. Paul
| title = Computing a maximum cardinality matching in a bipartite graph in time <math>\mathcal{O}(n^{1.5}\sqrt{m/\log n})</math>
| journal = Information Processing Letters
| date = 1991
}}</ref> schlagen eine Verbesserung von Hopcroft & Karp vor, indem sie ein Scanningverfahren für [[Adjazenzmatrizen]] nach Cheriyan, Hagerup, and Mehlhorn 1990<ref>{{Cite book
| publisher = Springer-Verlag
| isbn = 3-540-52826-1
| volume = 443
| pages = 235–248
| last = Cheriyan
| first = Joseph
| coauthors = Torben Hagerup, Kurt Mehlhorn
| title = Automata, Languages and Programming
| chapter = Can a maximum flow be computed in <math>\mathcal{O}(nm)</math> time?
| location = Berlin/Heidelberg
| date = 1990
}}</ref> anwenden. Eine einfache Beschreibung der Methode findet sich auch in [[#Burkard, Dell’Amico & Martello|Burkard, Dell’Amico & Martello]] ''47 ff.'' Feder und Motwani 1991<ref>{{Cite conference
| publisher = ACM
| doi = 10.1145/103418.103424
| isbn = 0-89791-397-3
| pages = 123–133
| last = Feder
| first = Tomás
| coauthors = Rajeev Motwani
| title = Clique partitions, graph compression and speeding-up algorithms
| booktitle = Proceedings of the twenty-third annual ACM symposium on Theory of computing
| location = New York
| date = 1991
}}</ref> haben eine Methode vorgeschlagen, die auf der Zerlegung von <math>G</math> in bipartite [[Clique (Graphentheorie)|Cliquen]] beruht und erreichen damit eine asymptotische Laufzeit von <math>\mathcal{O}( \sqrt{n} m \log(n^2 /m)/ \log n)</math>. Eine Methode, die ''nicht'' auf der Idee augmentierender Pfade beruht, sondern sogenannte „starke [[Spannbaum|Spannbäume]]“ benutzt, haben Balinski & Gonzalez 1991<ref>{{Cite journal
| doi = 10.1002/net.3230210203
| issn = 1097-0037
| volume = 21
| issue = 2
| pages = 165–179
| last = Balinski
| first = M. L
| coauthors = J. Gonzalez
| title = Maximum matchings in bipartite graphs via strong spanning trees
| journal = Networks
| date = 1991
}}</ref> vorgeschlagen und erreichen damit eine Laufzeit von <math>\mathcal{O}(n^3)</math>.

== Allgemeiner Fall ==
=== Satz von Tutte ===
{{Hauptartikel|Satz von Tutte}}

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<ref name="tutte">{{Cite journal
| volume = 1
| issue = 2
| pages = 107
| last = Tutte
| first = W. T
| title = The factorization of linear graphs
| journal = Journal of the London Mathematical Society
| date = 1947
}}</ref> eine Charakterisierung für perfekte Matchings in allgemeinen Graphen formulieren und beweisen konnte. Aus diesem tiefliegenden Resultat lassen sich alle bisher besprochenen vergleichsweise leicht herleiten.<ref>[[#Lovász & Plummer|Lovász & Plummer]] ''84.''</ref> Tutte benutzt die einfache Tatsache, dass eine Komponente mit ungerader Knotenzahl in einem Graphen kein perfektes Matching haben kann. Wenn also eine Knotenmenge <math>S</math> so gefunden werden kann, dass <math>G-S</math> mehr ungerade Komponenten als <math>S</math> Knoten hat, dann müsste für ein perfektes Matching aus jeder solcher Komponente wenigstens ein Knoten mit einem Knoten aus <math>S</math> gematcht werden und das kann nicht sein. Es stellt sich heraus, dass die Existenz einer solchen Menge <math>S</math> Graphen ohne perfektes Matching nicht nur beschreibt, sondern charakterisiert:

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

Eine solche Menge <math>T</math> heißt ''Tutte-Menge'' und die Bedingung in (5) heißt ''Tutte-Bedingung.'' Dass sie [[Notwendige Bedingung|notwendig]] für die Existenz perfekter Matching ist, wurde schon skizziert und es gibt mittlerweile 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 [[Pfaffsche Determinante|pfaffschen Determinante]].<ref name="tutte" /> [[Elementare Mathematik|Elementare]] Abzählargumente wurden relativ rasch danach veröffentlicht, wie in Maunsell 1952,<ref>{{Cite journal
| volume = 1
| issue = 1
| pages = 127
| last = Maunsell
| first = F. G.
| title = A note on Tutte’s paper “The factorization of linear graphs”
| journal = Journal of the London Mathematical Society
| date = 1952
}}</ref> Tutte 1952,<ref>{{Cite journal
| pages = 164–178
| first = W. T.
| last = Tutte
| title = The factors of graphs
| journal = Classic Papers in Combinatorics
| date = 1987
}}</ref> Gallai 1963,<ref name="gallai">{{Cite journal
| volume = 8
| pages = 135–139
| last = Gallai
| first = T.
| title = Neuer Beweis eines Tutte’schen Satzes, Magyar Tud
| journal = Akad. Kutató Int. Közl
| date = 1963
}}</ref> Halton 1966<ref>{{Cite journal
| doi = 10.1017/S0305004100040342
| volume = 62
| issue = 04
| pages = 683–684
| last = Halton
| first = John H.
| title = A Combinatorial Proof of a Theorem of Tutte
| journal = Mathematical Proceedings of the Cambridge Philosophical Society
| date = 1966
}}</ref> oder Balinski 1970.<ref>{{Cite journal
| volume = 12
| pages = 570–572
| last = Balinski
| first = M. L.
| title = On perfect matchings
| journal = SIAM Review
| date = 1970
}}</ref> Andere Beweise, wie Gallai 1963,<ref name="gallai" /> Anderson 1971<ref>{{Cite journal
| volume = 10
| issue = 3
| pages = 183–186
| last = Anderson
| first = I.
| title = Perfect matchings of a graph
| journal = Journal of Combinatorial Theory, Series B
| date = 1971
}}</ref> oder Marder 1973<ref>{{Cite journal
| doi = 10.1007/BF01428195
| issn = 0025-5831
| volume = 201
| issue = 4
| pages = 269–282
| last = Mader
| first = W.
| title = 1-Faktoren von Graphen
| journal = Mathematische Annalen
| date = 1973-12
}}</ref> 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<ref>{{Cite journal
| volume = 16
| pages = 3–6
| last = Hetyei
| first = G.
| title = A new proof of a factorization theorem
| journal = Acta Acad. Paedagog. Civitate Pécs Ser. 6 Math. Phys. Chem. Tech
| date = 1972
}}</ref> oder Lovász 1975.<ref>{{Cite journal
| volume = 19
| issue = 3
| pages = 269–271
| last = Lovasz
| first = L.
| title = Three short proofs in graph theory
| journal = Journal of Combinatorial Theory, Series B
| date = 1975
}}</ref>
[[Datei:Blossom Counter.svg|mini|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.<ref>[[#Jungnickel|Jungnickel]] ''409.''</ref> In diesem Beispiel enthält der kontrahierte Graph keinen augmentierenden Pfad, wohl aber der Ausgangsgraph.]]

=== Algorithmus von Edmonds ===
Der erste [[Polynomialzeit]]algorithmus für das klassische Matchingproblem stammt von [[Jack Edmonds]] (1965).<ref>{{Cite journal
| doi = 10.4153/CJM-1965-045-4
| volume = 17
| issue = 3
| pages = 449–467
| last = Edmonds
| first = J.
| title = Paths, trees, and flowers
| journal = Canadian Journal of mathematics
| date = 1965
}}</ref> 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 schwieriger heraus als im bipartiten Fall, weil einige neue Fälle auftreten können. Edmonds Suchmethode konstruiert nach und nach einen ''alternierenden [[Wald (Graphentheorie)|Wald]].'' Das ist ein kreisfreier Graph <math>F</math> mit so vielen Zusammenhangskomponenten wie es freie Knoten gibt. Jeder freie Knoten ist [[Wurzel (Graphentheorie)|Wurzel]] <math>r_i</math> eines [[Baum (Graphentheorie)|Baumes]] <math>T\subset F</math> und <math>F</math> ist so konstruiert, dass für alle anderen Knoten <math>v\in F</math> der eindeutig bestimmte <math>r_i</math>-<math>v</math>-Pfad ein alternierender Pfad ist. Ein Knoten in <math>v\in F</math> heißt dann ''innen'' oder ''ungerade,'' falls <math>\operatorname{d}(r_i,v)\equiv 1\mod 2</math> und andernfalls ''außen'' oder ''gerade.'' <math>\operatorname{d}</math> sei hier die Distanzfunktion in <math>T</math>, gebe also die Länge des eindeutig bestimmten <math>r_i</math>-<math>v</math>-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. Existiert kein freier Knoten mehr, dann existiert auch kein augmentierender Pfad. Diesen alternierenden Baum konstruiert Edmonds, indem er ausgehend von einem freien Knoten nach und nach alle Kanten hinzufügt oder ignoriert. Dabei können für eine neue Kante <math>e=uv</math> (<math>u</math> gehöre bereits zum Baum) folgende Fälle auftreten:

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

Blüten können, anders als bei Fall <math>3</math>, nicht ignoriert werden.<ref>Betrachte [[:Datei:Blossoms can't be ignored.svg|dieses Beispiel]] nach [[#Jungnickel|Jungnickel]] ''398.''</ref> 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.<ref>Diese Idee wurde in {{Cite book
| isbn = 3-486-23911-2
| pages = 103–114
| last = Pape
| first = U.
| coauthors = D. Conradt
| title = Ausgewählte Operations Research Software in FORTRAN
| chapter = Maximales Matching in Graphen
| location = Oldenbourg
| date = 1979
}} vorgeschlagen. [[#Jungnickel|Jungnickel]] ''399'' hat ein Gegenbeispiel, das auf Christian Fremuth-Paeger zurückgeht.</ref> 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 kann ablesen, dass die skizzierte Methode von Edmonds einen Aufwand von <math>\mathcal{O}(n^4)</math> hat. In Fall <math>2.4</math> reinitialisiert Edmonds die Suche und verwirft damit den bereits geleisteten Suchaufwand. [[Harold N. Gabow|Gabow]] 1976<ref>{{Cite journal
| doi = 10.1145/321941.321942
| issn = 0004-5411
| volume = 23
| issue = 2
| pages = 221–234
| last = Gabow
| first = Harold N.
| title = An Efficient Implementation of Edmonds’ Algorithm for Maximum Matching on Graphs
| journal = Journal of the ACM
| date = 1976-04
}}</ref> und [[#Lawler|Lawler]] haben eine naive Implementierung vorgeschlagen, die den Suchaufwand nicht verwirft und eine Laufzeit von <math>\mathcal{O}(n^3)</math> erreicht. Das Beispiel folgt bereits dieser Methode.

<gallery perrow="2" caption="Beispiel zu Edmonds" widths="300%">
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-t2.svg<math>5</math> und<math>6</math> sowie <math>4</math> und <math>14</math> werden wie eben nach Fall <math>2.2</math> hinzugefügt. <math>(6~4)</math> schließt einen geraden Kreis und wird nach <math>2.3</math> ignoriert. Die Kante <math>(4~5)</math> kann nach Fall <math>1.1</math> ignoriert werden.
Edmonds-example-0.svg<math>G</math> bleibt unverändert.
Edmonds-example-0.svg<math>G</math> zieht eine Blüte zusammen.
Edmonds-example-t4.svg<math>13~10</math> wird nach Fall <math>1</math> ignoriert und <math>12~10</math> nach Fall <math>2.3</math>. <math>12~11</math> schließt eine Blüte <math>B</math>.
Edmonds-example-1.svg|Der reduzierte Graph <math>G'=G/B</math>.
Edmonds-example-t5.svg<math>b~7</math> wird nach <math>2.3</math> ignoriert.
Edmonds-example-2.svg<math>G'</math> mit einer weiteren Blüte <math>B'</math>.
Edmonds-example-t5.svg<math>b~8</math> schließt wieder eine Blüte <math>B'</math>. Blüten können auch Pseudoknoten enthalten.
Edmonds-example-3.svg|Der weiter reduzierte Graph <math>G''=G'/B'</math>
Edmonds-example-t7.svg|Von <math>b'</math> wird der freie Knoten <math>9</math> gefunden, der nach Fall <math>2.1</math> in <math>G''</math> den augmentierenden Pfad <math>P''=(1~2~b'~9)</math> schließt. Die Liftung dieses Pfades liefert <math>P=(1~2~3~5~6~7~8~9)</math> zunächst in <math>G'</math>, der aber auch schon in <math>G</math> selbst liegt.
</gallery>

== Literatur ==
{{Anker|Lovász & Plummer}}
*{{Cite book
| edition = 1
| publisher = Elsevier Science und Akadémiai Kiadó Budapest
| isbn = 0-444-87916-1
| last = Lovász
| first = L.
| coauthors = M. D Plummer
| title = Matching Theory
| location = Budapest
| series = Annals of Discrete Mathematics
| date = 1986
}}
*{{Cite book
| edition = 3., neu bearb. und erw. A.
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| url = http://diestel-graph-theory.com/german/index.html
}}{{Anker|Jungnickel}}
*{{Cite book
| edition = 3
| publisher = Springer
| isbn = 978-3-540-72779-8
| volume = 5
| last = Jungnickel
| first = Dieter
| title = Graphs, Networks and Algorithms
| series = Algorithms and Computation in Mathematics
| date = 2007
}}{{Anker|Yu & Liu}}
*{{Cite book
| edition = 1
| publisher = Springer
| isbn = 3-540-93951-2
| last = Yu
| first = Qinglin Roger
| coauthors = Guizhen Liu
| title = Graph Factors and Matching Extensions
| location = Beijing
| date = 2009
}}{{Anker|Schrijver}}
*{{Cite book
| publisher = Springer
| isbn = 3-540-44389-4
| volume = A
| last = Schrijver
| first = Alexander
| title = Combinatorial Optimization – Polyhedra and Efficiency
| location = Amsterdam
| series = Algorithms and Combinatorics
| date = 2003
}}{{Anker|Bondy & Murty}}
*{{Cite book
| publisher = Springer
| isbn = 1-84996-690-7
| last = Bondy
| first = Adrian
| coauthors = U.S.R. Murty
| title = Graph Theory
| series = Graduate Texts in Mathematics
| date = 2008
| url = http://blogs.springer.com/bondyandmurty/
}}{{Anker|Burkard, Dell’Amico & Martello}}
*{{Cite book
| publisher = Society for Industrial and Applied Mathematics
| isbn = 978-1-61197-222-1
| last = Burkard
| first = Rainer
| coauthors = Mauro Dell’Amico, Silvano Martello
| title = Assignment Problems (Revised reprint)
| location = Philadelphia
| date = 2012
| url = http://www.assignmentproblems.com/
}}{{Anker|Johnson}}
*{{Cite book
| publisher = American Mathematical Society
| isbn = 0-8218-6598-6
| last = Johnson
| first = David S.
| title = Network Flows and Matching: First Dimacs Implementation Challenge
| date = 1993
}}{{Anker|Lawler}}
*{{Cite book
| publisher = Dover Publications
| isbn = 0-03-084866-0
| last = Lawler
| first = Eugene
| title = Combinatorial Optimization: Networks and Matroids
| location = Rocquencourt
| date = 1976
}}
; Historisch:{{Anker|Kőnig}}
*{{Cite book
| edition = 1. Auflage 1986
| publisher = Teubner Verlagsgesellschaft
| isbn = 3-322-00303-5
| last = Kőnig
| first = Dénes
| title = Theorie der endlichen und unendlichen Graphen – kombinatorische Topologie der Streckenkomplexe.
| location = Leipzig
| series = Teubner Archiv zur Mathematik
| date = 1936
}}{{Anker|Biggs, Lloyd & Wilson}}
*{{Cite book
| publisher = Oxford University Press, USA
| isbn = 0-19-853916-9
| last = Biggs
| first = Norman L.
| coauthors = E. Keith Lloyd, Robin J. Wilson
| title = Graph Theory 1736–1936
| date = 1999
}}

== Weblinks ==
{{Commonscat|Matching (graph theory)|Matching}}

== Einzelnachweise ==
<references />

== Anmerkungen ==
<references group="A" />

{{Normdaten|TYP=s|GND=4831446-8}}

[[Kategorie:Grundbegriff (Graphentheorie)]]

Dijkstra-Algorithmus

2017-01-10T14:34:50Z

Flowi: "durchschnittliche Laufzeit" (bei Fibonacci-Heaps) geändert zu "Laufzeit": die Laufzeiten des Heaps sind amortisiert (nicht etwa erwartet) und da nur sounsoviele Operationen vom Algorithmus durchgeführt werden, handelt es sich um worst-case-Laufzeit.

[[Datei:Dijkstra Animation.gif|miniatur|Animation des Dijkstra-Algorithmus]]
Der '''Algorithmus von Dijkstra''' (nach seinem Erfinder [[Edsger W. Dijkstra]]) ist ein [[Algorithmus]] aus der Klasse der [[Greedy-Algorithmus|Greedy-Algorithmen]]<ref>Tobias Häberlein: ''Praktische Algorithmik mit Python.'' Oldenbourg, München 2012, ISBN 978-3-486-71390-9, S. 162 ff.</ref> und löst das Problem der [[Kürzester Pfad|kürzesten Pfade]] für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem [[Kantengewichteter Graph|kantengewichteten Graphen]] (sofern dieser keine Negativkanten enthält).

Für [[Zusammenhang von Graphen|unzusammenhängende]] [[Ungerichteter Graph|ungerichtete Graphen]] ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für [[Gerichteter Graph|gerichtete]] nicht [[Stark zusammenhängender Graph|stark zusammenhängende Graphen]].

== Algorithmus ==

=== Informelle Darstellung ===
Die Grundidee des Algorithmus ist es, immer derjenigen Kante zu folgen, die den kürzesten Streckenabschnitt vom Startknoten aus verspricht. Andere Kanten werden erst dann verfolgt, wenn alle kürzeren Streckenabschnitte beachtet wurden. Dieses Vorgehen gewährleistet, dass bei Erreichen eines Knotens kein kürzerer Pfad zu ihm existieren kann. Eine einmal berechnete Distanz zwischen dem Startknoten und einem besuchten Knoten wird nicht mehr geändert. Distanzen zu noch nicht abgearbeiteten Knoten können sich hingegen im Laufe des Algorithmus durchaus verändern, nämlich verringern. Dieses Vorgehen wird fortgesetzt, bis die Distanz des Zielknotens berechnet wurde (''{{lang|en|single-pair shortest path}}'') oder die Distanzen aller Knoten zum Startknoten bekannt sind (''{{lang|en|single-source shortest path}}'').

[[Datei:Dijkstra's algorithm.svg|miniatur|text-top|hochkant=0.6|Berechnung der kürzesten Wege zum linken Knoten]]

Der Algorithmus lässt sich durch die folgenden Schritte beschreiben. Es werden sowohl die kürzesten Wegstrecken als auch deren Knotenfolgen berechnet.

# Weise allen Knoten die beiden Eigenschaften „Distanz“ und „Vorgänger“ zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ∞.
# Solange es noch unbesuchte Knoten gibt, wähle darunter denjenigen mit minimaler Distanz aus und
## speichere, dass dieser Knoten schon besucht wurde.
## Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten.
## Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.
##: Dieser Schritt wird auch als ''Update'' oder ''Relaxieren'' bezeichnet.

In dieser Form berechnet der Algorithmus ausgehend von einem Startknoten die kürzesten Wege zu allen anderen Knoten. Ist man dagegen nur an dem Weg zu einem ganz bestimmten Knoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist.

[[Datei:Dijkstra-negative-edge-weights-error.svg|miniatur|Negative Kantengewichte können zu nicht-optimalen Lösungen führen.]]

Aufgrund der Eigenschaft, einmal festgelegte Distanzen zum Startknoten nicht mehr zu verändern, gehört der Dijkstra-Algorithmus zu den Greedy-Algorithmen, die in jedem Schritt die momentan aussichtsreichste Teillösung bevorzugen. Anders als manche andere Greedy-Algorithmen berechnet der Dijkstra-Algorithmus jedoch stets die optimale Lösung. Diese Eigenschaft basiert auf der Annahme, dass die kürzesten Teilstrecken zwischen Knoten in einem Pfad zusammen die kürzeste Strecke auf diesem Pfad bilden. Unter der Voraussetzung positiver Kantengewichte ist die Annahme gültig, denn fände man nachträglich einen kürzeren Weg vom Startknoten zu einem Zielknoten, hätte man auch dessen kürzere Teilstrecke früher untersuchen müssen, um den Algorithmus korrekt durchzuführen. Dann hätte man aber über die kürzere Teilstrecke den Zielknoten früher gefunden als auf dem längeren Weg.

Die Annahme trifft jedoch nicht mehr zu, wenn der Graph negative Kantengewichte enthält. Dann kann jede Teilstrecke für sich zwar eine kürzeste Strecke zwischen den Endpunkten sein, man könnte jedoch über einen längeren Teilweg die Gesamtdistanz verbessern, wenn eine negative Kante die Weglänge wieder reduziert. Im Bild mit den Knoten 1, 2, 3 und 4 würde der Dijkstra-Algorithmus den kürzesten Weg von 1 nach 3 über 2 finden, da der Schritt zu 4 insgesamt schon länger ist als der gesamte obere Pfad. Die negative Kante bewirkt aber, dass der untere Pfad kürzer ist.

=== Algorithmus in Pseudocode ===
Die folgenden Zeilen Pseudocode beschreiben eine Funktion namens ''Dijkstra'', die einen Graphen und einen Startknoten im Graphen als Eingabe erhält. Der Startknoten gibt den Knoten an, von dem aus die kürzesten Wege zu allen Knoten gesucht werden. Das Ergebnis ist eine Liste, die zu jedem Knoten ''v'' den Vorgängerknoten auf dem Weg vom Startknoten zu ''v'' angibt.

Der Graph besteht aus Knoten und gewichteten Kanten zwischen seinen Knoten. Existiert eine Kante zwischen zwei Knoten, so sind sie jeweils Nachbarn. Das Kantengewicht zwischen benachbarten Knoten ''u'' und ''v'' wird im Pseudocode als ''abstand_zwischen(u,v)'' angegeben.

Zunächst werden abhängig vom Graphen und Startknoten die Abstände und Vorgänger initialisiert. Dies geschieht in der Methode ''initialisiere''. Der eigentliche Algorithmus verwendet eine Methode ''distanz_update'', die ein Update der Abstände durchführt, falls ein kürzerer Weg gefunden wurde.

1 '''Funktion''' Dijkstra(''Graph'', ''Startknoten''):
2 initialisiere(''Graph'',''Startknoten'',abstand[],vorgänger[],''Q'')
3 '''solange''' ''Q'' '''nicht''' leer: ''// Der eigentliche Algorithmus''
4 ''u'':= Knoten in ''Q'' mit kleinstem Wert in abstand[]
5 entferne ''u'' aus ''Q'' ''// für ''u'' ist der kürzeste Weg nun bestimmt''
6 '''für jeden''' Nachbarn ''v'' von ''u'':
7 '''falls''' ''v'' in ''Q'':
8 distanz_update(''u'',''v'',abstand[],vorgänger[]) ''// prüfe Abstand vom Startknoten zu ''v''''
9 '''return''' vorgänger[]

Die Initialisierung setzt die Abstände auf unendlich und die Vorgänger als unbekannt. Nur der Startknoten hat die Distanz 0. Die Menge ''Q'' enthält die Knoten, zu denen noch kein kürzester Weg gefunden wurde.

1 '''Methode''' initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q):
2 '''für jeden''' Knoten ''v'' in ''Graph'':
3 abstand[''v'']:= '''unendlich'''
4 vorgänger[''v'']:= '''null'''
5 abstand[''Startknoten'']:= 0
6 ''Q'':= Die Menge aller Knoten in ''Graph''

Der Abstand vom Startknoten zum Knoten ''v'' verkürzt sich dann, wenn der Weg zu ''v'' über ''u'' kürzer als der bisher bekannte Weg ist. Entsprechend wird ''u'' zum Vorgänger von ''v'' auf dem kürzesten Weg.

1 '''Methode''' distanz_update(u,v,abstand[],vorgänger[]):
2 ''alternativ'':= abstand[''u''] + abstand_zwischen(''u'', ''v'') ''// Weglänge vom Startknoten nach v über u''
3 '''falls''' ''alternativ'' < abstand[''v'']:
4 abstand[''v'']:= ''alternativ''
5 vorgänger[''v'']:= ''u''

Falls man nur am kürzesten Weg zwischen zwei Knoten interessiert ist, kann man den Algorithmus nach Zeile 5 der ''Dijkstra''-Funktion abbrechen lassen, falls ''u'' = ''Zielknoten'' ist.

Den kürzesten Weg zu einem ''Zielknoten'' kann man nun durch Iteration über die ''vorgänger'' ermitteln:

1 '''Funktion''' erstelleKürzestenPfad(Zielknoten,vorgänger[])
2 ''Weg[]'':= [Zielknoten]
3 ''u'':= ''Zielknoten''
4 '''solange''' vorgänger[''u''] '''nicht''' '''null''': ''// Der Vorgänger des Startknotens ist null''
5 ''u'':= vorgänger[''u'']
6 füge ''u'' am Anfang von ''Weg[]'' ein
7 '''return''' Weg[]

=== Implementierung ===
Knoten und Kanten zwischen Knoten lassen sich meistens durch [[Matrix (Mathematik)|Matrizen]] oder [[Zeiger (Informatik)|Zeigerstrukturen]] darstellen. Auch auf den Vorgänger eines Knotens kann ein Zeiger verweisen. Die Abstände der Knoten können in [[Feld (Datentyp)|Feldern]] gespeichert werden.

Für eine effiziente Implementierung wird die Menge ''Q'' der Knoten, für die noch kein kürzester Weg gefunden wurde, durch eine [[Vorrangwarteschlange|Prioritätswarteschlange]] implementiert. Die aufwändige Initialisierung findet nur einmal statt, dafür sind die wiederholten Zugriffe auf ''Q'' effizienter. Als Schlüsselwert für den Knoten wird sein jeweiliger Abstand verwendet, der im Pseudocode mit ''abstand[v]'' angegeben ist. Verkürzt sich der Abstand, ist eine teilweise Neusortierung der Warteschlange nötig.

Als Datenstruktur bietet sich hierfür eine [[Entfernungstabelle]] oder eine [[Adjazenzmatrix]] an.

== Beispiel ==

Ein Beispiel für die Anwendung des Algorithmus von Dijkstra ist die Suche nach einem kürzesten Pfad auf einer Landkarte.<ref>[http://motherboard.vice.com/read/the-simple-elegant-algorithm-that-makes-google-maps-possible ''The Simple, Elegant Algorithm That Makes Google Maps Possible.''] Bei: ''[[Vice (Magazin)|VICE]]'' Abgerufen am 24. März 2015.</ref> Im hier verwendeten Beispiel will man in der unten gezeigten Landkarte von [[Deutschland]] einen kürzesten Pfad von [[Frankfurt am Main|Frankfurt]] nach [[München]] finden.

Die Zahlen auf den Verbindungen zwischen zwei Städten geben jeweils die Entfernung zwischen den beiden durch die Kante verbundenen Städten an. Die Zahlen hinter den Städtenamen geben die ermittelte Distanz der Stadt zum Startknoten ''Frankfurt'' an, ''oo'' steht dabei für ∞, also für unbekannte Distanz. Die hellgrau unterlegten Knoten sind die Knoten, deren Abstand relaxiert wird (also verkürzt wird, falls eine kürzere Strecke gefunden wurde), die dunkelgrau unterlegten Knoten sind diejenigen, zu denen der kürzeste Weg von Frankfurt bereits bekannt ist.

Die Auswahl des nächsten Nachbarn erfolgt nach dem Prinzip einer Prioritätswarteschlange. Relaxierte Abstände erfordern daher eine Neusortierung.

<div style="clear:both;"></div>
<gallery caption="Beispiel" widths="300" heights="250" perrow="2">
MapGermanyGraph.svg|Ausgangssituation: Nicht-initialisierter Graph mit Startknoten Frankfurt und Zielknoten München
DijkstraStep01.svg|Entfernungen vom Startknoten (Frankfurt) ermitteln (relax), Neusortieren der Prioritätswarteschlange Q (1. Mannheim, 2. Kassel, 3. Würzburg, …)
DijkstraStep02.svg|Mannheim ist der nächstliegende Knoten, relax mit Nachbarknoten Karlsruhe, nächster Vorgänger von Karlsruhe ist nun Mannheim, Neusortieren von Q (1. Karlsruhe, 2. Kassel, 3. Würzburg, …)
DijkstraStep03.svg|Dem Startpunkt nächstliegender zu untersuchender Knoten laut Q ist nun Karlsruhe, relax mit Augsburg, Neusortieren von Q (1. Kassel, 2. Würzburg, 3. Augsburg, …)
DijkstraStep04.svg|Nächstliegender zu untersuchender Knoten ist nun Kassel, relax mit München, Neusortieren von Q (1. Würzburg, 2. Augsburg, 3. München, …)
DijkstraStep05.svg|Nächstliegender zu untersuchender Knoten ist nun Würzburg, relax mit Erfurt und Nürnberg, Neusortieren von Q (1. Nürnberg, 2. Erfurt, 3. Augsburg, 4. München, …)
DijkstraStep06.svg|Nächstliegender zu untersuchender Knoten ist nun Nürnberg, relax mit München und Stuttgart, Neusortieren von Q (1. Erfurt, 2. Augsburg, 3. München, 4. Stuttgart, …)
DijkstraStep07.svg|Nächstliegender zu untersuchender Knoten ist nun Erfurt, relax mit niemandem, Neusortieren von Q (1. Augsburg, 2. München, 3. Stuttgart, …)
DijkstraStep08.svg|Nächstliegender zu untersuchender Knoten ist nun Augsburg, relax mit München, Neusortieren von Q (1. München, 2. Stuttgart …)
DijkstraStep09.svg|Zielknoten soll untersucht werden: Kürzester Weg nach München ist nun bekannt; Rekonstruktion mittels ''erstelleKürzestenPfad()''. Dieser ist: Frankfurt-Würzburg-Nürnberg-München.
</gallery>

== Grundlegende Konzepte und Verwandtschaften ==

Ein alternativer Algorithmus zur Suche kürzester Pfade, der sich dagegen auf das [[Optimalitätsprinzip von Bellman]] stützt, ist der [[Floyd-Warshall-Algorithmus]]. Das Optimalitätsprinzip besagt, dass, wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.

Ein weiterer alternativer Algorithmus ist der [[A*-Algorithmus]], der den Algorithmus von Dijkstra um eine Abschätzfunktion erweitert. Falls diese gewisse Eigenschaften erfüllt, kann damit der kürzeste Pfad unter Umständen schneller gefunden werden.

== Berechnung eines Spannbaumes ==

[[Datei:Dijkstra-MSG-Negativbsp.svg|rechts|Negative Kante sorgt für Unklarheiten bei Knoten ''a''.]]

Nach Ende des Algorithmus ist in den Vorgängerzeigern ''π'' ein Teil-[[Spannbaum]] der [[Zusammenhang von Graphen|Komponente]] von <math> \left. s \right. </math> aus kürzesten Pfaden von <math> \left. s \right. </math> zu allen Knoten der Komponente, die in die Queue aufgenommen wurden, verzeichnet. Dieser Baum ist jedoch nicht notwendigerweise auch minimal, wie die Abbildung zeigt:

Sei <math> \left. x \right. </math> eine Zahl größer 0. Minimal spannende Bäume sind entweder durch die Kanten <math> \left\{ a,s \right\} </math> und <math> \left\{ a,b \right\} </math> oder <math> \left\{ b,s \right\} </math> und <math> \left\{ a,b \right\} </math> gegeben. Die Gesamtkosten eines minimal spannenden Baumes betragen <math> \left. 2 +x \right. </math>. Dijkstras Algorithmus liefert mit Startpunkt <math> \left. s \right. </math> die Kanten <math> \left\{ a,s \right\} </math> und <math> \left\{ b,s \right\} </math> als Ergebnis. Die Gesamtkosten dieses spannenden Baumes betragen <math>\left. 2+2x \right. </math>.

Die Berechnung eines [[Spannbaum|minimalen Spannbaumes]] ist mit dem [[Algorithmus von Prim]] oder dem [[Algorithmus von Kruskal]] möglich.

== Zeitkomplexität ==
Die folgende Abschätzung gilt nur für Graphen, die keine negativen Kantengewichte enthalten.

Die Laufzeit des Dijkstra Algorithmus hängt ab von der Anzahl der Kanten <math>|E|</math> und der Anzahl der Knoten <math>|V|</math>. Die genaue Zeitkomplexität hängt von der Datenstruktur <math>Q</math> ab, in der die Knoten gespeichert werden.
Für alle Implementierungen von <math>Q</math> gilt:
:<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>
wobei <math>T_\mathrm{dk}</math> und <math>T_\mathrm{em}</math> für die Komplexität der ''decrease-key'' und ''extract-minimum'' Operationen bei <math>Q</math> stehen. Die einfachste Implementierung für <math>Q</math> ist eine Liste oder ein Array. Dabei ist die Zeitkomplexität
<math>O(|E| + |V|^2) = O(|V|^2)</math>

Im Normalfall wird man hier auf eine [[Vorrangwarteschlange]] zurückgreifen, indem man dort die Knoten als Elemente mit ihrer jeweiligen bisherigen Distanz als Schlüssel/Priorität verwendet.

 
Die optimale Laufzeit für einen Graphen <math>G = (V, E)</math> beträgt <math>O(|V| \log(|V|) + |E|)</math> <ref>{{Literatur|Autor=Thomas H. Cormen|Titel=Introduction to Algorithms|Hrsg=|Sammelwerk=|Band=|Nummer=|Auflage=|Verlag=MIT Press|Ort=|Datum=|Seiten=663|ISBN=}}</ref> mittels Verwendung eines [[Fibonacci-Heap]] für den Dijkstra-Algorithmus.

== Anwendungen ==

[[Routenplaner]] sind ein prominentes Beispiel, bei dem dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Verkehrswegenetz, das verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Einige [[Topologischer Deskriptor|topologische Indizes]], etwa der [[Balaban-J-Index|J-Index]] von Balaban, benötigen gewichtete Distanzen zwischen den Atomen eines [[Molekül]]s. Die Gewichtung ist in diesen Fällen die Bindungsordnung.

Dijkstras Algorithmus wird auch im [[Internet]] als [[Routing]]-Algorithmus im [[Open Shortest Path First|OSPF]]- und [[Optimized Link State Routing|OLSR]]-Protokoll eingesetzt. Das letztere ''Optimized Link State Routing''-Protokoll ist eine an die Anforderungen eines mobilen drahtlosen LANs angepasste Version des [[Link-State|Link State Routing]]. Es ist wichtig für mobile [[Ad-hoc-Netz]]e. Eine mögliche Anwendung davon sind die [[Freies Funknetz|freien Funknetze]].

Auch bei der Lösung des [[Münzproblem]]s, eines zahlentheoretischen Problems, das auf den ersten Blick nichts mit Graphen zu tun hat, kann der Dijkstra-Algorithmus eingesetzt werden.

== Andere Verfahren zur Berechnung kürzester Pfade ==

Hat man genug Informationen über die Kantengewichte im Graphen, um daraus eine [[Heuristik]] für die Kosten einzelner Knoten ableiten zu können, ist es möglich, den Algorithmus von Dijkstra zum [[A*-Algorithmus]] zu erweitern. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graphen zu berechnen, kann man auch den [[Bellman-Ford-Algorithmus]] verwenden, der mit negativen Kantengewichten umgehen kann. Der [[Algorithmus von Floyd und Warshall]] berechnet schließlich die kürzesten Pfade aller Knoten zueinander.

== Algorithmen zum Auffinden minimaler Spannbäume ==

* [[Algorithmus von Kruskal]]
* [[Algorithmus von Borůvka]]
* [[Algorithmus von Prim]]

== Literatur ==
* {{BibISBN|3486275151|Seite=598–604}}
* [[Edsger W. Dijkstra]]: ''A note on two problems in connexion with graphs.'' In: ''Numerische Mathematik.'' 1, 1959, S. 269–271 ([http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf PDF; 739 kB])

== Weblinks ==

{{Wikibooks|Algorithmensammlung: Graphentheorie: Dijkstra-Algorithmus|Dijkstra-Algorithmus|Implementierungen in der Algorithmensammlung}}
* [https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus]
* [http://www.dgp.toronto.edu/~jstewart/270/9798s/Laffra/DijkstraApplet.html Java-Applet zu Dijkstra] (englisch)
* [http://www.uweschmidt.org/dijkstravis Interaktive Visualisierung und Animation von Dijkstras Algorithmus, geeignet für Personen ohne Vorkenntnisse von Algorithmen] (englisch)
* [http://computer.howstuffworks.com/routing-algorithm3.htm Implementierung in C] (englisch)
* [http://algo2.iti.uni-karlsruhe.de/singler/algorithmus-der-woche/Kuerzeste%20Wege.pdf Erklärung anhand eines analogen Modells] (PDF; 213 kB)
* [http://jgrapht.org Öffentliche Softwarebibliothek in Java mit diesem und anderen Algorithmen] (englisch)
* [http://sourceforge.net/projects/dijkstromania/ Java Implementierung – Simulation / Auswertung] (englisch)
* [http://www.hann3mann.de/artikel/dijkstra-algorithmus-in-c-csharp/ Implementierung in C#]

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus|Dijkstra, Algorithmus von]]
[[Kategorie:Graphsuchalgorithmus]]
[[Kategorie:Routing]]
[[Kategorie:Reise- und Routenplanung]]

Algorithmus von Borůvka

2016-08-30T13:32:30Z

Flowi: Sortieren ist unnötig und für die Entwicklung schnellerer Algorithmen sogar hinderlich (siehe Eintrag Diskussionsseite). #Teilgerüste wird mindestens (!) halbiert. Mathmode verwendet.

Der '''Algorithmus von Borůvka''' gilt als erster [[Algorithmus]] zum Auffinden [[Minimaler Spannbaum|minimaler Spannbäume]] in [[Ungerichteter Graph|ungerichteten Graphen]]. Er wurde 1926 von dem tschechischen Mathematiker [[Otakar Borůvka]] beschrieben. Die beiden bekannteren Algorithmen zur Lösung dieses Problems sind der [[Algorithmus von Prim]] und der [[Algorithmus von Kruskal]]. In der Erstveröffentlichung dieser beiden Algorithmen wird Borůvka jeweils erwähnt.

== Grundprinzip und Komplexität ==
Wie auch der Algorithmus von Kruskal startet der Algorithmus von Borůvka mit vielen Teilgerüsten, die aus jeweils einem Knoten der Knotenmenge V des Graphen G = (V, E) bestehen. In jeder nun folgenden [[Iteration]] wird eine kürzeste Kante von einem Teilgerüst zu einem anderen gesucht. Die Auswahl dieser Kanten kann insbesondere bei der Möglichkeit zur parallelen Ausführung simultan geschehen, was den Algorithmus attraktiv für parallele Implementierungen macht. Die so verbundenen Teilgerüste werden zu jeweils einem Teilgerüst verschmolzen. Bei jeder Iteration wird auf diese Weise die Anzahl der Teilgerüste mindestens halbiert, so dass der Algorithmus in maximal <math>\log_2 |V|</math> Phasen terminiert. Da jede Iteration in <math>\mathcal{O}(|E|)</math> durchgeführt werden kann, ist die Gesamtkomplexität des Algorithmus insgesamt <math>\mathcal{O}(|E| \log |V|)</math>.

== Literatur ==
*Borůvka, Otakar (1926). "O jistém problému minimálním (About a certain minimal problem)". Práce mor. přírodověd. spol. v Brně III (in Czech, German summary) 3: 37–58.
*Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech) 15: 153–154.
*Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics 233 (1–3): 3–36. {{doi|10.1016/S0012-365X(00)00224-7}}.
*Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes-rendus de l’Académie des Sciences (in French) 206: 310–313.
* Florek, Kazimierz (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum 2 (1951) (in French): 282–285.
* Sollin, M. (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
* Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R.; Urrutia, J. Handbook of Computational Geometry. Elsevier. pp. 425–461.
*Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320.

[[Kategorie:Graphsuchalgorithmus|Boruvka]]
[[Kategorie:Optimierungsalgorithmus|Boruvka]]

Diskussion:Algorithmus von Borůvka

2016-08-30T13:23:29Z

Flowi: Neuer Abschnitt /* Komplexität und Sortieren */

== Anzahl der Teilgerüste ==

Meiner Meinung nach verringert sich die Anzahl der Teilgerüste bei Hinzufügen einer Kante lediglich um 1, denn aus zwei Teilgerüsten wird eines (''nicht'' aus ''jeweils'' zwei Teilgerüsten eines). Die Auswahl der beiden Teilgerüste ist ''nicht'' beliebig, sondern es muss tatsächlich die Kante mit dem geringsten Gewicht unter allen Kanten zwischen Teilgerüsten gewählt werden (wie auch beim [[Algorithmus von Kruskal]]), andernfalls wird möglicherweise nicht der minimale Spannbaum gefunden. -- [[Benutzer:Carsten Milkau|Carsten Milkau]] 16:34, 2. Sep. 2008 (CEST)

== Komplexität und Sortieren ==

Im Artikel stand bisher, dass man die Kanten in O(|E| log |V|) sortieren "muss". Es ist überhaupt nicht klar, dass man das "muss". Außerdem ist O keine untere Schranke...

Tatsächlich kann man in jeder Iteration das Minimum der aus einer Komponente/Gerüst ausgehenden Kanten bestimmen (in Summe über den ganzen Graphen O(|E|)) und erreicht so (zugegebenermaßen) ebenfalls die O(|E| log |V|).
Interessanterweise kann man aber durch Durchführen von nur O(loglog|V|) Borůvka-Phasen und anschließender Ausführung des Prim-Algorithmus (mit Fibonacci-Heaps) auf dem so kontrahierten Graphen eine Gesamtlaufzeit von O(|E| loglog|V|) erreichen. Dann ist das "Vorab-Sortieren" definitiv nicht optimal! (Bereits zehn Jahre vor Entdeckung der Fibonacci-Heaps hatte Andrew Yao 1974 gezeigt, dass loglog möglich ist durch eine Abwandlung von "Sollins" (Borůvkas) Algorithmus.)

Ich werde den Artikel dementsprechend ändern. Dieser Eintrag soll als Erklärung für den Edit dienen, wenn Fragen aufkommen.

[[Benutzer:Flowi|Flowi]] ([[Benutzer Diskussion:Flowi|Diskussion]]) 15:23, 30. Aug. 2016 (CEST)

Felix Leinen

2015-12-04T21:57:16Z

Flowi: Links ausgetauscht (einer ohne Login nicht sichtbar, der andere verweist auf den neuen Link)

[[Datei:Felixleinen.JPG|mini|Felix Leinen]]
'''Felix Leinen''' (* [[15. Mai]] [[1957]] in [[Wiesbaden]]) ist ein deutscher Professor, Diplom-Mathematiker und Politiker ([[Ökologisch-Demokratische Partei|ÖDP]]).

== Familie und beruflicher Werdegang ==
Leinen studierte von 1976 bis 1982 [[Mathematikstudium|Mathematik]] mit Nebenfach [[Physikstudium|Physik]]. Die [[Promotion (Doktor)|Promotion]] zum Dr. rer. nat. erfolgte 1984 an der [[Albert-Ludwigs-Universität Freiburg|Albert-Ludwigs-Universität]] [[Freiburg im Breisgau]]. Seit 1985 arbeitet er an der Universität Mainz. Leinen ist außerplanmäßiger Professor an der [[Johannes Gutenberg-Universität Mainz|Johannes Gutenberg-Universität]] [[Mainz]]. Zwischenzeitlich hatte er mehrere berufliche Auslandsaufenthalte in England, Italien und den USA.
Nebenbei war von 1974 bis 1984 Helfer beim [[Technisches Hilfswerk|Technischen Hilfswerk]]. Leinen ist verheiratet und hat vier Kinder.

== Politische Karriere ==
In den späteren 1990er Jahren war er in einer Bürgerinitiative aktiv, die gegen die Umwandlung der in der Stadt Mainz gelegenen ''Laubenheimer Höhe'' (→ [[Mainz-Laubenheim]]) in einen Steinbruch kämpfte. 1999 trat er außerdem der ÖDP bei, deren stellvertretender Bundesvorsitzender er von 2008 bis 2010 war. Er leitet den Bundesarbeitskreis ''Bildungspolitik'' der ÖDP. Leinen ist Schatzmeister der [[Rheinland-Pfalz|rheinland-pfälzischen]] ÖDP und Vorsitzender des ÖDP-Ortsverbands [[Mainz-Hechtsheim]]. Bei der Kommunalwahl von 2009 gelang ihm der Einzug in den [[Mainz]]er Stadtrat, und er behielt sein Mandat in der folgenden Kommunalwahl 2014.

== Weblinks ==
* [http://www.staff.uni-mainz.de/leinen/AG%20Gruppentheorie/Leinen/ Leinens Internetauftritt] an der Universität Mainz
* [http://www.staff.uni-mainz.de/leinen/AG%20Gruppentheorie/Leinen/Publications.html Publikationsliste] auf seinem Internetauftritt

{{Normdaten|TYP=p|GND=|GNDName=114371121|GNDfehlt=ja|GNDCheck=2012-12-02}}

{{SORTIERUNG:Leinen, Felix}}
[[Kategorie:ÖDP-Mitglied]]
[[Kategorie:Hochschullehrer (Johannes Gutenberg-Universität Mainz)]]
[[Kategorie:Person (Technisches Hilfswerk)]]
[[Kategorie:Deutscher]]
[[Kategorie:Geboren 1957]]
[[Kategorie:Mann]]
[[Kategorie:Kommunalpolitiker (Mainz)]]

{{Personendaten
|NAME=Leinen, Felix
|ALTERNATIVNAMEN=
|KURZBESCHREIBUNG=deutscher Mathematiker und Politiker (ÖDP)
|GEBURTSDATUM=15. Mai 1957
|GEBURTSORT=[[Wiesbaden]]
|STERBEDATUM=
|STERBEORT=
}}