add munkres files

10 files changed, 255 insertions, 144 deletions

diff --git a/buch/papers/munkres/figures/Netzwerkdarstellung.png b/buch/papers/munkres/figures/Netzwerkdarstellung.png
new file mode 100644
index 0000000..6c20bf4
--- /dev/null
+++ b/buch/papers/munkres/figures/Netzwerkdarstellung.png
diff --git a/buch/papers/munkres/figures/beispiel_munkres.png b/buch/papers/munkres/figures/beispiel_munkres.png
new file mode 100644
index 0000000..2303708
--- /dev/null
+++ b/buch/papers/munkres/figures/beispiel_munkres.png
diff --git a/buch/papers/munkres/figures/bipartiter_graph.png b/buch/papers/munkres/figures/bipartiter_graph.png
new file mode 100644
index 0000000..87c164c
--- /dev/null
+++ b/buch/papers/munkres/figures/bipartiter_graph.png
diff --git a/buch/papers/munkres/main.tex b/buch/papers/munkres/main.tex
index 4dd20fa..8915a3d 100644
--- a/buch/papers/munkres/main.tex
+++ b/buch/papers/munkres/main.tex
@@ -3,34 +3,18 @@
 %
 % (c) 2020 Hochschule Rapperswil
 %
-\chapter{Thema\label{chapter:munkres}}
-\lhead{Thema}
+\chapter{Munkres-Algorithmus\label{chapter:munkres}}
+\lhead{Munkres-Algorithmus}
 \begin{refsection}
-\chapterauthor{Hans Muster}
+\chapterauthor{Marc Kühne}
 
-Ein paar Hinweise für die korrekte Formatierung des Textes
-\begin{itemize}
-\item
-Absätze werden gebildet, indem man eine Leerzeile einfügt.
-Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet.
-\item
-Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende
-Optionen werden gelöscht. 
-Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen.
-\item
-Beginnen Sie jeden Satz auf einer neuen Zeile. 
-Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen
-in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt 
-anzuwenden.
-\item 
-Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren
-Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern.
-\end{itemize}
 
 \input{papers/munkres/teil0.tex}
 \input{papers/munkres/teil1.tex}
 \input{papers/munkres/teil2.tex}
 \input{papers/munkres/teil3.tex}
+\input{papers/munkres/teil4.tex}
+\input{papers/munkres/teil5.tex}
 
 \printbibliography[heading=subbibliography]
 \end{refsection}
diff --git a/buch/papers/munkres/teil0.tex b/buch/papers/munkres/teil0.tex
index de522c7..1ef0538 100644
--- a/buch/papers/munkres/teil0.tex
+++ b/buch/papers/munkres/teil0.tex
@@ -3,20 +3,19 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Teil 0\label{munkres:section:teil0}}
-\rhead{Teil 0}
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua \cite{munkres:bibtex}.
-At vero eos et accusam et justo duo dolores et ea rebum.
-Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum
-dolor sit amet.
+\section{Geschichte\label{munkres:section:teil0}}
+\rhead{Geschichte}
+Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht.
+Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus
+weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker
+basierte: Dénes Kőnig und Jenő Egerváry.
+James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest,
+dass der Algorithmus (stark) polynomiell ist.
+Seitdem ist der Algorithmus auch als Kuhn-Munkres oder
+Munkres-Zuordnungsalgorithmus bekannt.
+Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$,
+später wurde zudem festgestellt, dass er modifiziert werden kann,
+um eine  $O(n^3)$-Laufzeit zu erreichen.
 
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua.
-At vero eos et accusam et justo duo dolores et ea rebum.  Stet clita
-kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit
-amet.
 
 
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index f4f5e39..7cbbbfd 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,53 +3,19 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Teil 1
+\section{Was ist die ungarische Methode?
 \label{munkres:section:teil1}}
 \rhead{Problemstellung}
-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
-\begin{equation}
-\int_a^b x^2\, dx
-=
-\left[ \frac13 x^3 \right]_a^b
-=
-\frac{b^3-a^3}3.
-\label{munkres:equation1}
-\end{equation}
-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?
-
-\subsection{De finibus bonorum et malorum
-\label{munkres:subsection:finibus}}
-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 \eqref{000tempmlate:equation1}.
-
-Et harum quidem rerum facilis est et expedita distinctio
-\ref{munkres:section:loesung}.
-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
-\ref{munkres:section:folgerung}.
-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.
-
-
+Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
+in polynomieller Zeit löst.
+\begin{itemize}
+\item
+Polynom = vielgliedrig
+\end{itemize}
+Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
+wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert.
+Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst
+werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen.
+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. 
diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex
index 23536b9..29db8d7 100644
--- a/buch/papers/munkres/teil2.tex
+++ b/buch/papers/munkres/teil2.tex
@@ -3,38 +3,86 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Teil 2 
+\section{Das Zuordnungsproblem
 \label{munkres:section:teil2}}
-\rhead{Teil 2}
-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?
-
-\subsection{De finibus bonorum et malorum
+\rhead{Das Zuordnungsproblem}
+Das (lineare) Zuordnungsproblem ist ein diskretes Optimierungsproblem aus
+der Graphentheorie.
+Es handelt sich um einen Spezialfall eines maximalen Matchings
+minimalen Gewichtes in einem bipartiten, gewichteten Graphen
+
+Vereinfacht gesagt sind Zuordnungsprobleme spezielle Transportprobleme.
+Der Unterschied zu klassischen Transportproblemen liegen darin,
+dass hier nicht Mengen möglichst kostenminimal von einem zum anderen
+Ort transportiert werden sollen, sondern es geht um die kostenminimale
+Zuordnung von z.~B.~Personen, oder Bau-Materialien auf bestimmte
+Orte, Stellen oder Aufgaben.
+Dabei sind alle Angebots- und Bedarfsmenge gleich 1 
+\begin{equation}
+a_{i}=b_{j}=1
+\end{equation}
+
+\subsection{Zuordnungsproblem in Netzwerkdarstellung
+\label{munkres:subsection:bonorum}}
+
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
+\caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.}
+\label{munkres:Vr2}
+\end{figure}
+
+\subsection{Matrix Formulierung
+\label{munkres:subsection:bonorum}}
+In der Matrixformulierung ist eine nicht-negative $n\times n$-Matrix
+gegeben, wobei das Element in der $i$-ten Zeile und $j$-ten Spalte
+die Kosten für die Zuweisung des $j$-ten Jobs an den $i$-ten Arbeiter
+darstellt.
+Wir müssen eine Zuordnung der Jobs zu den Arbeitern finden, so dass
+jeder Job einem Arbeiter zugewiesen wird und jeder Arbeiter einen
+Job zugewiesen bekommt, so dass die Gesamtkosten der Zuordnung
+minimal sind.
+Dies kann als Permutation der Zeilen und Spalten einer Kostenmatrix
+$C$ ausgedrückt werden, um die Spur einer Matrix zu minimieren:
+\begin{equation}
+\min(L,R)Tr (LCR)
+\end{equation}
+wobei $L$ und $R$ Permutationsmatrizen sind.
+Wenn das Ziel ist, die Zuordnung zu finden, die die maximalen Kosten
+ergibt, kann das Problem durch Negieren der Kostenmatrix $C$ gelöst
+werden.
+
+\subsection{Suche der optimalen Lösung
+\label{munkres:subsection:bonorum}}
+Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht
+in jeder Zeile und jeder Spalte der Matrix genau ein Element, das
+zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird
+auch als Transversale der Matrix bezeichnet.
+Deshalb kann die Problemstellung auch anders formuliert werden: Man
+ordne die Zeilen- oder die Spaltenvektoren so um, dass die Summe
+der Elemente in der Hauptdiagonale maximal wird.
+Hieraus wird sofort ersichtlich, dass es in einer 
+$n\times n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen-
+bzw.~Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen
+gibt, also $n!$.
+Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale
+Lösung durch Berechnung aller Möglichkeiten zu finden.
+Schon bei einer $10\times 10$-Matrix gibt es nahezu 3,63 Millionen (3.628.800)
+zu berücksichtigender Permutationen.
+
+\subsection{Formulierung Bipartiter Graph
 \label{munkres:subsection:bonorum}}
-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.
+Der Algorithmus ist einfacher zu beschreiben, wenn wir das Problem
+anhand eines bipartiten Graphen formulieren.
+Wir haben einen vollständigen zweistufigen Graphen $G=(S,T;E)$ mit
+$n$ Arbeiter-Eckpunkten ($S$) und $n$ Job-Scheitelpunkte ($T$), und
+jede Kante hat einen nichtnegativen Preis $c(i,j)$.
+Wir wollen ein perfektes Matching mit minimalen Gesamtkosten finden.
 
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/bipartiter_graph}
+\caption{$K_{3,3}$ vollständig bipartiter Graph mit 3 Knoten pro Teilmenge.}
+\label{munkres:Vr2}
+\end{figure}
 
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.
 
diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex
new file mode 100644
index 0000000..3d76743
--- /dev/null
+++ b/buch/papers/munkres/teil4.tex
@@ -0,0 +1,36 @@
+%
+% teil4.tex -- Beispiel-File für Teil 4
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Matrix-Interpretation
+\label{munkres:section:teil4}}
+\rhead{Matrix-Interpretation}
+Gegeben ist die quadratische Matrix $C=(c_{ij})$ der Grösse $n\times n$.
+Ohne Beschränkung der Allgemeinheit werden eine Zuordnung $j
+\rightarrow  s_j$, $j = 1, \dots, n$ mit minimaler Gesamtsumme
+$\sum_{j=1}^{n}c_{s_j,j}$ gesucht, wobei die $s_j$ eine Permutation
+von $\{1,\ldots ,n\}$ sind.
+Soll die Summe maximiert werden, dann kann $C$ durch $-C$ ersetzt werden.
+Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung
+unter bestimmten Änderungen der Matrix nicht ändert, sondern nur
+der Optimalwert.
+Diese Änderungen sind durch Knotenpotentiale bzw.~duale Variablen 
+\begin{equation}
+u_1 u_2,{\dots}, u_n
+\end{equation}
+
+für die Zeilen und 
+
+\begin{equation}v_1,v_2,\dots,v_n \end{equation} fuer die Spalten angegeben.
+Die modifizierte Matrix hat dann die Komponenten $\tilde{c}_{i,j}
+= c_{ij} - u_j - v_j$.
+
+In der Summe über jede kantenmaximale Zuordnung kommt jedes
+Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion
+eine Konstante ist.
+Sind die Einträge von $C$ nichtnegativ, und sind alle Knotenpotentiale
+ebenfalls nichtnegativ, so nennt man die modifizierte Matrix \~{C}
+auch eine Reduktion.
+Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf
+den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren.
diff --git a/buch/papers/munkres/teil5.tex b/buch/papers/munkres/teil5.tex
new file mode 100644
index 0000000..f8138f4
--- /dev/null
+++ b/buch/papers/munkres/teil5.tex
@@ -0,0 +1,14 @@
+%
+% teil5.tex -- Beispiel-File für Teil 5
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Ungarische Methode anhand eines Beispiels
+\label{munkres:section:teil5}}
+\rhead{Ungarische Methode anhand eines Beispiels}
+\begin{figure}
+\centering
+\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres}
+\caption{Händisches Beispiel des Munkres Algorithmus.}
+\label{munkres:Vr2}
+\end{figure}