Matching-Probleme

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

Ausgangssituation

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

Beispiel

Jugendherberge

Maximales Matching

Perfektes Matching

Zusammenhang

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

Matchings für bipartite Graphen

Heiratssatz

Maximal-Matching-Algorithmen

Greedy-Matching-Algorithmus

Verbessernde Wege

Möglichkeiten des perfekten Matchings

Zuordnungsproblem

Quellen