Matching (auch Paarung) ist in der Graphentheorie eine Auswahl von Kanten eines Graphen, bei der keine zwei Kanten einen gemeinsamen Knoten teilen. Vereinfacht: Jeder Knoten ist höchstens einmal „verheiratet“ — die ausgewählten Kanten bilden paarweise unabhängige Verbindungen.
Arten von Matchings
- Maximales Matching: Keine weitere Kante kann hinzugefügt werden, ohne die Bedingung zu verletzen.
- Größtes Matching: Enthält so viele Kanten wie irgend möglich (maximale Kardinalität) — das größte Matching ist immer auch maximal, aber nicht umgekehrt.
- Perfektes Matching: Jeder Knoten des Graphen ist von genau einer Matching-Kante berührt. Dafür muss der Graph eine gerade Anzahl Knoten haben.
Matching in bipartiten Graphen
Besonders wichtige Rolle spielt das Matching in bipartiten Graphen, deren Knotenmenge in zwei Gruppen zerfällt. Der Satz von Hall (Heiratssatz) gibt an, wann eine Zuordnung existiert, die jede Person der einen Gruppe mit einem Partner der anderen verbindet. Algorithmen wie Hopcroft-Karp finden das größte Matching in bipartiten Graphen effizient; der Knotengrad der Teilknoten spielt dabei eine Schlüsselrolle.
Anwendungen
- Zuordnungsprobleme: Bewerber auf Jobs, Patienten auf Spenderorgane, Studenten auf Praktikumsplätze.
- Stundenpläne: Kurse und Räume bzw. Dozenten so kombinieren, dass keine Ressource doppelt belegt ist.
- Turniere: Rundenpaarungen ohne sich wiederholende Gegner.
- Transport & Logistik: Lieferungen an Empfänger mit minimalen Kosten (Gewichtetes Matching).
Abgrenzung
Ein Matching ist ein spezieller Subgraph: Er besteht nur aus den Matching-Kanten und den berührten Knoten. In ungerichteten Graphen ist jede Kantenauswahl ohne gemeinsame Endknoten ein Matching; in gerichteten Graphen gelten die Kanten als unabhängig, wenn auch ihre Richtungs-Interpretation dies zulässt. Nicht verwechseln mit Zusammenhangskomponenten — ein Matching erzeugt grundsätzlich nur isolierte Kantenpaare, keine größeren Verbundstrukturen.