Matching-Probleme

Aus ProgrammingWiki
Archivierte Version vom 2015-11-10T09:44:53+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

Ausgangssituation

  • Behandelt werden ausschließlich Probleme von zwei Mengen

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.

Matchings für bipartite Graphen

Möglichkeiten des perfekten Matchings

Zuordnungsproblem

Quellen