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.
* ein Knoten kann nur zu einer Matchingkante gehören
* zwei Matchingkanten dürfen niemals adjazent sein

[[Bild:1_2_graph.PNG]]
<br>
<popup name="Matching">[[Bild:1_2_matching.png]]</popup>
<br>
;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
<br>
<popup name="Maximales Matching">Hier nur ein Beispiel eines maximalen Matching:<br>[[Bild:1_2_max_matching.PNG‎]]</popup><br>
;Sind alle Knoten von G von einem Matching überdeckt, so handelt es sich um ein perfektes Matching.
* damit ist die maximale Mächtigkeit eines Matching erreicht
* Anzahl $n$ der Knoten muss dafür eine gerade Zahl sein
<br>
<popup name="Perfektes Matching">[[Bild:1_2_perf_matching.png]]</popup>

==Zusammenhang==
Jedes perfekte Matching ist maximal, aber nicht jedes maximale Matching ist perfekt.
==Ausgangssituation==
* Behandelt werden ausschließlich Probleme von zwei Mengen
* Somit fällt die Betrachtung auf bipartite Graphen
==Beispiel==
Jugendherberge
=Matchings für bipartite Graphen=
;Ein Graph $G = (V,E)$ heißt bipartit, wenn sich die Knotenmenge $V$ in zwei disjunkte Teilmengen $V1$ und $V2$ zerlegen lässt, sodass keine Kante von $G$ zwei Knoten derselben Teilmenge miteinander verbindet. Ein bipartiter Graph mit maximal möglicher Kantenanzahl heißt vollständig bipartit und wird mit $K_{r,s}$ bezeichnet, wenn $r$ bzw. $s$ die Anzahlen von $V1$ bzw. $V2$ sind.
*Alle Kanten verbinden nur jeweils einen Knoten aus $V1$ mit einem Knoten aus $V2$
==Heiratssatz von Hall==
*Name kommt vom früher verbreiteten Problem, eine Gruppe Frauen zu verheiraten
*aber nur, wenn es eine Gleichgroße Gruppe Männer gibt
*die sich mindestens für eine Frau der Gruppe interessieren
<br>
<strong>Grad einer Knotenmenge:</strong>
;Es sei $G = (V,E)$ ein Graph und $U$ eine Teilmenge der Knoten $E$. Wir definieren den Grad von $U$ als die Anzahl derjenigen Knoten von $G$, die mit einem Knoten aus $U$ eine Kante bilden, und schreiben dafür $d(U)$.
* für die Teilmenge $U=${$Ursula, Karin$} gilt $d(U)=3$, da drei Kanten zu einer anderen Teilmenge führen (Peter, Michael, Wolfgang)
<br>
;Jetzt kann man den Satz von Hall verständlich formulieren:
;Ein bipartiter Graph $G = (V1 ∪ V2,E)$ besitzt genau dann ein perfektes Matching, wenn für alle Teilmengen $U1 ⊆ V1$ die Ungleichung $d(U1) ≥ |U1|$ erfüllt ist.


[[Bild:2_1_graph.PNG]]
{| class="wikitable"
|-
! Wahl !! Ursula !! Karin !! Helga !! Sabine 
|-
| 1 || Peter|| Peter || Thomas || Wolfgang
|-
| 2 || Michael|| Michael || Wolfgang || Michael
|-
| 3 || Wolfgang|| - || - || - 
|}
{| class="wikitable"
|-
! Wahl !! Peter !! Michael !! Thomas !! Wolfgang 
|-
| 1 || Karin|| Sabine|| Helga || Ursula
|-
| 2 || Ursula|| Karin || - || Helga 
|-
| 3 || - || Ursula|| - || Sabine
|}

<popup name="mögliches perfektes Matching">[[Bild:2_1_mögl_perf_matching.PNG]]</popup>

=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