add munkres files

1 files changed, 94 insertions, 30 deletions

diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index b67ad74..806cd83 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -3,38 +3,102 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Teil 3
+\section{Der Algorithmus in Form von bipartiten Graphen
 \label{munkres:section:teil3}}
-\rhead{Teil 3}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit
-aspernatur aut odit aut fugit, sed quia consequuntur magni dolores
-eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam
-est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci
-velit, sed quia non numquam eius modi tempora incidunt ut labore
-et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima
-veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam,
-nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure
-reprehenderit qui in ea voluptate velit esse quam nihil molestiae
-consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla
-pariatur?
+\rhead{Der Algorithmus in Form von bipartiten Graphen}
+Mit der ungarischen Methode können also lineare Optimierungsprobleme
+gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen
+entstehen.
 
-\subsection{De finibus bonorum et malorum
+Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen
+so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der
+Gesamtgewinn maximiert werden kann.
+
+Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen
+zwischen den Elementen zweier Mengen.
+Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» 
+
+\subsection{Beweis, dass der Algorithmus Fortschritte macht
+\label{munkres:subsection:malorum}}
+Wir müssen zeigen, dass der Algorithmus, solange das Matching nicht
+die maximal mögliche Größe hat, immer in der Lage ist, Fortschritte
+zu machen --- das heißt, entweder die Anzahl der übereinstimmenden
+Kanten zu erhöhen oder mindestens eine Kante zu straffen.
+Es genügt zu zeigen, dass bei jedem Schritt mindestens eine der
+folgenden Bedingungen erfüllt ist:
+
+\begin{itemize}
+\item
+$M$ die maximal mögliche Größe.
+\item
+$Gy$ enthält einen Erweiterungspfad.
+\item
+$G$ enthält einen losen Pfad: einen Pfad von einem Knoten in $Rs$
+zu einem Knoten in $T$ / $Z$ die aus einer beliebigen Anzahl von
+festen Kanten, gefolgt von einer einzelnen losen Kante, besteht.
+Die freie Kante einer freien Bahn ist also $Z$ (beinhaltet $T$),
+so garantiert es, dass Delta gut definiert ist.
+\end{itemize}
+Wenn $M$ die maximal mögliche Größe hat, sind wir natürlich fertig.
+Andernfalls muss es nach Berges Lemma im zugrundeliegenden Graphen
+$G$ einen Augmentierungspfad $P$ in Bezug auf $M$ geben.
+Dieser Pfad darf jedoch nicht in $G_y$ existieren: Obwohl jede
+geradzahlige Kante in $P$ durch die Definition von $M$ fest ist,
+können ungeradzahlige Kanten lose sein und in $G_y$ fehlen.
+Ein Endpunkt von $P$ liegt in $R_{S}$, der andere in $R_T$; w.l.o.g.,
+nehmen Sie an, es beginnt in $R_{S}$.
+Wenn jede Kante von $P$ dicht ist, dann bleibt sie ein augmentierender
+Pfad in $G_y$ und wir sind fertig.
+Andernfalls sei $uv$ die erste lose Kante auf $P$.
+Wenn $v$ kein Element von $Z$ ist, dann haben wir einen losen Pfad
+gefunden und sind fertig.
+Andernfalls ist $v$ von irgendeinem anderen Pfad $Q$ aus festen
+Kanten von einem Knoten in $R_{S}$ erreichbar.
+Sei $P_{v}$ der Teilpfad von $P$, der bei $v$ beginnt und bis zum
+Ende reicht, und sei $P'$ der Pfad, der gebildet wird, indem man
+entlang $Q$ gebildet wird, bis ein Scheitelpunkt auf $P_{v}$ erreicht
+wird, und dann weiter bis zum Ende von $P_{v}$.
+Beachten Sie, dass $P'$ ein erweiternder Pfad in $G$ mit mindestens
+einer losen Kante weniger als $P$ ist.
+$P$ kann durch $P'$ ersetzt und dieser Argumentationsprozess iteriert
+werden (formal, unter Verwendung von Induktion auf die Anzahl der
+losen Kanten), bis entweder ein erweiternder Pfad in $G_y$ oder ein
+losender Pfad in $G$ gefunden wird.
+
+\subsection{Beweis, dass die Anpassung des Potentials $y$ $M$ unverändert lässt
 \label{munkres:subsection:malorum}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis
-est et expedita distinctio. Nam libero tempore, cum soluta nobis
-est eligendi optio cumque nihil impedit quo minus id quod maxime
-placeat facere possimus, omnis voluptas assumenda est, omnis dolor
-repellendus. Temporibus autem quibusdam et aut officiis debitis aut
-rerum necessitatibus saepe eveniet ut et voluptates repudiandae
-sint et molestiae non recusandae. Itaque earum rerum hic tenetur a
-sapiente delectus, ut aut reiciendis voluptatibus maiores alias
-consequatur aut perferendis doloribus asperiores repellat.
+Um zu zeigen, dass jede Kante in $M$ nach der Anpassung von $y$
+erhalten bleibt, genügt es zu zeigen, dass für eine beliebige Kante
+in $M$ entweder beide Endpunkte oder keiner von ihnen in $Z$ liegen.
+Zu diesem Zweck sei $vu$ eine Kante in $M$ von $T$ nach $S$.
+Es ist leicht zu sehen, dass wenn $v$ in $Z$ ist, dann muss auch
+$u$ in $Z$ sein, da jede Kante in $M$ dicht ist.
+Nehmen wir nun an, dass $u$ kein Element von $Z$ und auch $v$ kein
+Element von $Z$ ist.
+$u$ selbst kann nicht in $R_{S}$ sein, da es der Endpunkt einer
+angepassten Kante ist, also muss es einen gerichteten Pfad von engen
+Kanten von einem Knoten in $R_{S}$ zu $u$ geben.
+Dieser Pfad muss $v$ vermeiden, da es per Annahme nicht in $Z$ ist,
+also ist der Knoten, der $u$ in diesem Pfad unmittelbar vorausgeht,
+ein anderer Knoten $v$ (ein Element von $T$) und $v$ ein Element
+von $u$ ist eine enge Kante von $T$ nach $S$ und ist somit in $M$.
+Aber dann enthält $M$ zwei Kanten, die den Knoten $u$ teilen, was
+der Tatsache widerspricht, dass $M$ ein Matching ist.
+Jede Kante in $M$ hat also entweder beide Endpunkte oder keinen
+Endpunkt in $Z$.
 
+\subsection{Beweis, dass $y$ ein Potential bleibt
+\label{munkres:subsection:malorum}}
+Um zu zeigen, dass y nach der Anpassung ein Potenzial bleibt, genügt
+es zu zeigen, dass keine Kante ihr Gesamtpotenzial über ihre Kosten
+hinaus erhöht.
+Dies ist für Kanten in $M$ bereits durch den vorangegangenen Absatz
+bewiesen.
+Man betrachtet also eine beliebige Kante $uv$ von $S$ nach $T$.
+Wenn $y(u)$ erhöht wird um $\Delta$, dann wird entweder $v\in
+\mathbb{Z}_n$ in diesem Fall wird $y(v)$ verringert um $\Delta$,
+wobei das Gesamtpotenzial der Kante unverändert bleibt, oder $v\in
+T\setminus Z$, wobei die Definition von $\Delta$ garantiert, dass
+$y(u)+y(v)+\Delta \le c(u,v)$
+Also $y$ bleibt ein Potential.