Matching-Probleme

Aus ProgrammingWiki
Archivierte Version vom 2015-11-10T09:52:14+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.

Maximales Matching

Perfektes Matching

Zusammenhang

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

Matchings für bipartite Graphen

Möglichkeiten des perfekten Matchings

Zuordnungsproblem

Quellen