Merge pull request #1 from AndreasFMueller/master

update

4 files changed, 614 insertions, 0 deletions

diff --git a/vorlesungen/slides/8/pfade/adjazenz.tex b/vorlesungen/slides/8/pfade/adjazenz.tex
new file mode 100644
index 0000000..f923262
--- /dev/null
+++ b/vorlesungen/slides/8/pfade/adjazenz.tex
@@ -0,0 +1,97 @@
+%
+% adjazenz.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+\definecolor{darkred}{rgb}{0.5,0,0}
+\begin{frame}[fragile]
+\newboolean{pfeilspitzen}
+\setboolean{pfeilspitzen}{true}
+\frametitle{Adjazenz-Matrix}
+
+\begin{columns}[t]
+\begin{column}{0.48\hsize}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+\def\r{2.2}
+\coordinate (A) at ({\r*cos(-54+0*72)},{\r*sin(-54+0*72)});
+\coordinate (C) at ({\r*cos(-54+1*72)},{\r*sin(-54+1*72)});
+\coordinate (D) at ({\r*cos(-54+2*72)},{\r*sin(-54+2*72)});
+\coordinate (B) at ({\r*cos(-54+3*72)},{\r*sin(-54+3*72)});
+\coordinate (E) at ({\r*cos(-54+4*72)},{\r*sin(-54+4*72)});
+
+\def\knoten#1#2{
+        \fill[color=white] #1 circle[radius=0.3];
+        \draw[line width=1pt] #1 circle[radius=0.3];
+        \node at #1 {$#2$};
+}
+
+\def\kante#1#2#3{
+        \ifthenelse{\boolean{pfeilspitzen}}{
+                \draw[->,line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm]
+                        #1 -- #2;
+        }{
+                \draw[line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm]
+                        #1 -- #2;
+        }
+%        \fill[color=white,opacity=0.7] ($0.5*#1+0.5*#2$) circle[radius=0.22];
+%        \node at ($0.5*#1+0.5*#2$) {$#3$};
+}
+
+\kante{(A)}{(E)}{1}
+\kante{(B)}{(C)}{2}
+\kante{(B)}{(D)}{13}
+\kante{(C)}{(A)}{3}
+\kante{(D)}{(C)}{6}
+\kante{(E)}{(B)}{5}
+\kante{(E)}{(D)}{6}
+
+\knoten{(A)}{1}
+\knoten{(B)}{2}
+\knoten{(C)}{3}
+\knoten{(D)}{4}
+\knoten{(E)}{5}
+
+\end{tikzpicture}
+\end{center}
+\end{column}
+\begin{column}{0.48\hsize}
+\[
+a_{{\color{darkred}i}{\color{blue}j}}
+=
+\begin{cases}
+1&\quad\text{\# Kanten von ${\color{blue}j}$ nach ${\color{darkred}i}$}\\
+0&\quad\text{sonst}
+\end{cases}
+\]
+\begin{center}
+\begin{tikzpicture}[>=latex]
+\node at (0,0) {$\displaystyle
+A=
+\begin{pmatrix}
+0&0&1&0&0\\
+0&0&0&0&1\\
+0&1&0&1&0\\
+0&1&0&0&1\\
+1&0&0&0&0
+\end{pmatrix}
+$};
+\def\s{0.54}
+\foreach \x in {1,...,5}{
+	\node[color=blue] at ({-0.71+(\x-1)*\s},1.4) {\tiny $\x$};
+}
+\node[color=blue] at ({-0.71+2*\s},1.7) {von};
+\def\r{0.48}
+\foreach \y in {1,...,5}{
+	\node[color=darkred] at ({-0.71+5*\s},{0.02+(3-\y)*\r}) {\tiny $\y$};
+}
+\node[color=darkred] at ({-0.4+5*\s},{0.02}) [rotate=90] {nach};
+\end{tikzpicture}
+\end{center}
+\end{column}
+\end{columns}
+
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/pfade/beispiel.tex b/vorlesungen/slides/8/pfade/beispiel.tex
new file mode 100644
index 0000000..43685f3
--- /dev/null
+++ b/vorlesungen/slides/8/pfade/beispiel.tex
@@ -0,0 +1,404 @@
+%
+% beispiel.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+\newboolean{pfeilspitzen}
+
+\def\knoten#1#2{
+        \fill[color=white] #1 circle[radius=0.3];
+        \draw[line width=1pt] #1 circle[radius=0.3];
+        \node at #1 {$#2$};
+}
+
+\def\kante#1#2#3{
+        \ifthenelse{\boolean{pfeilspitzen}}{
+                \draw[->,line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm]
+                        #1 -- #2;
+        }{
+                \draw[line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm]
+                        #1 -- #2;
+        }
+%        \fill[color=white,opacity=0.7] ($0.5*#1+0.5*#2$) circle[radius=0.22];
+%        \node at ($0.5*#1+0.5*#2$) {$#3$};
+}
+
+\begin{frame}
+\setboolean{pfeilspitzen}{true}
+\frametitle{Beispiel}
+\begin{columns}[t]
+\begin{column}{0.37\hsize}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+\def\r{2.2}
+\coordinate (A) at ({\r*cos(-54+0*72)},{\r*sin(-54+0*72)});
+\coordinate (C) at ({\r*cos(-54+1*72)},{\r*sin(-54+1*72)});
+\coordinate (D) at ({\r*cos(-54+2*72)},{\r*sin(-54+2*72)});
+\coordinate (B) at ({\r*cos(-54+3*72)},{\r*sin(-54+3*72)});
+\coordinate (E) at ({\r*cos(-54+4*72)},{\r*sin(-54+4*72)});
+
+\kante{(A)}{(E)}{1}
+\kante{(B)}{(C)}{2}
+\kante{(B)}{(D)}{13}
+\kante{(C)}{(A)}{3}
+\kante{(D)}{(C)}{6}
+\kante{(E)}{(B)}{5}
+\kante{(E)}{(D)}{6}
+
+\knoten{(A)}{1}
+\knoten{(B)}{2}
+\knoten{(C)}{3}
+\knoten{(D)}{4}
+\knoten{(E)}{5}
+
+\end{tikzpicture}
+\end{center}
+\end{column}
+\begin{column}{0.59\hsize}
+
+\only<1>{
+\begin{block}{Pfade der Länge 1}
+\[
+A=
+\begin{pmatrix}
+0&0&1&0&0\\
+0&0&0&0&1\\
+0&1&0&1&0\\
+0&1&0&0&1\\
+1&0&0&0&0
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<2>{
+\begin{block}{Pfade der Länge 2}
+\[
+A^2=\begin{pmatrix}
+   0 & 1 & 0 & 1 & 0 \\
+   1 & 0 & 0 & 0 & 0 \\
+   0 & 1 & 0 & 0 & 2 \\
+   1 & 0 & 0 & 0 & 1 \\
+   0 & 0 & 1 & 0 & 0
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<3>{
+\begin{block}{Pfade der Länge 3}
+\[
+A^3=\begin{pmatrix}
+   0 & 1 & 0 & 0 & 2 \\
+   0 & 0 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 0 \\
+   2 & 0 & 0 & 0 & 1 \\
+   1 & 0 & 1 & 0 & 0 \\
+   0 & 1 & 0 & 1 & 0
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<4>{
+\begin{block}{Pfade der Länge 4}
+\[
+A^4=\begin{pmatrix}
+   2%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 0 & 0 & 1 \\
+   0 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 1 & 0 \\
+   1 & 0 & 2%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 0 \\
+   0 & 1 & 1 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 \\
+   0 & 1 & 0 & 0 & 2%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<5>{
+\begin{block}{Pfade der Länge 5}
+\[
+A^5=\begin{pmatrix}
+   1 & 0 & 2 & 0 & 0 \\
+   0 & 1 & 0 & 0 & 2 \\
+   0 & 2 & 1 & 2 & 0 \\
+   0 & 2 & 0 & 1 & 2 \\
+   2 & 0 & 0 & 0 & 1
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<6>{
+\begin{block}{Pfade der Länge 6}
+\[
+A^6=\begin{pmatrix}
+   0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 2 & 1 & 2 & 0 \\
+   2 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 0 & 1 \\
+   0 & 3 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 1 & 4 \\
+   2 & 1 & 0 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 3 \\
+   1 & 0 & 2 & 0 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<7>{
+\begin{block}{Pfade der Länge 7}
+\[
+A^7=\begin{pmatrix}
+   0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 3 & 0 & 1 & 4 \\
+   1 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 2 & 0 & 0 \\
+   4 & 1 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 4 \\
+   3 & 0 & 2 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 1 \\
+   0 & 2 & 1 & 2 & 0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<8>{
+\begin{block}{Pfade der Länge 8}
+\[
+A^8=\begin{pmatrix}
+   4 & 1 & 0 & 0 & 4 \\
+   0 & 2 & 1 & 2 & 0 \\
+   4 & 0 & 4 & 0 & 1 \\
+   1 & 2 & 3 & 2 & 0 \\
+   0 & 3 & 0 & 1 & 4
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<9>{
+\begin{block}{Pfade der Länge 9}
+\[
+A^9=\begin{pmatrix}
+   4 & 0 & 4 & 0 & 1 \\
+   0 & 3 & 0 & 1 & 4 \\
+   1 & 4 & 4 & 4 & 0 \\
+   0 & 5 & 1 & 3 & 4 \\
+   4 & 1 & 0 & 0 & 4
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<10>{
+\begin{block}{Pfade der Länge 10}
+\[
+A^{10}=\begin{pmatrix}
+   1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 4 & 4 & 4 & 0 \\
+   4 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 0 & 0 & 4 \\
+   0 & 8 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 4 & 8 \\
+   4 & 4 & 0 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+& 8 \\
+   4 & 0 & 4 & 0 & 1%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<11>{
+\begin{block}{Pfade der Länge 15}
+\[
+A^{15}=\begin{pmatrix}
+    1 & 20 &  6 & 12 & 16 \\
+   12 &  1 &  8 &  0%
+\begin{picture}(0,0)
+\color{red}\put(-3,4){\circle{12}}
+\end{picture}%
+&  6 \\
+   16 & 18 &  1 &  6 & 32 \\
+   20 &  6 &  8 &  1 & 18 \\
+    6 &  8 & 12 &  8 &  1
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<12>{
+\begin{block}{Pfade der Länge 20}
+\[
+A^{20}=\begin{pmatrix}
+   33 & 56 &  8 & 24 & 80 \\
+   24 & 17 & 32 & 16 &  8 \\
+   80 & 32 & 33 &  8 & 80 \\
+   56 & 24 & 48 & 17 & 32 \\
+    8 & 48 & 24 & 32 & 33
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<13>{
+\begin{block}{Pfade der Länge 25}
+\[
+A^{25}=\begin{pmatrix}
+   193 & 120 &  74 &  40 & 240 \\
+    40 & 113 &  80 &  80 &  74 \\
+   240 & 114 & 193 &  74 & 160 \\
+   120 & 154 & 160 & 113 & 114 \\
+    74 & 160 &  40 &  80 & 193
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<14>{
+\begin{block}{Pfade der Länge 30}
+\[
+A^{30}=\begin{pmatrix}
+   673 & 348 & 460 & 188 & 560 \\
+   188 & 433 & 160 & 240 & 460 \\
+   560 & 648 & 673 & 460 & 536 \\
+   348 & 700 & 400 & 433 & 648 \\
+   460 & 400 & 188 & 160 & 673
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\only<15>{
+\begin{block}{Pfade der Länge 35}
+\[
+A^{35}=\begin{pmatrix}
+   1793%
+\color{red}\drawline(-23,-3)(-23,10)(2,10)(2,-3)(-23,-3)
+& 1644 & 1806 & 1108 & 1632 \\
+   1108 & 1233 &  536 &  560 & 1806 \\
+   1632 & 2914 & 1793%
+\color{red}\drawline(-23,-3)(-23,10)(2,10)(2,-3)(-23,-3)
+& 1806 & 2752 \\
+   1644 & 2366 & 1096 & 1233 & 2914 \\
+   1806 & 1096 & 1108 &  536 & 1793%
+\color{red}\drawline(-23,-3)(-23,10)(2,10)(2,-3)(-23,-3)
+\end{pmatrix}
+\]
+\end{block}
+}
+
+\end{column}
+\end{columns}
+\vbox to2cm{
+\vfill
+\only<3>{
+	\begin{block}{Kürzester Verbindung von 3 nach 2}
+	Der Weg 3---1---6---2 ist die kürzeste Verbindung von 3 nach 2
+	\end{block}
+}
+\only<4>{
+	\begin{block}{Kürzeste Zyklen}
+	Jeder Knoten liegt auf einem Zyklus der Länge 4,
+	dies sind die kürzesten Zyklen.
+	1, 3 und 5 liegen auf beiden Zyklen, 2 und 4 nur auf einem.
+	\end{block}
+}
+\only<6>{
+	\begin{block}{Zyklen der Länge 6}
+	{\em Keine} Zyklen der Länge 6
+	\end{block}
+}
+\only<7>{
+	\begin{block}{Zyklen der Länge 7}
+	{\em Keine} Zyklen der Länge 7
+	\end{block}
+}
+\only<10>{
+	\begin{block}{Zyklen der Länge 10}
+	Genau ein Zyklus der Länge 10
+	\end{block}
+}
+\only<11>{
+	\begin{block}{Verbindung von 4 nach 2}
+	{\em Keine} Verbindung der Länge 15 von 4 nach 2
+	\end{block}
+}
+\only<15>{
+	\begin{block}{Zyklen der Länge 35}
+	Es gibt 1793 Zyklen, die 1 enthalten, und sie enthalten alle auch 3 und 5
+	\end{block}
+}
+}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/pfade/gf.tex b/vorlesungen/slides/8/pfade/gf.tex
new file mode 100644
index 0000000..e89a1fb
--- /dev/null
+++ b/vorlesungen/slides/8/pfade/gf.tex
@@ -0,0 +1,54 @@
+%
+% gf.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}
+\definecolor{darkred}{rgb}{0.8,0,0}
+\frametitle{Erzeugende Funktion}
+Alle Weglängen zusammen:
+\[
+\uncover<7->{f({\color{darkred}t})=}
+\uncover<4->{E+}
+A
+\uncover<3->{{\color{darkred}t}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{2!}}
+A^2
+\uncover<3->{{\color{darkred}t^2}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{3!}}
+A^3
+\uncover<3->{{\color{darkred}t^3}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{4!}}
+A^4
+\uncover<3->{{\color{darkred}t^4}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{5!}}
+A^5
+\uncover<3->{{\color{darkred}t^5}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{6!}}
+A^6
+\uncover<3->{{\color{darkred}t^6}}
+\uncover<2->{+}
+\uncover<5->{\frac{1}{7!}}
+A^7
+\uncover<3->{{\color{darkred}t^7}}
+\dots
+\uncover<6->{= e^{A{\color{darkred}t}}}
+\]
+\uncover<4->{%
+heisst {\em\usebeamercolor[fg]{title} \only<5->{exponentiell} erzeugende Funktion}
+der Wege-Anzahlen}
+
+\begin{itemize}
+\item<8->
+Begriff der Entropie auf einem Graphen
+\item<9->
+Wahrscheinlichkeit, dass ein Zufallsspaziergänger auf einem Graphen an
+einem bestimmten Knoten vorbeikommt
+\end{itemize}
+
+\end{frame}
diff --git a/vorlesungen/slides/8/pfade/langepfade.tex b/vorlesungen/slides/8/pfade/langepfade.tex
new file mode 100644
index 0000000..8c0dd0d
--- /dev/null
+++ b/vorlesungen/slides/8/pfade/langepfade.tex
@@ -0,0 +1,59 @@
+%
+% langepfade.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+\definecolor{darkred}{rgb}{0.5,0,0}
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{frame}
+\frametitle{Wieviele Pfade der Länge $k$?}
+\begin{definition}
+Anzahl Pfade der Länge $k$ zwischen zwei Knoten
+\[
+a_{{\color{darkred}i}{\color{blue}j}}^{(k)} 
+=
+\#\{\text{Pfade der Länge $k$ von $\color{blue}j$ nach $\color{darkred}i$}\},
+\qquad
+A^{(k)}
+=
+\left(
+a_{{\color{darkred}i}{\color{blue}j}}^{(k)}
+\right)
+\]
+\end{definition}
+\uncover<2->{
+{\usebeamercolor[fg]{title}Spezialfall:} $A^{(1)}=A$.
+}
+
+\uncover<3->{
+\begin{block}{Rekursionsformel}
+\vspace{-25pt}
+\begin{align*}
+a_{{\color{darkred}i}{\color{blue}{\color{blue}j}}}^{(k)}
+&\uncover<4->{=
+\sum_{{\color{darkgreen}l}=1}^n
+\#\{\text{Pfade der Länge $1$ von $\color{darkgreen}l$ nach $\color{darkred}i$}\}}
+\\[-11pt]
+&\uncover<4->{\qquad\qquad\times
+\#\{\text{Pfade der Länge $k-1$ von $\color{blue}j$ nach $\color{darkgreen}l$}\}}
+\\
+&\uncover<5->{=
+\sum_{{\color{darkgreen}l}=1}^n
+a_{{\color{darkred}i}{\color{darkgreen}l}}^{(1)}
+\cdot
+a_{{\color{darkgreen}l}{\color{blue}j}}^{(k-1)}}
+\\
+\uncover<6->{
+\Rightarrow\qquad
+A^{(k)}}
+&\uncover<6->{=
+A\;A^{(k-1)}}
+\uncover<7->{
+\qquad\Rightarrow\qquad
+A^{(k)} = A^k}
+\end{align*}
+\end{block} }
+
+\end{frame}
+\egroup