Leonard Mory, Felix Lüpke

Thematischer Einstieg und Motivation

Erläuterung

• Bei Matching-Problemen handelt es sich um spezielle Zuordnungsprobleme
• werden auch als Zuteilungsprobleme bezeichnet
• Gegenstand ist die optimale Zuordnung der Elemente zweier disjunkter Mengen
• Zuordnungsprobleme sind z.B. Bewerber auf freie Stellen, Lehrer auf Schulklassen
• eine erfolgreiche Paarbildung nennt sich Matching

Effizienz

• Matchingprobleme werden in Polynomialzeit gelöst

Definition

Ein Graph G=(V,E) heißt bipartiter Graph, wenn man V in zwei disjunkte Mengen U und W zerlegen kann, so dass alle Kanten zwischen U und W verlaufen.

Matching

Ein Matching von G=(V,E) ist eine Teilmenge M ⊆ E der Kanten von G mit der Eigenschaft, dass keine zwei Kanten einen gemeinsamen Knoten besitzen.

• ein Knoten kann nur zu einer Matchingkante gehören
• zwei Matchingkanten dürfen niemals adjazent sein

   Hinweis Das Stellen und Bearbeiten von Matchingproblemen setzt keinesfalls einen Bipartiten Graphen voraus, bietet sich jedoch an. 
   Einem nicht bipartiten Graphen, für den ein Matching existiert, können wir dennoch einen bipartiten Kontext "unterstellen".

Maximales Matching

Ein Matching M von G ist maximal, wenn jedes Hinzufügen einer weiteren Kante zu M das Matching zerstört. Die Knoten der Kanten, die zu einem Matching gehören, nennt man vom Matching überdeckt.

• Wenn der Graph aus n Knoten besteht, kann ein maximales Matching \frac{n}{2} Kanten beinhalten
• Ein maximales Matching wird auch "nicht erweiterbar" genannt

Es ist wichtig den Unterschied zwischen einem erweiterten- und einem völlig anderen Matching zu erkennen

Perfektes Matching

   M ist perfekt wenn: \forall e(v,w) \in M \colon \forall \{ v,w\} \subseteq V , so ist M perfekt.

Sind alle Knoten von G von einem Matching überdeckt, so handelt es sich um ein perfektes Matching.

• damit ist die maximale Mächtigkeit eines Matching erreicht
• Anzahl n der Knoten muss dafür eine gerade Zahl sein

Möglichkeiten des perfekten Matchings

Zusammenhang

Jedes perfekte Matching ist maximal, aber nicht jedes maximale Matching ist perfekt.

Ausgangssituation

• Behandelt werden ausschließlich Probleme von zwei Mengen
• Somit fällt die Betrachtung auf bipartite Graphen

Beispiel

Jugendherberge

Matchings für bipartite Graphen

Ein Graph G = (V,E) heißt bipartit, wenn sich die Knotenmenge V in zwei disjunkte Teilmengen V1 und V2 zerlegen lässt, sodass keine Kante von G zwei Knoten derselben Teilmenge miteinander verbindet. Ein bipartiter Graph mit maximal möglicher Kantenanzahl heißt vollständig bipartit und wird mit K_{r,s} bezeichnet, wenn r bzw. s die Anzahlen von V1 bzw. V2 sind.

• Alle Kanten verbinden nur jeweils einen Knoten aus V1 mit einem Knoten aus V2

Heiratssatz von Hall

• Name kommt vom früher verbreiteten Problem, eine Gruppe Frauen zu verheiraten
• aber nur, wenn es eine Gleichgroße Gruppe Männer gibt
• die sich mindestens für eine Frau der Gruppe interessieren

Grad einer Knotenmenge:

Es sei G = (V,E) ein Graph und U eine Teilmenge der Knoten E. Wir definieren den Grad von U als die Anzahl derjenigen Knoten von G, die mit einem Knoten aus U eine Kante bilden, und schreiben dafür d(U).

• für die Teilmenge U={Ursula, Karin} gilt d(U)=3, da drei Kanten zu einer anderen Teilmenge führen (Peter, Michael, Wolfgang)

Jetzt kann man den Satz von Hall verständlich formulieren:

Ein bipartiter Graph G = (V1 ∪ V2,E) besitzt genau dann ein perfektes Matching, wenn für alle Teilmengen U1 ⊆ V1 die Ungleichung d(U1) ≥ |U1| erfüllt ist.

• zur Untersuchung wird der Graph in zwei Teilmengen zerlegt
• V1={Ursula (1), Karin (2), Helga (3), Sabine (4)} und V2={Peter, Michael, Thomas, Wolfgang}
• eine Kante bedeutet, dass beide Personen aneinander interessiert sind
• jetzt müssen alle 15 Teilmengen von V1 überprüft werden, wir begrenzen uns aber nur auf Teilmengen die den Knoten 1 enthalten

   1 Setze M := \varnothing
   2 Wähle eine Kante e \in E, füge e M hinzu
   3 Entferne e und alle benachbarten Kanten aus E
   4 Falls E \neq \varnothing gehe zu 2, sonst STOPP: M ist maximal