From ac7015feefad911eb609c5ab032d234cb654ef4d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 13 Mar 2021 10:48:55 +0100 Subject: add new slides --- vorlesungen/slides/8/pfade/adjazenz.tex | 97 +++++++ vorlesungen/slides/8/pfade/beispiel.tex | 404 ++++++++++++++++++++++++++++++ vorlesungen/slides/8/pfade/gf.tex | 54 ++++ vorlesungen/slides/8/pfade/langepfade.tex | 59 +++++ 4 files changed, 614 insertions(+) create mode 100644 vorlesungen/slides/8/pfade/adjazenz.tex create mode 100644 vorlesungen/slides/8/pfade/beispiel.tex create mode 100644 vorlesungen/slides/8/pfade/gf.tex create mode 100644 vorlesungen/slides/8/pfade/langepfade.tex (limited to 'vorlesungen/slides/8/pfade') 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 -- cgit v1.2.1