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
===Effizienz===
* Matchingprobleme werden in Polynomialzeit gelöst

==Definition==
;Ein Graph $G=(V,E)$ heißt bipartiter Graph, wenn man $V$ in zwei disjunkte Mengen $U$ und $W$ zerlegen kann, so dass alle Kanten zwischen $U$ und $W$ verlaufen.
===Matching===
;Ein Matching von $G=(V,E)$ 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
    [[Hinweis]] Das Stellen und Bearbeiten von Matchingproblemen setzt keinesfalls einen Bipartiten Graphen voraus, bietet sich jedoch an. 
    Einem nicht bipartiten Graphen, für den ein Matching existiert, können wir dennoch einen bipartiten Kontext "unterstellen".
[[Bild:1_2_graph.PNG]][[Bild:Flikkes_NoMatching1.png]]
<br>
<popup name="Matching">[[Bild:1_2_matching.png]][[Bild:Flikkes_Matching1.png]]</popup>
<br>

===Maximales Matching===
;Ein Matching $M$ von $G$ ist maximal, wenn jedes [[Hinzufügen]] einer weiteren Kante zu $M$ das Matching zerstört. 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 $\frac{n}{2}$ Kanten beinhalten
* Ein maximales Matching wird auch "nicht erweiterbar" genannt
<br>
    $M$ ist maximal, wenn: $\nexists e \in E \setminus M \colon e\cup M$ ist Matching
<popup name="Maximales Matching">Hier nur ein Beispiel eines maximalen Matching:<br>[[Bild:1_2_max_matching.PNG‎]][[Bild:Flikkes_MaxMatching1.png]]</popup><br>
;Es ist wichtig den Unterschied zwischen einem erweiterten- und einem völlig anderen Matching zu erkennen

===Perfektes Matching===
;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>
    $M$ ist perfekt wenn: $\forall e(v,w) \in M \colon \{ v,w\} \subseteq V$
<popup name="Perfektes Matching">[[Bild:1_2_perf_matching.png]]</popup>
====Möglichkeiten des perfekten Matchings====

==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>
<strong>Jetzt kann man den Satz von Hall verständlich formulieren:</strong>
;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.
*zur Untersuchung wird der Graph in zwei Teilmengen zerlegt
* $V1=${$Ursula (1), Karin (2), Helga (3), Sabine (4)$} und $V2=${$Peter, Michael, Thomas, Wolfgang$}
* eine Kante bedeutet, dass beide Personen aneinander interessiert sind
* jetzt müssen alle 15 Teilmengen von $V1$ überprüft werden, wir begrenzen uns aber nur auf Teilmengen die den Knoten 1 enthalten
<br><center>
{|
|d({1})|| = 3 ≥ 1<br>
|-
|d({1, 2})|| = 3 ≥ 2<br>
|-
|d({1, 3})|| = 4 ≥ 2<br>
|-
|d({1, 4})|| = 3 ≥ 2<br>
|-
|d({1, 2, 3})|| = 4 ≥ 3<br>
|-
|d({1, 2, 4})|| = 3 ≥ 3<br>
|-
|d({1, 3, 4})|| = 4 ≥ 3<br>
|-
|d({1, 2, 3, 4, })|| = 4 ≥ 4<br>
|}</center>
* wenn kein Widerspruch gefunden wird, besagt der Heiratssatz, dass ein perfektes Matching existiert
[[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>
* nur für kleine Interessengraphen

=Maximal-Matching-Algorithmen=
==Greedy-Matching-Algorithmus==
Es handelt sich um einen Algorithmus, in welchem, gemäß dem Konzept des Greedy-Verfahrens, am Ende eines Schritts stets der aktuell bestmögliche Folgeschritt gewählt wird. Der Vorteil liegt in der Schnelligkeit, mit der Ergebnisse produziert werden, welche allerdings nicht immer optimal sind.
===Ausgangssituation===
Gegeben sei ein Ausgangsgraph $G = (V,E)$ und ein Matching $M$. 
Zum Schluss soll $M$ ein maximales Matching sein.
===Protokoll===
    1 Setze $M := \varnothing$
    2 Wähle eine Kante $e \in E$, füge $e$ $M$ hinzu
    3 Entferne $e$ und alle benachbarten Kanten aus $E$
    4 Falls $E \neq \varnothing$ gehe zu 2, sonst STOPP: $M$ ist maximal

==Verbessernde Wege (Verbessernde Pfade)==
;Mit verbessernden Wegen kann ein gefundenes maximales Matching optimiert werden.
    Gibt es für einen Graphen $G$ mit einem Matching $M$ einen Weg $P(v_0, v_1 , v_2, ..., v_n)\colon \{ v_0,v_n\} \cap M = \emptyset$,
    mit ungerader Knotenanzahl, wobei jede zweite Kante $\subseteq M$, so nennt man $P$ einen
    ($M$-)verbessernden Weg
;Existiert ein verbessernder Weg, so kann dieser invertiert und die Zahl der Matchingkanten um eins erhöht werden.
;Ein verbessernder Weg $P$ wird invertiert, indem Matching-und Nicht-Matchingkanten ausgetauscht werden (swap).
===Ausgangssituation===
;Gegeben sei ein Graph $G$ mit einem maximalen Matching $M$. $M$ soll zu einem maximalen Matching mit maximal möglicher Kantenanzahl werden ([[Maximum-Matching]]).

===Protokoll===
    $M:=$maximales Matching
    while $G$ enthält $M$-verbessernden Weg do
        entferne Matchingkanten $E$ mit $E  \subseteq P,M$ aus $M$
        $M:= P \cup M$
    endwhile

=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
*http://matheplanet.com/default3.html?call=article.php?sid=1070&ref=https%3A%2F%2Fwww.google.de%2F
*http://algo.rwth-aachen.de/Lehre/SS11/VEA/Skripte/matchings.pdf
*https://www.tu-ilmenau.de/fileadmin/public/iti/Lehre/EAII/WS11/Kapitel2-Matchings.pdf