Ein perfektes Matching (englisch perfect matching, auch vollständige Paarung) ist ein Matching, das jeden Knoten des Graphen mit genau einer Kante überdeckt. Während ein Matching nur fordert, dass keine zwei Kanten einen gemeinsamen Knoten teilen, verlangt das perfekte Matching zusätzlich, dass kein Knoten unpaarig bleibt.
Definition
Ein Matching in einem Graphen ist eine Menge von Kanten ohne gemeinsame Knoten. Ein perfektes Matching M existiert genau dann, wenn jeder Knoten Endpunkt genau einer Kante aus M ist. Bei n Knoten muss |M| = n/2 gelten — daher ist eine gerade Knotenzahl eine notwendige Bedingung. Bei einem bipartiten Graphen mit den beiden Teilmengen A und B muss zusätzlich |A| = |B| gelten.
Existenzkriterien
Der Satz von Hall (auch Heiratssatz genannt) liefert für bipartite Graphen ein exaktes Kriterium: Ein perfektes Matching existiert genau dann, wenn für jede Teilmenge S der einen Seite die Menge der Nachbarn N(S) mindestens so groß ist wie S selbst. Anschaulich: Egal welche Auswahl an Personen der einen Gruppe man betrachtet, es gibt immer genügend mögliche Partner in der anderen Gruppe.
Für allgemeine Graphen ist die Frage, ob ein perfektes Matching existiert, trotzdem in Polynomialzeit lösbar — der Blossom-Algorithmus von Edmonds (1965) entscheidet sie effizient, auch mit einer Verallgemeinerung zur Suche nach perfekten Matchings maximalen Gewichts.
Komplexität
- Bipartite Graphen: Der Hopcroft-Karp-Algorithmus findet ein maximales Matching in O(E·√V) — auch perfekte Matchings, sofern sie existieren.
- Allgemeine Graphen: Der Blossom-Algorithmus läuft in polynomialer Zeit und findet entweder ein perfektes Matching oder beweist, dass keines existiert.
- Nicht jeder Graph hat ein perfektes Matching: Ein Stern mit ungerader Knotenzahl oder ein Pfad mit drei Knoten besitzt keins, obwohl maximale Matchings existieren.
Anwendungen
- Partner- und Team-Zuordnung: Personen so paaren, dass jeder genau einmal zugeordnet ist.
- Praktikums- und Stundenplanprobleme: Jeder Bewerber erhält genau einen Platz, jede Gruppe genau einen Bewerber.
- Dominoprobleme: Ein Schachbrett mit 2n Feldern lässt sich genau dann lückenlos mit Dominosteinen belegen, wenn der zugehörige Kantengraph des Brettes ein perfektes Matching besitzt.
Verwandte Grundlagen: Matching, gewichtetes Matching, bipartiter Graph, Graph-Datenstruktur, Knotengrad.