Matching-Probleme

Wiki-Quelltext dieser Seite.

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.

<popup name="Lösung">
[[Bild:Ghx8 ;_LetzteUbungC.png|200px]]
</popup> 
==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=
*https://books.google.de/books?id=2qkkBAAAQBAJ&pg=PA45&dq=matching+probleme&hl=de&sa=X&ved=0CCIQ6AEwAWoVChMI_K-g08SFyQIVob5yCh19wwwa#v=onepage&q=matching%20probleme&f=false
*https://books.google.de/books?id=Rj0lBAAAQBAJ&pg=PA292&dq=matching+probleme&hl=de&sa=X&ved=0CD0Q6AEwBWoVChMI_K-g08SFyQIVob5yCh19wwwa#v=onepage&q=matching%20probleme&f=false