Matching

Ein Matching $M$ in einem ungerichteten Graph $G = (V,E)$ besteht aus einer Menge von unabhängigen Kanten, d.h. Kanten, die keine gemeinsamen Endknoten haben. Ein Matching modelliert mögliche Zuordnungen in einem System von binären Beziehungen, z.B. Spielpartner in einem Tennisturnier.

Bzgl. eines Matchings $M$ wird ein Knoten frei genannt, wenn er nicht Endpunkt einer Matchingkante ist; der Knoten heißt belegt, wenn er Endpunkt von (genau) einer Matching-Kante ist. In einem gewichteten Graphen werden die Kosten eines Matchings durch die Summe der Gewichte der benutzten Kanten definiert.

$M$ ist ein Maximal-Matching, wenn zu $M$ keine weitere Kante hinzugefügt werden kann.

$M$ ist ein Maximum-Matching, wenn es keine anderen Matchings mit mehr Kanten gibt.

$M$ ist ein perfektes Matching, wenn alle Knoten belegt sind.

$M$ ist ein Minimum-Cost-Matching, wenn es von allen perfekten Matchings die geringsten Kosten verursacht.

Maximale Matchings können mit einem Greedyverfahren bestimmt werden, indem solange Kanten zwischen freien Knoten gewählt werden, bis dies nicht mehr möglich ist.

Maximum-Matchings können bestimmt werden, indem ausgehend von einem initialen Matching sogenannte erweiternde Wege gefunden werden, längs derer das Matching vergrößert wird. Genauer: Ein alternierender Weg bzgl. eines Matchings $M$ ist eine Sequenz von Kanten mit jeweils gemeinsamen Endpunkten, die abwechselnd zum Matching und nicht zum Matching gehören. Ein erweiternder Weg bzgl. eines Matchings $M$ ist ein alternierender Weg bzgl. $M$, der bei einem freien Knoten beginnt und bei einem freien Knoten endet. Durch Umtauschen der Matchingkanten in Nicht-Matchingkanten und umgekehrt kann längs des erweiternden Weges das Matching um eine Kante erhöht werden.

Es gilt der Satz:

$M$ ist ein Maximum-Matching $\iff$ es gibt keinen erweiternden Weg mehr.

Folgendes Bild zeigt ein maximales Matching bestehend aus vier (dick gezeichneten) Kanten. Dieses Matching lässt sich durch den alternierenden (gestrichelt gezeichneten) Weg über die Knoten $c,f,d,g,e,h$ um eine Kante erweitern. Es besteht dann aus den 5 Kanten $(a,b), (c,f), (d,g), (e,h), (i,j)$ und bildet ein Maximum-Matching.