aboutsummaryrefslogtreecommitdiffstats
path: root/vorlesungen/slides/8/pfade
diff options
context:
space:
mode:
authorLordMcFungus <mceagle117@gmail.com>2021-03-22 18:05:11 +0100
committerGitHub <noreply@github.com>2021-03-22 18:05:11 +0100
commit76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7 (patch)
tree11b2d41955ee4bfa0ae5873307c143f6b4d55d26 /vorlesungen/slides/8/pfade
parentmore chapter structure (diff)
parentadd title image (diff)
downloadSeminarMatrizen-76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7.tar.gz
SeminarMatrizen-76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7.zip
Merge pull request #1 from AndreasFMueller/master
update
Diffstat (limited to 'vorlesungen/slides/8/pfade')
-rw-r--r--vorlesungen/slides/8/pfade/adjazenz.tex97
-rw-r--r--vorlesungen/slides/8/pfade/beispiel.tex404
-rw-r--r--vorlesungen/slides/8/pfade/gf.tex54
-rw-r--r--vorlesungen/slides/8/pfade/langepfade.tex59
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