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

Definition

Matching

Ein Matching von G 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

Maximales Matching

Ein maximales Matching von G ist ein Matching von G, dem keine weitere Kante mehr hinzugefügt werden kann. 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 \frac2n Kanten beinhalten

Perfektes Matching

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 24 Teilmengen von V1 überprüft werden, wir begrenzen uns aber nur auf Teilmengen die den Knoten 1 enthalten