Matching-Probleme

Aus ProgrammingWiki
Archivierte Version vom 2015-11-22T10:51:55+00:00. Aktuelle Version

Inhaltsverzeichnis

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

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

1_2_graph.PNG

Matching

1_2_matching.png


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


Maximales Matching

Hier nur ein Beispiel eines maximalen Matching:
1_2_max_matching.PNG‎


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


Perfektes Matching

1_2_perf_matching.png

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.


2_1_graph.PNG

WahlUrsulaKarinHelgaSabine
1PeterPeterThomasWolfgang
2MichaelMichaelWolfgangMichael
3Wolfgang---
WahlPeterMichaelThomasWolfgang
1KarinSabineHelgaUrsula
2UrsulaKarin-Helga
3-Ursula-Sabine
mögliches perfektes Matching

2_1_mögl_perf_matching.PNG

Maximal-Matching-Algorithmen

Greedy-Matching-Algorithmus

Verbessernde Wege

Möglichkeiten des perfekten Matchings

Zuordnungsproblem

Quellen