Matching-Probleme

Aus ProgrammingWiki
Archivierte Version vom 2015-11-21T14:36:56+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.

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