Matching-Probleme

Aus ProgrammingWiki
Archivierte Version vom 2015-11-21T16:03:49+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

Heiratssatz

Maximal-Matching-Algorithmen

Greedy-Matching-Algorithmus

Verbessernde Wege

Möglichkeiten des perfekten Matchings

Zuordnungsproblem

Quellen