Grundlagen Matchingtheorie

Als Matching bezeichnet man die Einteilung der Elemente einer Menge in Zweier-Paare, sodass jedes Element nur in maximal einem Paar vorkommen kann. Solche Zuordnungen sind in vielen verschiedenen Bereichen interessant. Hierzu zählen unter anderem der Aufbau von Server-Client-Verbindungen, die Verteilung von Spenderorganen an Patienten oder die Vergabe von Schulplätzen. Auf unserer Seite zum School-Choice-Problem befindet sich eine ausführlichere Beschreibung zur Schulplatzvergabe als Matchingproblem.

Je nach Anwendungsfall muss das gefundene Matching verschiedene Eigenschaften erfüllen. Zum Finden solcher Matchings wurden unterschiedliche Algorithmen entwickelt. Zum Beispiel wurde der Boston-Algorithmus speziell für das School-Choice-Problem entwickelt. Dieser soll möglichst viele Schüler den Schulen zuordnen, die sie am meisten präferieren. In diesem Fall wird dann von einem bb-Matching gesprochen, da mehrere Schüler mit einer Schule gematcht werden.

Häufig werden Matchings in einem Graphen dargestellt. Hier stehen die Knoten für die Elemente und die Kanten für mögliche Zuordnungen. Ein Matching ist dann eine Teilmenge der Kanten.

Matching

Definition

Sei G=(V,E)G = (V,E) ein Graph. Dann heißt eine Teilmenge M⊆EM \subseteq E Matching auf GG, wenn keine zwei Kanten in MM zum selben Knoten inzident sind.

Matching als Abbildung

Definition

Sei G=(V,E)G = (V,E) ein Graph. Dann heißt M:V→V∪{∅}M: V \rightarrow V \cup \{\emptyset\} mit

M(v):={∅∄e∈M fu¨r das gilt v inzident zu euwenn {u,v}∈MM(v) := \begin{cases} \emptyset & \nexists e \in M \text{ für das gilt } v \text{ inzident zu } e\\ u & \text{wenn } \{u,v\} \in M \end{cases}

ein Matching MM auf GG.

b-Matching

Das bb-Matchingproblem stellt eine Verallgemeinerung des Matchingproblems dar.

Definition

Ein bb-Matching ist eine Teilmenge von Kanten M⊆EM \subseteq E, sodass jeder Knoten vv ∈\in VV zu maximal bvb_v Kanten dieser Menge inzident ist. Für jeden Knoten v∈Vv \in V ist bvb_v die Kapazität von vv.

Für den Spezialfall, dass bv=1b_v = 1 für jeden Knoten vv ∈\in VV gilt, ist MM ein Matching.

Im bb-Matching kann also mehr als ein Matchingpartner erlaubt sein. Dies ermöglicht die Darstellung von Kapazitäten von Knoten.

Beispiel:

In einem Restaurant wird jedem Tisch ein diensthabender Kellner zugeteilt. Ein Tisch wird maximal von einem Kellner bewirtet. Ein Kellner kann gleichzeitig für bis zu 3 Tische zuständig sein. Die möglichen Zuteilungen von Kellnern und Tischen sind hier als graue Kanten dargestellt. Die lachsfarbenen Kanten in diesem bipartiten Graphen stellen ein bb-Matching dar, welches den Kellnern w1w_1 und w2w_2 Tische zuordnet. Dabei gilt: bt1=bt2=bt3=bt4=bt5=1b_{t_1} = b_{t_2}= b_{t_3} = b_{t_4} = b_{t_5} = 1 sowie bw1=bw2=3b_{w_1} = b_{w_2} = 3.

M-alternierende Wege oder Kreise

Definition

Sei G=(V,E)G = (V,E) ein Graph und M⊆EM \subseteq E ein Matching in diesem Graphen. MM-alternierende Wege oder Kreise in einem Graphen GG sind Wege oder Kreise, die alternierend Kanten aus MM und E∖ME \setminus M enthalten.

M-augmentierende Wege

Definition

Sei G=(V,E)G = (V,E) ein Graph und M⊆EM \subseteq E ein Matching in diesem Graphen. MM-augmentierende Wege, in einem Graphen GG sind MM-alternierende Wege, deren Start- und Endkanten nicht in M sind.

In diesem Graph, mit den lachsfarbenden Kanten als Matching, ist der Weg {a,d,b,e}\{a,d,b,e\} ein augmentierender Weg.

Symmetrische Differenz

Definition

Die symmetrische Differenz M△PM \vartriangle P zwischen einem Matching MM und einem Weg PP bezeichnet (M∖P)∪(P∖M)(M \setminus P) \cup (P \setminus M).

Die symmetrische Differenz zwischen einem Matching MM und einem größeren Matching M′M' besteht aus elementaren Kreisen, alternierenden Pfaden und aus einzelnen Knoten.

Matching MM

Matching M′M' mit ∣M′∣>∣M∣|M'| > |M|

Die symmetrische Differenz M△M′M \vartriangle M'.


Man erkennt die isolierten Knoten, einen elementaren Kreis und einen elementaren Weg.