From 972eba4c4cb38eb330bd053500e627085a3f4328 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 12 Mar 2021 17:27:08 +0100 Subject: add new slides --- vorlesungen/slides/8/Makefile.inc | 11 ++++ vorlesungen/slides/8/chapter.tex | 7 +++ vorlesungen/slides/8/dgraph.tex | 100 ++++++++++++++++++++++++++++++++ vorlesungen/slides/8/graph.tex | 117 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 235 insertions(+) create mode 100644 vorlesungen/slides/8/Makefile.inc create mode 100644 vorlesungen/slides/8/chapter.tex create mode 100644 vorlesungen/slides/8/dgraph.tex create mode 100644 vorlesungen/slides/8/graph.tex (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc new file mode 100644 index 0000000..e8c7502 --- /dev/null +++ b/vorlesungen/slides/8/Makefile.inc @@ -0,0 +1,11 @@ + +# +# Makefile.inc -- additional depencencies +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +chapter8 = \ + ../slides/8/dgraph.tex \ + ../slides/8/graph.tex \ + ../slides/8/chapter.tex + diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex new file mode 100644 index 0000000..761ea63 --- /dev/null +++ b/vorlesungen/slides/8/chapter.tex @@ -0,0 +1,7 @@ +% +% chapter.tex +% +% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi +% +\folie{8/graph.tex} +\folie{8/dgraph.tex} diff --git a/vorlesungen/slides/8/dgraph.tex b/vorlesungen/slides/8/dgraph.tex new file mode 100644 index 0000000..6b5864a --- /dev/null +++ b/vorlesungen/slides/8/dgraph.tex @@ -0,0 +1,100 @@ +% +% dgraph.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame} +\frametitle{Gerichteter Graph} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.44\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\r{2.4} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\uncover<3->{ + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); + \draw[color=white,line width=5pt] (B) -- (D); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); +} + +\uncover<2->{ + \draw (A) circle[radius=0.2]; + \draw (B) circle[radius=0.2]; + \draw (C) circle[radius=0.2]; + \draw (D) circle[radius=0.2]; + \draw (E) circle[radius=0.2]; + + \node at (A) {$1$}; + \node at (B) {$2$}; + \node at (C) {$3$}; + \node at (D) {$4$}; + \node at (E) {$5$}; +} +\node at (0,0) {$G$}; + +\uncover<3->{ + \node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 1$}; + \node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 2$}; + \node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; + \node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$}; + \node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$}; + \node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$}; + \node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; +} + +\uncover<7->{ + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm,color=red] + (E) to[out=-18,in=-126,distance=2cm] (E); +} + +\uncover<9->{ + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm,color=darkgreen] + (D) to[out=120,in=-120] (C); +} + +\end{tikzpicture} +\end{center} +\end{column} +\begin{column}{0.52\textwidth} +\begin{block}{Definition} +Ein gerichteter Graph $G=(V,E)$ ist +\begin{enumerate} +\item<2-> Eine Menge $V$ von Knoten (Vertizes) +$V=\{v_1,v_2,\dots\}$ +\item<3-> +Eine Menge $E$ von gerichteten Kanten +(Edges) +\[ +E\subset \{ (v_1,v_2)\;|\; v_i\in V\} +\] +\end{enumerate} +\end{block} +\vspace{-30pt} +\uncover<6->{% +\begin{block}{Achtung} +\begin{itemize} +\item<6-> Kanten sind {\em geordnete} Paare +\uncover<7->{$\Rightarrow$ {\color{red}Schleifen} sind möglich} +\item<8-> Kanten sind immer ``Einbahnstrassen'' +\item<9-> {\color{darkgreen}Gegenrichtung explizit angeben} +\end{itemize} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/graph.tex b/vorlesungen/slides/8/graph.tex new file mode 100644 index 0000000..32150af --- /dev/null +++ b/vorlesungen/slides/8/graph.tex @@ -0,0 +1,117 @@ +% +% graph.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Graph} +\vspace{-18pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\r{2.4} + +\begin{scope} +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\uncover<3->{ + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); + \draw[color=white,line width=5pt] (B) -- (D); + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); +} + +\uncover<2->{ + \draw (A) circle[radius=0.2]; + \draw (B) circle[radius=0.2]; + \draw (C) circle[radius=0.2]; + \draw (D) circle[radius=0.2]; + \draw (E) circle[radius=0.2]; + + \node at (A) {$1$}; + \node at (B) {$2$}; + \node at (C) {$3$}; + \node at (D) {$4$}; + \node at (E) {$5$}; +} +\node at (0,0) {$G$}; + +\uncover<3->{ + \node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) + [above right] {$\scriptstyle 1$}; + \node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) + [above left] {$\scriptstyle 2$}; + \node at ($0.5*(C)+0.5*(D)+(0.05,0)$) + [left] {$\scriptstyle 3$}; + \node at ($0.5*(D)+0.5*(E)$) + [below] {$\scriptstyle 4$}; + \node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) + [below right] {$\scriptstyle 5$}; + \node at ($0.6*(A)+0.4*(C)$) + [above] {$\scriptstyle 6$}; + \node at ($0.4*(B)+0.6*(D)$) + [left] {$\scriptstyle 7$}; +} + +\uncover<8->{ + \draw[shorten >= 0.2cm,shorten <= 0.2cm] + (E) to[out=-18,in=-126,distance=2cm] (E); + + \draw[color=red,line width=4pt] ($(E)+(-0.5,-0.5)+(0,-0.5)$) + -- ($(E)+(0.5,0.5)+(0,-0.5)$); + \draw[color=red,line width=4pt] ($(E)+(-0.5,0.5)+(0,-0.5)$) + -- ($(E)+(0.5,-0.5)+(0,-0.5)$); +} + +\end{scope} + +\end{tikzpicture} +\end{center} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Definition} +Ein Graph $G=(V,E)$ ist +\begin{enumerate} +\item<2-> +Eine Menge $V$ von Knoten (Vertizes): +$V=\{v_1,v_2,\dots\}$ +\item<3-> +Eine Menge $E$ von Kanten (Edges): +\[ +E\subset +\left\{ e = \{v_1,v_2\}\;\left|\; \begin{minipage}{1.3cm}\raggedright +$v_i\in V$\\ +$v_1\ne v_2$ +\end{minipage} +\right. +\right\} +\] +\end{enumerate} +\end{block} +\vspace{-20pt} +\uncover<5->{% +\begin{block}{Achtung:} +\begin{itemize} +\item<6-> Kanten sind Mengen +\uncover<7->{$\Rightarrow$ zwei verschiedene Knoten} +\uncover<8->{$\Rightarrow$ Keine Schleifen} +\item<9-> Kanten sind ungerichtet, keine ``Einbahnstrassen'' +\end{itemize} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup -- cgit v1.2.1 From 0a0f140762a5be23e2475eceecf51d6cb6f84399 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 12 Mar 2021 21:13:21 +0100 Subject: add new slides --- vorlesungen/slides/8/Makefile.inc | 2 + vorlesungen/slides/8/chapter.tex | 2 + vorlesungen/slides/8/grad.tex | 84 ++++++++++++++++++++++++ vorlesungen/slides/8/inzidenz.tex | 131 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 219 insertions(+) create mode 100644 vorlesungen/slides/8/grad.tex create mode 100644 vorlesungen/slides/8/inzidenz.tex (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index e8c7502..903fce2 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -7,5 +7,7 @@ chapter8 = \ ../slides/8/dgraph.tex \ ../slides/8/graph.tex \ + ../slides/8/grad.tex \ + ../slides/8/inzidenz.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index 761ea63..23d9aac 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -5,3 +5,5 @@ % \folie{8/graph.tex} \folie{8/dgraph.tex} +\folie{8/grad.tex} +\folie{8/inzidenz.tex} diff --git a/vorlesungen/slides/8/grad.tex b/vorlesungen/slides/8/grad.tex new file mode 100644 index 0000000..a232828 --- /dev/null +++ b/vorlesungen/slides/8/grad.tex @@ -0,0 +1,84 @@ +% +% grad.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Grad} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); +%\draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +%\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 1$}; +%\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 2$}; +%\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; +%\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$}; +%\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$}; +%\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$}; +%\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; + +\end{tikzpicture} +\end{center} +\begin{block}{Definition} +Der Grad +$\deg v$ +eines Knotens $v\in V$ ist die Anzahl der Kanten mit Ende in $v$ +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Gradmatrix} +Diagonalmatrix mit $d_{ii}=\deg v_i$ +\[ +D(G) += +\begin{pmatrix} +3&0&0&0&0\\ +0&3&0&0&0\\ +0&0&3&0&0\\ +0&0&0&2&0\\ +0&0&0&0&1 +\end{pmatrix} +\] +\end{block} +\begin{block}{Satz} +Die Summe der Grade ist gerade: +\[ +\sum_{i=1}^n\deg v_i = \operatorname{Spur} D(G) \equiv 0 \mod 2 +\] +\end{block} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex new file mode 100644 index 0000000..5911593 --- /dev/null +++ b/vorlesungen/slides/8/inzidenz.tex @@ -0,0 +1,131 @@ +% +% inzidenz.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\frametitle{Inzidenz- und Adjazenzmatrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[color=darkgreen,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); +%\draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + +\fill[color=red!20] (B) circle[radius=0.2]; + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 1$}; +\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 2$}; +\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; +\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 4$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 5$}; +\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 6$}; + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\begin{block}{Definition} +\vspace{-15pt} +\begin{align*} +B(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante $j$ endet in Knoten $i$}\\ +A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$} +\end{align*} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\dy{0.48} +\def\dx{0.54} + + +\begin{scope} +\fill[color=red!20] (1.8,1.8) rectangle (4.75,2.15); +\fill[color=darkgreen!40,opacity=0.5] (4.46,0.36) rectangle (4.79,2.65); +\foreach \y in {1,...,5}{ + \node[color=gray] at (5.3,{2.45-(\y-1)*\dy}) {\tiny $\y$}; +} +\foreach \y in {1,...,6}{ + \node[color=gray] at ({1.92+(\y-1)*\dx},2.90) {\tiny $\y$}; +} +\draw[color=gray] (1.8,2.75) -- (4.7,2.75); +\draw[color=gray] (5.2,2.55) -- (5.2,0.45); +\node[color=gray] at ({1.92+2.5*\dx},3.1) {\tiny Kanten}; +\node[color=gray] at (5.3,{2.45-2*\dy}) [above,rotate=-90] {\tiny Knoten}; +\end{scope} + +\begin{scope} +\fill[color=red!20] (1.8,-1.16) rectangle (4.25,-0.77); +\fill[color=red!20] (2.3,-2.6) rectangle (2.63,-0.29); +\foreach \y in {1,...,5}{ + \node[color=gray] at (4.7,{-0.5-(\y-1)*\dy}) {\tiny $\y$}; + \node[color=gray] at ({1.92+(\y-1)*\dx},-0.1) {\tiny $\y$}; +} +\draw[color=gray] (1.8,-0.22) -- (4.2,-0.22); +\draw[color=gray] (4.6,-0.4) -- (4.6,-2.55); +\node[color=gray] at ({1.92+2*\dx},0.1) {\tiny Knoten}; +\node[color=gray] at (4.7,{-0.5-2*\dy}) [above,rotate=-90] {\tiny Knoten}; +\end{scope} + +\node (0,0) [right] {$\displaystyle +\begin{aligned} +B(G) +&= +\begin{pmatrix} +1&0&0&1&1&0\\ +1&1&0&0&0&1\\ +0&1&1&0&1&0\\ +0&0&1&0&0&0\\ +0&0&0&1&0&1 +\end{pmatrix} +\\[12pt] +A(G) +&= +\begin{pmatrix} +0&1&1&0&1\\ +1&0&1&1&0\\ +1&1&0&1&0\\ +0&1&1&0&0\\ +1&0&0&0&0 +\end{pmatrix} +\end{aligned}$}; + +\end{tikzpicture} +\end{center} +\end{column} +\end{columns} +\end{frame} +\egroup -- cgit v1.2.1 From 33baa215192f04f27d7c389c83e7f2fd9f481abd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 12 Mar 2021 22:15:39 +0100 Subject: new slides --- vorlesungen/slides/8/Makefile.inc | 1 + vorlesungen/slides/8/chapter.tex | 1 + vorlesungen/slides/8/inzidenzd.tex | 145 +++++++++++++++++++++++++++++++++++++ 3 files changed, 147 insertions(+) create mode 100644 vorlesungen/slides/8/inzidenzd.tex (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index 903fce2..68e2e27 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -9,5 +9,6 @@ chapter8 = \ ../slides/8/graph.tex \ ../slides/8/grad.tex \ ../slides/8/inzidenz.tex \ + ../slides/8/inzidenzd.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index 23d9aac..6ac3e98 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -7,3 +7,4 @@ \folie{8/dgraph.tex} \folie{8/grad.tex} \folie{8/inzidenz.tex} +\folie{8/inzidenzd.tex} diff --git a/vorlesungen/slides/8/inzidenzd.tex b/vorlesungen/slides/8/inzidenzd.tex new file mode 100644 index 0000000..19da619 --- /dev/null +++ b/vorlesungen/slides/8/inzidenzd.tex @@ -0,0 +1,145 @@ +% +% inzidenzd.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\frametitle{Inzidenz- und Adjazenz-Matrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.40\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm,color=darkgreen] (B) -- (D); + +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + +\draw (A) circle[radius=0.2]; +\fill[color=red!20] (B) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 1$}; +\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 2$}; +\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$}; +\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$}; +\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; + +\end{tikzpicture} +\end{center} +\vspace{-15pt} +\begin{block}{Definition} +\vspace{-20pt} +\begin{align*} +B(G)_{ij}&=-1&&\Leftrightarrow&&\text{Kante $j$ von $i$}\\ +B(G)_{kj}&=+1&&\Leftrightarrow&&\text{Kante $j$ nach $k$}\\ +A(G)_{ij}&=\pm 1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$} +\end{align*} +\end{block} +\end{column} +\begin{column}{0.58\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\dx{0.84} +\def\dy{0.48} + +\begin{scope}[xshift=4cm,yshift=3cm] +\fill[color=red!20] +({-0.67-(7-1)*\dx-0.4},{-0.38-(2-1)*\dy-0.2}) +rectangle +({-0.67-(7-7)*\dx+0.2},{-0.38-(2-1)*\dy+0.16}); +\fill[color=darkgreen!40,opacity=0.5] +({-0.67-(7-7)*\dx-0.4},{-0.38-(5-1)*\dy-0.2}) +rectangle +({-0.67-(7-7)*\dx+0.2},{-0.38-(1-1)*\dy+0.16}); +%\draw (0,0) circle[radius=0.05]; +\foreach \x in {1,...,7}{ + \node[color=gray] at ({-0.67-(7-\x)*\dx},0.0) {\tiny $\x$}; +} +\draw[color=gray] ({-0.72-6*\dx},-0.1) -- (-0.6,-0.1); +\foreach \y in {1,...,5}{ + \node[color=gray] at ({0},{-0.38-(\y-1)*\dy}) {\tiny $\y$}; +} +\draw[color=gray] (-0.1,-0.28) -- (-0.1,-2.4); +\node[color=gray] at ({-0.67-(7-4)*\dx},0.04) [above] {\tiny Kanten}; +\end{scope} + +\begin{scope}[xshift=2.32cm,yshift=-0.24cm] +%\draw (0,0) circle[radius=0.05]; +\fill[color=red!20] +({-0.67-(5-1)*\dx-0.4},{-0.38-(2-1)*\dy-0.2}) +rectangle +({-0.67-(5-5)*\dx+0.2},{-0.38-(2-1)*\dy+0.16}); +\fill[color=red!20] +({-0.67-(5-2)*\dx-0.4},{-0.38-(5-1)*\dy-0.2}) +rectangle +({-0.67-(5-2)*\dx+0.2},{-0.38-(1-1)*\dy+0.16}); +\foreach \x in {1,...,5}{ + \node[color=gray] at ({-0.67-(5-\x)*\dx},0.0) {\tiny $\x$}; +} +\draw[color=gray] ({-0.72-4*\dx},-0.1) -- (-0.6,-0.1); +\foreach \y in {1,...,5}{ + \node[color=gray] at ({0},{-0.38-(\y-1)*\dy}) {\tiny $\y$}; +} +\draw[color=gray] (-0.1,-0.28) -- (-0.1,-2.4); +\node[color=gray] at ({-0.67-(5-3)*\dx},0.04) [above] {\tiny Knoten}; +\node[color=gray] at ({0.00},{-0.38-(3-1)*\dy}) + [above,rotate=-90] {\tiny Knoten}; +\end{scope} + +\node at (0,0) {$\displaystyle +\begin{aligned} +B(G) +&= +\begin{pmatrix*}[r] +-1& 0& 0& 0& 1&-1& 0\\ + 1&-1& 0& 0& 0& 0&-1\\ + 0& 1&-1& 0& 0& 1& 0\\ + 0& 0& 1&-1& 0& 0& 1\\ + 0& 0& 0& 1&-1& 0& 0 +\end{pmatrix*} +\\[20pt] +A(G) +&= +\begin{pmatrix*}[r] + 0&-1&-1& 0&-1\\ +-1& 0&-1&-1& 0\\ +-1&-1& 0&-1& 0\\ + 0&-1&-1& 0&-1\\ +-1& 0& 0&-1& 0 +\end{pmatrix*} +\end{aligned}$}; +\end{tikzpicture} +\end{center} +\end{column} +\end{columns} +\end{frame} -- cgit v1.2.1 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/Makefile.inc | 11 + vorlesungen/slides/8/chapter.tex | 18 + vorlesungen/slides/8/diffusion.tex | 89 +++ vorlesungen/slides/8/floyd-warshall/burgerking.png | Bin 0 -> 121512 bytes vorlesungen/slides/8/floyd-warshall/fw.tex | 680 +++++++++++++++++++++ vorlesungen/slides/8/floyd-warshall/iteration.tex | 14 + vorlesungen/slides/8/floyd-warshall/macdonalds.png | Bin 0 -> 129601 bytes vorlesungen/slides/8/floyd-warshall/problem.tex | 146 +++++ vorlesungen/slides/8/floyd-warshall/rekursion.tex | 108 ++++ vorlesungen/slides/8/floyd-warshall/starbucks.png | Bin 0 -> 160194 bytes vorlesungen/slides/8/floyd-warshall/wege.tex | 26 + .../slides/8/floyd-warshall/wegiteration.tex | 13 + vorlesungen/slides/8/floyd-warshall/wegweiser.jpg | Bin 0 -> 431961 bytes vorlesungen/slides/8/inzidenzd.tex | 24 +- vorlesungen/slides/8/laplace.tex | 213 +++++++ 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 ++ 19 files changed, 1945 insertions(+), 11 deletions(-) create mode 100644 vorlesungen/slides/8/diffusion.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/burgerking.png create mode 100644 vorlesungen/slides/8/floyd-warshall/fw.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/iteration.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/macdonalds.png create mode 100644 vorlesungen/slides/8/floyd-warshall/problem.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/rekursion.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/starbucks.png create mode 100644 vorlesungen/slides/8/floyd-warshall/wege.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/wegiteration.tex create mode 100644 vorlesungen/slides/8/floyd-warshall/wegweiser.jpg create mode 100644 vorlesungen/slides/8/laplace.tex 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') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index 68e2e27..0a20f88 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -10,5 +10,16 @@ chapter8 = \ ../slides/8/grad.tex \ ../slides/8/inzidenz.tex \ ../slides/8/inzidenzd.tex \ + ../slides/8/diffusion.tex \ + ../slides/8/laplace.tex \ + ../slides/8/pfade/adjazenz.tex \ + ../slides/8/pfade/langepfade.tex \ + ../slides/8/pfade/beispiel.tex \ + ../slides/8/pfade/gf.tex \ + ../slides/8/floyd-warshall/problem.tex \ + ../slides/8/floyd-warshall/rekursion.tex \ + ../slides/8/floyd-warshall/iteration.tex \ + ../slides/8/floyd-warshall/wegiteration.tex \ + ../slides/8/floyd-warshall/wege.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index 6ac3e98..bd1c18f 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -8,3 +8,21 @@ \folie{8/grad.tex} \folie{8/inzidenz.tex} \folie{8/inzidenzd.tex} +\folie{8/diffusion.tex} +\folie{8/laplace.tex} + +\folie{8/pfade/adjazenz.tex} +\folie{8/pfade/langepfade.tex} +\folie{8/pfade/beispiel.tex} +\folie{8/pfade/gf.tex} + +\folie{8/floyd-warshall/problem.tex} +\folie{8/floyd-warshall/rekursion.tex} +\folie{8/floyd-warshall/iteration.tex} +\folie{8/floyd-warshall/wegiteration.tex} +\folie{8/floyd-warshall/wege.tex} + + + + + diff --git a/vorlesungen/slides/8/diffusion.tex b/vorlesungen/slides/8/diffusion.tex new file mode 100644 index 0000000..0d07a27 --- /dev/null +++ b/vorlesungen/slides/8/diffusion.tex @@ -0,0 +1,89 @@ +% +% diffusion.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\frametitle{Diffusion} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (B) -- (D); + +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (A) -- (B); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (B) -- (C); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (C) -- (D); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (D) -- (E); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (E) -- (A); + +\draw[->,color=darkgreen,line width=8pt,shorten <= 0.25cm,shorten >= 0cm] + (A) -- (E); +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (A) -- (B); +\draw[->,color=darkgreen,line width=4pt,shorten <= 0.25cm,shorten >= 0.15cm] + (A) -- (C); +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (B) -- (C); +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (C) -- (D); +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (D) -- (E); +\draw[->,color=darkgreen,line width=4pt,shorten <= 0.25cm,shorten >= 0.15cm] + (B) -- (D); + +\fill[color=red] (A) circle[radius=0.3]; +\fill[color=red!50] (B) circle[radius=0.3]; +\fill[color=white] (C) circle[radius=0.3]; +\fill[color=blue!50] (D) circle[radius=0.3]; +\fill[color=blue] (E) circle[radius=0.3]; + +\draw (A) circle[radius=0.3]; +\draw (B) circle[radius=0.3]; +\draw (C) circle[radius=0.3]; +\draw (D) circle[radius=0.3]; +\draw (E) circle[radius=0.3]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\begin{block}{Knotenfunktion} +$f\colon V\to \mathbb{R}$ +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Fluss} +Je grösser die Differenz zu den Nachbarn, desto grösser der Fluss in +den Knoten: +\begin{align*} +\frac{df(v)}{dt} +&= +\kappa \sum_{\text{$v'$ Nachbar von $v$}} (f(v')-f(v)) +\end{align*} +``Wärmeleitungsgleichung'' +\end{block} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/burgerking.png b/vorlesungen/slides/8/floyd-warshall/burgerking.png new file mode 100644 index 0000000..cf4211d Binary files /dev/null and b/vorlesungen/slides/8/floyd-warshall/burgerking.png differ diff --git a/vorlesungen/slides/8/floyd-warshall/fw.tex b/vorlesungen/slides/8/floyd-warshall/fw.tex new file mode 100644 index 0000000..99929fb --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/fw.tex @@ -0,0 +1,680 @@ +% +% fw.tex -- Durchführung des Floyd-Warshall Algorithmus +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup + +\definecolor{wegelb}{rgb}{1,0.6,0} +\definecolor{weghell}{rgb}{1,0.9,0.6} +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\begin{columns}[t] +\begin{column}{0.44\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#3{ + \fill[color=#3] #1 circle[radius=0.3]; + \draw[line width=1pt] #1 circle[radius=0.3]; + \node at #1 {$#2$}; +} + +\def\kante#1#2#3{ + \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$}; +} + +% Wege über 1 +% 3--1--5 +\only<4>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E); +} + +% Wege über 2 +% 5--2--3 +\only<6>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C); +} +% 5--2--4 +\only<7>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(D); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(D); +} + +% Wege über 3 +% 2--3--1 +\only<9>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A); +} +% 2--3--5 +\only<10>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E); +} +% 4--3--1 +\only<11>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A); +} +% 4--3--5 +\only<12>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E); +} +% 5--3--1 +\only<13>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C)--(A); +} +% 5--3--5 +\only<14>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C)--(A)--(E); +} + +% Wege über 4 +% 2--4--1 +\only<16>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A); +} +% 2--4--3 +\only<17>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C); +} +% 2--4--5 +\only<18>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C)--(A)--(E); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A)--(E); +} +% 5--4--1 +\only<19>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C)--(A); +} +% 5--4--3 +\only<20>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C); +} +% 5--4--5 +\only<21>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C)--(A)--(E); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C)--(A)--(E); +} +% 1--5--1 +\only<23>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B)--(C)--(A); +} +% 1--5--2 +\only<24>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B); +} +% 1--5--3 +\only<25>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B)--(C); +} +% 1--5--4 +\only<26>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(D); +} +% 2--5--1 +\only<27>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A); +} +% 2--5--2 +\only<28>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(B); +} +% 2--5--3 +\only<29>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C); +} +% 2--5--4 +\only<30>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(D); +} +% 3--5--1 +\only<31>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (C)--(A); +} +% 3--5--2 +\only<32>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(B); +} +% 3--5--3 +\only<33>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(B)--(C); +} +% 3--5--4 +\only<34>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(D); +} +% 4--5--1 +\only<35>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (D)--(C)--(A); +} +% 4--5--2 +\only<36>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(B); +} +% 4--5--3 +\only<37>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (D)--(C); +} +% 4--5--4 +\only<38>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D); +} + + +\uncover<40>{ + \draw[->,color=red!50,line width=7pt] + (B)--(C)--(A)--(E)--(D); +} + +\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} + +\only<1>{ + \knoten{(A)}{}{white} + \knoten{(B)}{}{white} + \knoten{(C)}{}{white} + \knoten{(D)}{}{white} + \knoten{(E)}{}{white} +} + +\only<2->{ + \knoten{(A)}{1}{white} + \knoten{(B)}{2}{white} + \knoten{(C)}{3}{white} + \knoten{(D)}{4}{white} + \knoten{(E)}{5}{white} +} + +\only<4>{ + \knoten{(A)}{1}{darkgreen!50} +} +\only<6-7>{ + \knoten{(B)}{2}{darkgreen!50} +} +\only<9-14>{ + \knoten{(C)}{3}{darkgreen!50} +} +\only<16-21>{ + \knoten{(D)}{4}{darkgreen!50} +} +\only<23-38>{ + \knoten{(E)}{5}{darkgreen!50} +} + +\end{tikzpicture} +\end{center} +\begin{block}{Aufgabe} +Finde den kürzesten Weg von 2 nach 4 +\end{block} +\end{column} +\begin{column}{0.5\hsize} +\begin{center} +\begin{tikzpicture}[>=latex,scale=0.8] + +\def\punkt#1#2{ + ({#2-0.5},{0.5-(#1)}) +} +\def\punktoff#1#2{ + ({#2-0.7},{0.7-(#1)}) +} +\def\feld#1#2#3{ + \ifthenelse{\boolean{wegweiser}}{ + \fill[color=white] + ({#2-1},{1-#1}) rectangle ({#2-0.45},{0.45-#1}); + \node at \punktoff{#1}{#2} {$#3$}; + }{ + \fill[color=white] + ({#2-1},{1-#1}) rectangle ({#2},{-#1}); + \node at \punkt{#1}{#2} {$#3$}; + } +} +\def\verbindung#1#2#3{ + \draw[->,line width=5pt,color=red!20,shorten >= 0.2cm,shorten <= 0.2cm] + \punkt{#1}{#2}--\punkt{#2}{#3}; + \node at (5,-5.5) [left] {$#1\rightsquigarrow #2\rightsquigarrow #3$\strut}; +} +\def\Infty{{}} +\def\wegweiser#1#2#3{ + \ifthenelse{\boolean{wegweiser}}{ + \ifnum #2 = #3 + \fill[color=weghell] + ({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1}); + \else + \fill[color=wegelb] + ({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1}); + \fi + \node at ({#2-0.25},{0.25-#1}) {\tiny #3}; + }{} +} + +% direkte Wege +\uncover<3->{ + \feld{1}{1}{\Infty} + \feld{1}{2}{\Infty} + \feld{1}{3}{\Infty} + \feld{1}{4}{\Infty} + \feld{1}{5}{1} + \wegweiser{1}{5}{5} + + \feld{2}{1}{\Infty} + \feld{2}{2}{\Infty} + \feld{2}{3}{2} + \wegweiser{2}{3}{3} + \feld{2}{4}{13} + \wegweiser{2}{4}{4} + \feld{2}{5}{\Infty} + + \feld{3}{1}{3} + \wegweiser{3}{1}{1} + \feld{3}{2}{\Infty} + \feld{3}{3}{\Infty} + \feld{3}{4}{\Infty} + \feld{3}{5}{\Infty} + + \feld{4}{1}{\Infty} + \feld{4}{2}{\Infty} + \feld{4}{3}{6} + \wegweiser{4}{3}{3} + \feld{4}{4}{\Infty} + \feld{4}{5}{\Infty} + + \feld{5}{1}{\Infty} + \feld{5}{2}{5} + \wegweiser{5}{2}{2} + \feld{5}{3}{\Infty} + \feld{5}{4}{6} + \wegweiser{5}{4}{4} + \feld{5}{5}{\Infty} +} + +\uncover<3-3>{ + \node at (-0.8,-5.5) [right] {direkte Verbindungen}; +} + +\uncover<4-4>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $1$:\strut}; +} + +% Wege über 1 +% 3-1-5 +\uncover<4>{ + \verbindung{3}{1}{5} + \feld{3}{5}{\color{red}4} + \wegweiser{3}{5}{1} +} +\uncover<5->{ + \feld{3}{5}{4} + \wegweiser{3}{5}{1} +} + +\uncover<6-7>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $2$:\strut}; +} + +% Wege über 2 +% 5-2-3 +\uncover<6>{ + \verbindung{5}{2}{3} + \feld{5}{3}{\color{red}7} + \wegweiser{5}{3}{2} +} +\uncover<7->{ + \feld{5}{3}{7} + \wegweiser{5}{3}{2} +} +% 5-2-4 +\uncover<7>{ + \verbindung{5}{2}{4} + \feld{5}{4}{\color{blue}6} +} + +\uncover<9-14>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $3$:\strut}; +} + +% Wege über 3 +% 2-3-1 +\uncover<9>{ + \verbindung{2}{3}{1} + \feld{2}{1}{\color{red}5} + \wegweiser{2}{1}{3} +} +\uncover<10->{ + \feld{2}{1}{5} + \wegweiser{2}{1}{3} +} +% 2-3-5 +\uncover<10>{ + \verbindung{2}{3}{5} + \feld{2}{5}{\color{red}6} + \wegweiser{2}{5}{3} +} +\uncover<11->{ + \feld{2}{5}{6} + \wegweiser{2}{5}{3} +} +% 4-3-1 +\uncover<11>{ + \verbindung{4}{3}{1} + \feld{4}{1}{\color{red}9} + \wegweiser{4}{1}{3} +} +\uncover<12->{ + \feld{4}{1}{9} + \wegweiser{4}{1}{3} +} +% 4-3-5 +\uncover<12>{ + \verbindung{4}{3}{5} + \feld{4}{5}{\color{red}10} + \wegweiser{4}{5}{3} +} +\uncover<13->{ + \feld{4}{5}{10} + \wegweiser{4}{5}{3} +} +% 5-3-1 +\uncover<13>{ + \verbindung{5}{3}{1} + \feld{5}{1}{\color{red}10} + \wegweiser{5}{1}{2} +} +\uncover<14->{ + \feld{5}{1}{10} + \wegweiser{5}{1}{2} +} +% 5-3-5 +\uncover<14>{ + \verbindung{5}{3}{5} + \feld{5}{5}{\color{red}11} + \wegweiser{5}{5}{2} +} +\uncover<15->{ + \feld{5}{5}{11} + \wegweiser{5}{5}{2} +} + +\uncover<16-21>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $4$:\strut}; +} + +% Wege über 4 +% 2-4-1 +\uncover<16>{ + \verbindung{2}{4}{1} + \feld{2}{1}{\color{blue}5} +} +% 2-4-3 +\uncover<17>{ + \verbindung{2}{4}{3} + \feld{2}{3}{\color{blue}2} +} +% 2-4-5 +\uncover<18>{ + \verbindung{2}{4}{5} + \feld{2}{5}{\color{blue}6} +} +% 5-4-1 +\uncover<19>{ + \verbindung{5}{4}{1} + \feld{5}{1}{\color{blue}10} +} +% 5-4-3 +\uncover<20>{ + \verbindung{5}{4}{3} + \feld{5}{3}{\color{blue}7} +} +% 5-4-5 +\uncover<21>{ + \verbindung{5}{4}{5} + \feld{5}{5}{\color{blue}11} +} + +% Wege über 5 +\uncover<23-38>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $5$:\strut}; +} + +% Wege über 5 +% 1-5-1 +\uncover<23>{ + \verbindung{1}{5}{1} + \feld{1}{1}{\color{red}11} + \wegweiser{1}{1}{5} +} +\uncover<24->{ + \feld{1}{1}{11} + \wegweiser{1}{1}{5} +} +% 1-5-2 +\uncover<24>{ + \verbindung{1}{5}{2} + \feld{1}{2}{\color{red}6} + \wegweiser{1}{2}{5} +} +\uncover<25->{ + \feld{1}{2}{6} + \wegweiser{1}{2}{5} +} +% 1-5-3 +\uncover<25>{ + \verbindung{1}{5}{3} + \feld{1}{3}{\color{red}8} + \wegweiser{1}{3}{5} +} +\uncover<26->{ + \feld{1}{3}{8} + \wegweiser{1}{3}{5} +} +% 1-5-4 +\uncover<26>{ + \verbindung{1}{5}{4} + \feld{1}{4}{\color{red}7} + \wegweiser{1}{4}{5} +} +\uncover<27->{ + \feld{1}{4}{7} + \wegweiser{1}{4}{5} +} +% 2-5-1 +\uncover<27>{ + \verbindung{2}{5}{1} + \feld{2}{1}{\color{blue}5} +} +% 2-5-2 +\uncover<28>{ + \verbindung{2}{5}{2} + \feld{2}{2}{\color{red}11} + \wegweiser{2}{2}{3} +} +\uncover<29->{ + \feld{2}{2}{11} + \wegweiser{2}{2}{3} +} +% 2-5-3 +\uncover<29>{ + \verbindung{2}{5}{3} + \feld{2}{3}{\color{blue}2} +} +% 2-5-4 +\uncover<30>{ + \verbindung{2}{5}{4} + \feld{2}{4}{\color{red}12} + \wegweiser{2}{4}{3} +} +\uncover<31->{ + \feld{2}{4}{12} + \wegweiser{2}{4}{3} +} +% 3-5-1 +\uncover<31>{ + \verbindung{3}{5}{1} + \feld{3}{1}{\color{blue}3} +} +% 3-5-2 +\uncover<32>{ + \verbindung{3}{5}{2} + \feld{3}{2}{\color{red}9} + \wegweiser{3}{2}{1} +} +\uncover<33->{ + \feld{3}{2}{9} + \wegweiser{3}{2}{1} +} +% 3-5-3 +\uncover<33>{ + \verbindung{3}{5}{3} + \feld{3}{3}{\color{red}11} + \wegweiser{3}{3}{1} +} +\uncover<34->{ + \feld{3}{3}{11} + \wegweiser{3}{3}{1} +} +% 3-5-4 +\uncover<34>{ + \verbindung{3}{5}{4} + \feld{3}{4}{\color{red}10} + \wegweiser{3}{4}{1} +} +\uncover<35->{ + \feld{3}{4}{10} + \wegweiser{3}{4}{1} +} +% 4-5-1 +\uncover<35>{ + \verbindung{4}{5}{1} + \feld{4}{1}{\color{blue}9} +} +% 4-5-2 +\uncover<36>{ + \verbindung{4}{5}{2} + \feld{4}{2}{\color{red}15} + \wegweiser{4}{2}{3} +} +\uncover<37->{ + \feld{4}{2}{15} + \wegweiser{4}{2}{3} +} +% 4-5-3 +\uncover<37>{ + \verbindung{4}{5}{3} + \feld{4}{3}{\color{blue}6} +} +% 4-5-4 +\uncover<38>{ + \verbindung{4}{5}{4} + \feld{4}{4}{\color{red}16} + \wegweiser{4}{4}{3} +} +\uncover<39->{ + \feld{4}{4}{16} + \wegweiser{4}{4}{3} +} + + +\uncover<3->{ + + \foreach \x in {0,...,5}{ + \draw[line width=0.7pt] (\x,0.8)--(\x,-5); + } + \foreach \y in {0,...,-5}{ + \draw[line width=0.7pt] (-0.8,\y)--(5,\y); + } + \draw[line width=1.4pt] (0,0)--(5,0)--(5,-5)--(0,-5)--cycle; + + \node at (0.5,0.5) {$1$}; + \node at (1.5,0.5) {$2$}; + \node at (2.5,0.5) {$3$}; + \node at (3.5,0.5) {$4$}; + \node at (4.5,0.5) {$5$}; + + \node at (-0.5,-0.5) {$1$}; + \node at (-0.5,-1.5) {$2$}; + \node at (-0.5,-2.5) {$3$}; + \node at (-0.5,-3.5) {$4$}; + \node at (-0.5,-4.5) {$5$}; +} + +\end{tikzpicture} +\end{center} + +\uncover<40>{ + \vspace{-22pt} + \begin{block}{Lösung} + Der kürzeste Weg von 2 nach 4 ist 2---3---1---5---4 + \end{block} +} + +\end{column} +\end{columns} + +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/iteration.tex b/vorlesungen/slides/8/floyd-warshall/iteration.tex new file mode 100644 index 0000000..d7e782d --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/iteration.tex @@ -0,0 +1,14 @@ +% +% iteration.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup +\newboolean{wegweiser} +\begin{frame}[fragile] +\frametitle{Floyd-Warshall: Iteration} +\setboolean{wegweiser}{false} +\input{../slides/8/floyd-warshall/fw.tex} + +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/macdonalds.png b/vorlesungen/slides/8/floyd-warshall/macdonalds.png new file mode 100644 index 0000000..c442dfb Binary files /dev/null and b/vorlesungen/slides/8/floyd-warshall/macdonalds.png differ diff --git a/vorlesungen/slides/8/floyd-warshall/problem.tex b/vorlesungen/slides/8/floyd-warshall/problem.tex new file mode 100644 index 0000000..93f8229 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/problem.tex @@ -0,0 +1,146 @@ +% +% graph.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame}[fragile] +\frametitle{Problem: Kürzeste Wege} +\begin{center} +\begin{tikzpicture}[>=latex] + +\def\blob#1#2#3{ + \fill[color=#3] #1 circle[radius=0.2]; + \draw[line width=0.7pt] #1 circle[radius=0.2]; + \node at #1 {{\tiny #2}}; +} + +\def\kante#1#2{ + \draw[line width=0.7pt,shorten >= 0.2,shorten >= 0.2] #1 -- #2 ; +} + +\def\a{72} +\def\r{1.0} +\def\R{2.0} +\def\RR{3.5} + +\coordinate (A1) at ({\r*cos(0*\a)},{\r*sin(0*\a)}); +\coordinate (B1) at ({\r*cos(1*\a)},{\r*sin(1*\a)}); +\coordinate (C1) at ({\r*cos(2*\a)},{\r*sin(2*\a)}); +\coordinate (D1) at ({\r*cos(3*\a)},{\r*sin(3*\a)}); +\coordinate (E1) at ({\r*cos(4*\a)},{\r*sin(4*\a)}); + +\coordinate (F1) at ({\R*cos(0*\a)},{\R*sin(0*\a)}); +\coordinate (G1) at ({\R*cos(1*\a)},{\R*sin(1*\a)}); +\coordinate (H1) at ({\R*cos(2*\a)},{\R*sin(2*\a)}); +\coordinate (I1) at ({\R*cos(3*\a)},{\R*sin(3*\a)}); +\coordinate (J1) at ({\R*cos(4*\a)},{\R*sin(4*\a)}); + +\coordinate (K1) at ({\RR*cos(0.5*\a)},{\RR*sin(0.5*\a)}); +\coordinate (L1) at ({\RR*cos(1.5*\a)},{\RR*sin(1.5*\a)}); +\coordinate (M1) at ({\RR*cos(2.5*\a)},{\RR*sin(2.5*\a)}); +\coordinate (N1) at ({\RR*cos(3.5*\a)},{\RR*sin(3.5*\a)}); +\coordinate (O1) at ({\RR*cos(4.5*\a)},{\RR*sin(4.5*\a)}); + +\kante{(A1)}{(C1)} +\kante{(C1)}{(E1)} +\kante{(E1)}{(B1)} +\kante{(B1)}{(D1)} +\kante{(D1)}{(A1)} + +\kante{(F1)}{(G1)} +\kante{(G1)}{(H1)} +\kante{(H1)}{(I1)} +\kante{(I1)}{(J1)} +\kante{(J1)}{(F1)} + +\kante{(A1)}{(F1)} +\kante{(B1)}{(G1)} +\kante{(C1)}{(H1)} +\kante{(D1)}{(I1)} +\kante{(E1)}{(J1)} + +\kante{(K1)}{(L1)} +\kante{(L1)}{(M1)} +\kante{(M1)}{(N1)} +\kante{(N1)}{(O1)} +\kante{(O1)}{(K1)} + +\kante{(F1)}{(K1)} +\kante{(G1)}{(L1)} +\kante{(H1)}{(M1)} +\kante{(I1)}{(N1)} +\kante{(J1)}{(O1)} + +\kante{(F1)}{(O1)} +\kante{(G1)}{(K1)} +\kante{(H1)}{(L1)} +\kante{(I1)}{(M1)} +\kante{(J1)}{(N1)} + +\uncover<2>{ + \draw[line width=2pt,color=red] (M1)--(H1)--(G1)--(B1); +} + +\uncover<3>{ + \draw[line width=2pt,color=red] (M1)--(L1)--(G1)--(B1); +} + +\uncover<4>{ + \draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(B1); +} + +\uncover<5>{ + \draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(A1)--(F1); +} + +\uncover<6->{ + \draw[line width=2pt,color=red] (M1)--(I1)--(J1)--(F1); +} + +\uncover<2-4>{ + \blob{(B1)}{1}{red!20} + \blob{(M1)}{12}{red!20} +} +\uncover<5-8>{ + \blob{(M1)}{1}{red!20} + \blob{(F1)}{12}{red!20} +} + +\blob{(A1)}{0}{white} +\uncover<1>{ + \blob{(B1)}{1}{white} +} +\uncover<5-8>{ + \blob{(B1)}{12}{white} +} +\blob{(C1)}{2}{white} +\blob{(D1)}{3}{white} +\blob{(E1)}{4}{white} +\uncover<1-4>{ + \blob{(F1)}{5}{white} +} +\blob{(G1)}{6}{white} +\blob{(H1)}{7}{white} +\blob{(I1)}{8}{white} +\blob{(J1)}{9}{white} +\blob{(K1)}{10}{white} +\blob{(L1)}{11}{white} +\uncover<1>{ + \blob{(M1)}{12}{white} +} +\blob{(N1)}{13}{white} +\blob{(O1)}{14}{white} + +\node at (6,0) {\begin{minipage}{5cm} +\begin{itemize} +\item<3-> Nicht eindeutig +\item<5-> geradeste Wege sind nicht unbedingt die kürzesten +\item<7-> Gewichtung der Kanten +($\text{Schnellstrassen}\ne\text{Feldwege}$) +\item<8-> Orientierung der Kanten? +\end{itemize} +\end{minipage}}; + +\end{tikzpicture} +\end{center} +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/rekursion.tex b/vorlesungen/slides/8/floyd-warshall/rekursion.tex new file mode 100644 index 0000000..c664e41 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/rekursion.tex @@ -0,0 +1,108 @@ +% +% rekursion.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame}[fragile] +\frametitle{Rekursion} +\vspace{-20pt} +\begin{center} +\begin{tikzpicture}[>=latex] + +\def\blob#1#2#3{ + \fill[color=#3] #1 circle[radius=0.3]; + \draw[line width=0.7pt] #1 circle[radius=0.3]; + \node at #1 {{#2}}; +} + +\def\kante#1#2{ + \draw[line width=0.7pt,shorten >= 0.3,shorten >= 0.3] #1 -- #2 ; +} + +\coordinate (A) at (0,0); +\coordinate (B1) at (2,2); +\coordinate (B2) at (2,1); +\coordinate (B3) at (2,0); +\coordinate (B4) at (2,-1); +\coordinate (B5) at (2,-2); + +\draw[line width=1.9pt,color=gray] (A)--(B1); +\draw[line width=1.9pt,color=gray] (A)--(B2); +\draw[line width=1.9pt,color=gray] (A)--(B3); +\draw[line width=1.9pt,color=gray] (A)--(B4); +\draw[line width=1.9pt,color=gray] (A)--(B5); + +\coordinate (Z) at (10,0); + +\begin{scope} +\clip (2,-2.3) rectangle (10,2.3); +\foreach \y in{-10,...,10}{ + \draw[line width=1.9pt,color=gray] + (2,\y)--(10,{\y-8}); + \draw[line width=1.9pt,color=gray] + (2,\y)--(10,{\y+8}); +} +\end{scope} + +\uncover<2>{ +\draw[line width=4pt,color=red] (A)--(B1)--(5,-1)--(8,2)--(Z); +} + +\uncover<3>{ +\draw[line width=4pt,color=red] (A)--(B2)--(3,0)--(4,1)--(5,0)--(6,1)--(8.5,-1.5)--(Z); +} + +\uncover<4>{ +\draw[line width=4pt,color=red] (A)--(B3)--(2.5,0.5)--(3.5,-0.5)--(5,1.0)--(7,-1)--(9,1)--(Z); +} + +\uncover<5>{ +\draw[line width=4pt,color=red] (A)--(B4)--(3,0)--(4,1)--(5,0)--(6,1)--(7,0) + --(6.0,-1.0)--(7,-2)--(7.5,-1.5)--(7,-1)--(7.5,-0.5) + --(8.5,-1.5)--(Z); +} + +\uncover<6->{ + \draw[line width=4pt,color=red] (A)--(B5)--(6,2); +} +\uncover<7->{ + \draw[line width=4pt,color=red] (6,2)--(7,1)--(5,-1); +} +\uncover<8->{ + \draw[line width=4pt,color=red] (5,-1)--(6,-2)--(8,0)--(9,-1); +} +\uncover<9->{ + \draw[line width=4pt,color=red] (9,-1)--(Z); +} + +\blob{(A)}{$A$}{red!20} +\blob{(B1)}{$B_1$}{white} +\blob{(B2)}{$B_2$}{white} +\blob{(B3)}{$B_3$}{white} +\blob{(B4)}{$B_4$}{white} +\blob{(B5)}{$B_5$}{white} + +\blob{(Z)}{$Z$}{red!20} + +\uncover<6->{ + \node at (6,2) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/macdonalds.png}}; +} + +\uncover<7->{ + \node at (5,-1) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/starbucks.png}}; +} + +\uncover<8->{ + \node at (9,-1) {\includegraphics[width=2cm]{../slides/8/floyd-warshall/burgerking.png}}; +} + +\end{tikzpicture} +\end{center} + +\begin{block}{Abstieg} +Für den kürzesten Weg von $A$ nach $Z$ suche denjenigen Nachbarn $B_i$ +von $A$, der den kürzesten Weg von $B_i$ nach $Z$ hat. +\uncover<7->{$\Rightarrow$ wir brauchen {\color{red}alle} kürzesten Wege!} +\end{block} + +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/starbucks.png b/vorlesungen/slides/8/floyd-warshall/starbucks.png new file mode 100644 index 0000000..a28dbf7 Binary files /dev/null and b/vorlesungen/slides/8/floyd-warshall/starbucks.png differ diff --git a/vorlesungen/slides/8/floyd-warshall/wege.tex b/vorlesungen/slides/8/floyd-warshall/wege.tex new file mode 100644 index 0000000..7ff62a1 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wege.tex @@ -0,0 +1,26 @@ +% +% wege.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\frametitle{Wege statt Weglänge?} +\begin{columns}[t] +\begin{column}{0.48\hsize} +\begin{block}{Wege speichern?} +\uncover<3->{Es reicht, einen Wegweiser zum nächsten Knoten zu speichern} +\end{block} +\begin{center} +\begin{tikzpicture}[>=latex] + +\end{tikzpicture} +\end{center} +\end{column} +\begin{column}{0.48\hsize} +\uncover<2->{% +\begin{center} +\includegraphics[width=\hsize]{../slides/8/floyd-warshall/wegweiser.jpg} +\end{center}}% +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/wegiteration.tex b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex new file mode 100644 index 0000000..84ec679 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex @@ -0,0 +1,13 @@ +% +% wegiteration.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup +\newboolean{wegweiser} +\begin{frame}[fragile] +\frametitle{Floyd-Warshall: Wegweiser} +\setboolean{wegweiser}{true} +\input{../slides/8/floyd-warshall/fw.tex} +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg new file mode 100644 index 0000000..33aebe3 Binary files /dev/null and b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg differ diff --git a/vorlesungen/slides/8/inzidenzd.tex b/vorlesungen/slides/8/inzidenzd.tex index 19da619..18feeae 100644 --- a/vorlesungen/slides/8/inzidenzd.tex +++ b/vorlesungen/slides/8/inzidenzd.tex @@ -61,7 +61,7 @@ \begin{align*} B(G)_{ij}&=-1&&\Leftrightarrow&&\text{Kante $j$ von $i$}\\ B(G)_{kj}&=+1&&\Leftrightarrow&&\text{Kante $j$ nach $k$}\\ -A(G)_{ij}&=\pm 1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$} +A(G)_{ij}&=\phantom{-}1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$} \end{align*} \end{block} \end{column} @@ -91,6 +91,8 @@ rectangle } \draw[color=gray] (-0.1,-0.28) -- (-0.1,-2.4); \node[color=gray] at ({-0.67-(7-4)*\dx},0.04) [above] {\tiny Kanten}; +\node[color=gray] at ({0.00},{-0.38-(3-1)*\dy}) + [above,rotate=-90] {\tiny Knoten}; \end{scope} \begin{scope}[xshift=2.32cm,yshift=-0.24cm] @@ -121,21 +123,21 @@ rectangle B(G) &= \begin{pmatrix*}[r] --1& 0& 0& 0& 1&-1& 0\\ - 1&-1& 0& 0& 0& 0&-1\\ - 0& 1&-1& 0& 0& 1& 0\\ - 0& 0& 1&-1& 0& 0& 1\\ - 0& 0& 0& 1&-1& 0& 0 +-1& 0& 0& 0&+1&-1& 0\\ ++1&-1& 0& 0& 0& 0&-1\\ + 0&+1&-1& 0& 0&+1& 0\\ + 0& 0&+1&-1& 0& 0&+1\\ + 0& 0& 0&+1&-1& 0& 0 \end{pmatrix*} \\[20pt] A(G) &= \begin{pmatrix*}[r] - 0&-1&-1& 0&-1\\ --1& 0&-1&-1& 0\\ --1&-1& 0&-1& 0\\ - 0&-1&-1& 0&-1\\ --1& 0& 0&-1& 0 + 0&\phantom{-}1&\phantom{-}1& 0&\phantom{-}1\\ +\phantom{-}1& 0&\phantom{-}1&\phantom{-}1& 0\\ +\phantom{-}1&\phantom{-}1& 0&\phantom{-}1& 0\\ + 0&\phantom{-}1&\phantom{-}1& 0&\phantom{-}1\\ +\phantom{-}1& 0& 0&\phantom{-}1& 0 \end{pmatrix*} \end{aligned}$}; \end{tikzpicture} diff --git a/vorlesungen/slides/8/laplace.tex b/vorlesungen/slides/8/laplace.tex new file mode 100644 index 0000000..a1c364d --- /dev/null +++ b/vorlesungen/slides/8/laplace.tex @@ -0,0 +1,213 @@ +% +% laplace.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Laplace-Matrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (B) -- (D); + +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (A) -- (B); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (B) -- (C); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (C) -- (D); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (D) -- (E); +\draw[shorten >= 0.3cm,shorten <= 0.3cm] (E) -- (A); + +\uncover<2-4>{ +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (A) -- (B); +} + +\uncover<3-7>{ +\draw[->,color=darkgreen,line width=4pt,shorten <= 0.25cm,shorten >= 0.15cm] + (A) -- (C); +} + +\uncover<4-13>{ +\draw[->,color=darkgreen,line width=8pt,shorten <= 0.25cm,shorten >= 0cm] + (A) -- (E); +} + +\uncover<5->{ +\draw[<->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (A) -- (B); +} + +\uncover<6-8>{ +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (B) -- (C); +} + +\uncover<7-10>{ +\draw[->,color=darkgreen,line width=4pt,shorten <= 0.25cm,shorten >= 0.15cm] + (B) -- (D); +} + +\uncover<8->{ +\draw[<->,color=darkgreen,line width=4pt,shorten <= 0.15cm,shorten >= 0.15cm] + (A) -- (C); +} + +\uncover<9->{ +\draw[<->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (B) -- (C); +} + +\uncover<10-11>{ +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (C) -- (D); +} + +\uncover<11->{ +\draw[<->,color=darkgreen,line width=4pt,shorten <= 0.15cm,shorten >= 0.15cm] + (B) -- (D); +} + +\uncover<12->{ +\draw[<->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (C) -- (D); +} + +\uncover<13-14>{ +\draw[->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (D) -- (E); +} + +\uncover<14->{ +\draw[<->,color=darkgreen,line width=8pt,shorten <= 0cm,shorten >= 0cm] + (A) -- (E); +} + +\uncover<15->{ +\draw[<->,color=darkgreen,line width=2pt,shorten <= 0.25cm,shorten >= 0.25cm] + (D) -- (E); +} + +\fill[color=red] (A) circle[radius=0.3]; +\fill[color=red!50] (B) circle[radius=0.3]; +\fill[color=white] (C) circle[radius=0.3]; +\fill[color=blue!50] (D) circle[radius=0.3]; +\fill[color=blue] (E) circle[radius=0.3]; + +\draw (A) circle[radius=0.3]; +\draw (B) circle[radius=0.3]; +\draw (C) circle[radius=0.3]; +\draw (D) circle[radius=0.3]; +\draw (E) circle[radius=0.3]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; + +\end{tikzpicture} +\end{center} +\uncover<16->{% +\begin{block}{Definition} +Laplace-Matrix +\[ +L(G) = D(G) - A(G) +\] +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\begin{align*} +f +&= +\begin{pmatrix} +f(1)\\ +f(2)\\ +f(3)\\ +f(4)\\ +f(5) +\end{pmatrix} +\\ +\frac{df}{dt} +&= +-\kappa +\begin{pmatrix*}[r] +\only<1>{\phantom{-0}} + \only<2>{\phantom{-}1} + \only<3>{\phantom{-}2} + \only<4->{\phantom{-}3} + &\only<1>{\phantom{-0}}\only<2->{{-1}}% + &\only<-2>{\phantom{-0}}\only<3->{{-1}}% + &\uncover<16->{ 0} + &\only<-3>{\phantom{-0}}\only<4->{{-1}}\\ +\only<-4>{\phantom{-0}}\only<5->{{-1}} + &\only<-4>{\phantom{-0}} + \only<5>{\phantom{-}1} + \only<6>{\phantom{-}2} + \only<7->{\phantom{-}3} + &\only<-5>{\phantom{-0}}\only<6->{{-1}} + &\only<-6>{\phantom{-0}}\only<7->{{-1}} + &\uncover<16->{ 0}\\ +\only<-7>{\phantom{-0}}\only<8->{{-1}} + &\only<-8>{\phantom{-0}}\only<9->{{-1}} + &\only<-7>{\phantom{-0}} + \only<8>{\phantom{-}1} + \only<9>{\phantom{-}2} + \only<10->{\phantom{-}3} + &\only<-9>{\phantom{-0}}\only<10->{{-1}} + &\uncover<16->{ 0}\\ +\uncover<16->{ 0} + &\only<-10>{\phantom{-0}}\only<11->{{-1}} + &\only<-11>{\phantom{-0}}\only<12->{{-1}} + &\only<-10>{\phantom{-0}} + \only<11>{\phantom{-}1} + \only<12>{\phantom{-}2} + \only<13->{\phantom{-}3} + &\only<-12>{\phantom{-0}}\only<13->{{-1}}\\ +\only<-13>{\phantom{-0}}\only<14->{{-1}} + &\uncover<16->{ 0} + &\uncover<16->{ 0} + &\only<-14>{\phantom{-0}}\only<15->{{-1}} + &\only<-13>{\phantom{-0}} + \only<14>{\phantom{-}1} + \only<15->{\phantom{-}2} +\end{pmatrix*} +\begin{pmatrix} +f(1)\\ +f(2)\\ +f(3)\\ +f(4)\\ +f(5) +\end{pmatrix} +\\ +\uncover<17->{ +&= +-\kappa L f} +\end{align*} +\vspace{-20pt} +\uncover<18->{% +\begin{block}{Rekonstruktion} +Der Graph lässt sich aus $L$ rekonstruieren +\end{block}} +\end{column} +\end{columns} +\end{frame} + +\egroup + + 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 From a0a5f0f799be512684e31d13cdedc2ef1c404792 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 13 Mar 2021 21:09:35 +0100 Subject: add additional paper --- vorlesungen/slides/8/Makefile.inc | 11 +++ vorlesungen/slides/8/chapter.tex | 12 ++- vorlesungen/slides/8/inzidenz.tex | 27 +++++- vorlesungen/slides/8/inzidenzd.tex | 25 ++++- vorlesungen/slides/8/markov/google.tex | 123 +++++++++++++++++++++++++ vorlesungen/slides/8/markov/irreduzibel.tex | 136 ++++++++++++++++++++++++++++ vorlesungen/slides/8/markov/markov.tex | 111 +++++++++++++++++++++++ vorlesungen/slides/8/markov/pf.tex | 53 +++++++++++ vorlesungen/slides/8/markov/stationaer.tex | 57 ++++++++++++ vorlesungen/slides/8/tokyo/bahn0.tex | 11 +++ vorlesungen/slides/8/tokyo/bahn1.tex | 28 ++++++ vorlesungen/slides/8/tokyo/bahn2.tex | 12 +++ vorlesungen/slides/8/tokyo/google.tex | 11 +++ 13 files changed, 608 insertions(+), 9 deletions(-) create mode 100644 vorlesungen/slides/8/markov/google.tex create mode 100644 vorlesungen/slides/8/markov/irreduzibel.tex create mode 100644 vorlesungen/slides/8/markov/markov.tex create mode 100644 vorlesungen/slides/8/markov/pf.tex create mode 100644 vorlesungen/slides/8/markov/stationaer.tex create mode 100644 vorlesungen/slides/8/tokyo/bahn0.tex create mode 100644 vorlesungen/slides/8/tokyo/bahn1.tex create mode 100644 vorlesungen/slides/8/tokyo/bahn2.tex create mode 100644 vorlesungen/slides/8/tokyo/google.tex (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index 0a20f88..cc2c497 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -12,6 +12,8 @@ chapter8 = \ ../slides/8/inzidenzd.tex \ ../slides/8/diffusion.tex \ ../slides/8/laplace.tex \ + ../slides/8/fourier.tex \ + ../slides/8/spanningtree.tex \ ../slides/8/pfade/adjazenz.tex \ ../slides/8/pfade/langepfade.tex \ ../slides/8/pfade/beispiel.tex \ @@ -21,5 +23,14 @@ chapter8 = \ ../slides/8/floyd-warshall/iteration.tex \ ../slides/8/floyd-warshall/wegiteration.tex \ ../slides/8/floyd-warshall/wege.tex \ + ../slides/8/tokyo/google.tex \ + ../slides/8/tokyo/bahn0.tex \ + ../slides/8/tokyo/bahn1.tex \ + ../slides/8/tokyo/bahn2.tex \ + ../slides/8/markov/google.tex \ + ../slides/8/markov/markov.tex \ + ../slides/8/markov/irreduzibel.tex \ + ../slides/8/markov/stationaer.tex \ + ../slides/8/markov/pf.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index bd1c18f..b29145f 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -10,6 +10,8 @@ \folie{8/inzidenzd.tex} \folie{8/diffusion.tex} \folie{8/laplace.tex} +\folie{8/fourier.tex} +\folie{8/spanningtree.tex} \folie{8/pfade/adjazenz.tex} \folie{8/pfade/langepfade.tex} @@ -22,7 +24,15 @@ \folie{8/floyd-warshall/wegiteration.tex} \folie{8/floyd-warshall/wege.tex} +\folie{8/tokyo/google.tex} +\folie{8/tokyo/bahn0.tex} +\folie{8/tokyo/bahn1.tex} +\folie{8/tokyo/bahn2.tex} - +\folie{8/markov/google.tex} +\folie{8/markov/markov.tex} +\folie{8/markov/stationaer.tex} +\folie{8/markov/irreduzibel.tex} +\folie{8/markov/pf.tex} diff --git a/vorlesungen/slides/8/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex index 5911593..87578df 100644 --- a/vorlesungen/slides/8/inzidenz.tex +++ b/vorlesungen/slides/8/inzidenz.tex @@ -23,7 +23,9 @@ \draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); \draw[color=white,line width=5pt] (B) -- (D); -\draw[color=darkgreen,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); +{\color<2->{darkgreen} +\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); +} \draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); \draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); @@ -31,7 +33,12 @@ %\draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); \draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); +\only<-2>{ +\fill[color=white] (B) circle[radius=0.2]; +} +\only<3->{ \fill[color=red!20] (B) circle[radius=0.2]; +} \draw (A) circle[radius=0.2]; \draw (B) circle[radius=0.2]; @@ -51,18 +58,21 @@ \node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; \node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 4$}; \node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 5$}; -\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 6$}; +{\color<2->{darkgreen} +\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 6$}; +} \end{tikzpicture} \end{center} \vspace{-10pt} +\uncover<5->{% \begin{block}{Definition} \vspace{-15pt} \begin{align*} B(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante $j$ endet in Knoten $i$}\\ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$} \end{align*} -\end{block} +\end{block}} \end{column} \begin{column}{0.48\textwidth} \begin{center} @@ -73,8 +83,12 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$} \begin{scope} +\uncover<3->{ \fill[color=red!20] (1.8,1.8) rectangle (4.75,2.15); +} +\uncover<2->{ \fill[color=darkgreen!40,opacity=0.5] (4.46,0.36) rectangle (4.79,2.65); +} \foreach \y in {1,...,5}{ \node[color=gray] at (5.3,{2.45-(\y-1)*\dy}) {\tiny $\y$}; } @@ -87,9 +101,12 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$} \node[color=gray] at (5.3,{2.45-2*\dy}) [above,rotate=-90] {\tiny Knoten}; \end{scope} +\uncover<4->{ \begin{scope} +\uncover<3->{ \fill[color=red!20] (1.8,-1.16) rectangle (4.25,-0.77); \fill[color=red!20] (2.3,-2.6) rectangle (2.63,-0.29); +} \foreach \y in {1,...,5}{ \node[color=gray] at (4.7,{-0.5-(\y-1)*\dy}) {\tiny $\y$}; \node[color=gray] at ({1.92+(\y-1)*\dx},-0.1) {\tiny $\y$}; @@ -99,6 +116,7 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$} \node[color=gray] at ({1.92+2*\dx},0.1) {\tiny Knoten}; \node[color=gray] at (4.7,{-0.5-2*\dy}) [above,rotate=-90] {\tiny Knoten}; \end{scope} +} \node (0,0) [right] {$\displaystyle \begin{aligned} @@ -112,6 +130,7 @@ B(G) 0&0&0&1&0&1 \end{pmatrix} \\[12pt] +\uncover<4->{ A(G) &= \begin{pmatrix} @@ -121,7 +140,7 @@ A(G) 0&1&1&0&0\\ 1&0&0&0&0 \end{pmatrix} -\end{aligned}$}; +\end{aligned}}$}; \end{tikzpicture} \end{center} diff --git a/vorlesungen/slides/8/inzidenzd.tex b/vorlesungen/slides/8/inzidenzd.tex index 18feeae..5f2f51a 100644 --- a/vorlesungen/slides/8/inzidenzd.tex +++ b/vorlesungen/slides/8/inzidenzd.tex @@ -23,7 +23,9 @@ \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); \draw[color=white,line width=5pt] (B) -- (D); -\draw[->,shorten >= 0.2cm,shorten <= 0.2cm,color=darkgreen] (B) -- (D); +{\color<2->{darkgreen} +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); +} \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); @@ -32,7 +34,12 @@ \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); \draw (A) circle[radius=0.2]; +\only<-2>{ +\fill[color=white] (B) circle[radius=0.2]; +} +\only<3->{ \fill[color=red!20] (B) circle[radius=0.2]; +} \draw (B) circle[radius=0.2]; \draw (C) circle[radius=0.2]; \draw (D) circle[radius=0.2]; @@ -51,11 +58,14 @@ \node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$}; \node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$}; \node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$}; -\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; +{\color<2->{darkgreen} +\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; +} \end{tikzpicture} \end{center} \vspace{-15pt} +\uncover<5->{% \begin{block}{Definition} \vspace{-20pt} \begin{align*} @@ -63,7 +73,7 @@ B(G)_{ij}&=-1&&\Leftrightarrow&&\text{Kante $j$ von $i$}\\ B(G)_{kj}&=+1&&\Leftrightarrow&&\text{Kante $j$ nach $k$}\\ A(G)_{ij}&=\phantom{-}1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$} \end{align*} -\end{block} +\end{block}} \end{column} \begin{column}{0.58\textwidth} \begin{center} @@ -73,14 +83,18 @@ A(G)_{ij}&=\phantom{-}1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$} \def\dy{0.48} \begin{scope}[xshift=4cm,yshift=3cm] +\uncover<3->{ \fill[color=red!20] ({-0.67-(7-1)*\dx-0.4},{-0.38-(2-1)*\dy-0.2}) rectangle ({-0.67-(7-7)*\dx+0.2},{-0.38-(2-1)*\dy+0.16}); +} +\uncover<2->{ \fill[color=darkgreen!40,opacity=0.5] ({-0.67-(7-7)*\dx-0.4},{-0.38-(5-1)*\dy-0.2}) rectangle ({-0.67-(7-7)*\dx+0.2},{-0.38-(1-1)*\dy+0.16}); +} %\draw (0,0) circle[radius=0.05]; \foreach \x in {1,...,7}{ \node[color=gray] at ({-0.67-(7-\x)*\dx},0.0) {\tiny $\x$}; @@ -95,6 +109,7 @@ rectangle [above,rotate=-90] {\tiny Knoten}; \end{scope} +\uncover<4->{ \begin{scope}[xshift=2.32cm,yshift=-0.24cm] %\draw (0,0) circle[radius=0.05]; \fill[color=red!20] @@ -117,6 +132,7 @@ rectangle \node[color=gray] at ({0.00},{-0.38-(3-1)*\dy}) [above,rotate=-90] {\tiny Knoten}; \end{scope} +} \node at (0,0) {$\displaystyle \begin{aligned} @@ -130,6 +146,7 @@ B(G) 0& 0& 0&+1&-1& 0& 0 \end{pmatrix*} \\[20pt] +\uncover<4->{ A(G) &= \begin{pmatrix*}[r] @@ -138,7 +155,7 @@ A(G) \phantom{-}1&\phantom{-}1& 0&\phantom{-}1& 0\\ 0&\phantom{-}1&\phantom{-}1& 0&\phantom{-}1\\ \phantom{-}1& 0& 0&\phantom{-}1& 0 -\end{pmatrix*} +\end{pmatrix*}} \end{aligned}$}; \end{tikzpicture} \end{center} diff --git a/vorlesungen/slides/8/markov/google.tex b/vorlesungen/slides/8/markov/google.tex new file mode 100644 index 0000000..d1ec31d --- /dev/null +++ b/vorlesungen/slides/8/markov/google.tex @@ -0,0 +1,123 @@ +% +% google.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Google-Matrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.4} +\coordinate (A) at (0,0); +\coordinate (B) at (0:\r); +\coordinate (C) at (60:\r); +\coordinate (D) at (120:\r); +\coordinate (E) at (180:\r); + +\foreach \a in {2,...,5}{ + \fill[color=white] ({60*(\a-2)}:\r) circle[radius=0.2]; + \draw ({60*(\a-2)}:\r) circle[radius=0.2]; + \node at ({60*(\a-2)}:\r) {$\a$}; +} +\fill[color=white] (A) circle[radius=0.2]; +\draw (A) circle[radius=0.2]; +\node at (A) {$1$}; + +{\color<6>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +} + +{\color<7>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) to[out=-150,in=-30] (E); +} + +{\color<8>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-90,in=30] (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-30,in=90] (B); +} + +{\color<9>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (C); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +} + +{\color<10>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) to[out=90,in=-150] (D); +} + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\renewcommand{\arraystretch}{1.1} +\uncover<5->{ +\begin{align*} +H&=\begin{pmatrix} +\uncover<6->{0 } + &\uncover<7->{0 } + &\uncover<8->{{\color<8>{red}\frac{1}{2}}} + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ +\uncover<6->{{\color<6>{red}\frac{1}{2}}} + &\uncover<7->{0 } + &\uncover<8->{{\color<8>{red}\frac{1}{2}}} + &\uncover<9->{0 } + &\uncover<10->{0 }\\ +\uncover<6->{{\color<6>{red}\frac{1}{2}}} + &\uncover<7->{{\color<7>{red}\frac{1}{2}}} + &\uncover<8->{0 } + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{0 }\\ +\uncover<6->{0 } + &\uncover<7->{0 } + &\uncover<8->{0 } + &\uncover<9->{0 } + &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ +\uncover<6->{0 } + &\uncover<7->{{\color<7>{red}\frac{1}{2}}} + &\uncover<8->{0 } + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{0 } +\end{pmatrix} +\\ +\uncover<11->{ +h_{ij} +&= +\frac{1}{\text{Anzahl Links ausgehend von $j$}} +} +\end{align*}} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Aufgabe} +Bestimme die Wahrscheinlichkeit $p(i)$, mit der sich ein Surfer +auf der Website $i$ befindet +\end{block} +\uncover<2->{ +\begin{block}{Navigation} +$p(i) = P(i,\text{vor Navigation})$, +\uncover<3->{$p'(i)=P(i,\text{nach Navigation})$} +\uncover<4->{ +\[ +p'(i) = \sum_{j=1}^n h_{ij} p(j) +\]} +\end{block}} +\vspace{-15pt} +\begin{block}{Freier Wille} +\vspace{-12pt} +\[ +G = \alpha H + (1-\alpha)\frac{UU^t}{n} +\] +Google-Matrix +\end{block} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/irreduzibel.tex b/vorlesungen/slides/8/markov/irreduzibel.tex new file mode 100644 index 0000000..87e90e4 --- /dev/null +++ b/vorlesungen/slides/8/markov/irreduzibel.tex @@ -0,0 +1,136 @@ +% +% irreduzibel.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Irreduzible Markovkette} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\r{2} +\coordinate (A) at ({\r*cos(0*60)},{\r*sin(0*60)}); +\coordinate (B) at ({\r*cos(1*60)},{\r*sin(1*60)}); +\coordinate (C) at ({\r*cos(2*60)},{\r*sin(2*60)}); +\coordinate (D) at ({\r*cos(3*60)},{\r*sin(3*60)}); +\coordinate (E) at ({\r*cos(4*60)},{\r*sin(4*60)}); +\coordinate (F) at ({\r*cos(5*60)},{\r*sin(5*60)}); + +\uncover<-2>{ +\draw (A) -- (B); +\draw (A) -- (C); +\draw (A) -- (D); +\draw (A) -- (E); +\draw (A) -- (F); + +\draw (B) -- (A); +\draw (B) -- (C); +\draw (B) -- (D); +\draw (B) -- (E); +\draw (B) -- (F); + +\draw (C) -- (A); +\draw (C) -- (B); +\draw (C) -- (D); +\draw (C) -- (E); +\draw (C) -- (F); + +\draw (D) -- (A); +\draw (D) -- (B); +\draw (D) -- (C); +\draw (D) -- (E); +\draw (D) -- (F); + +\draw (E) -- (A); +\draw (E) -- (B); +\draw (E) -- (C); +\draw (E) -- (D); +\draw (E) -- (F); + +\draw (F) -- (A); +\draw (F) -- (B); +\draw (F) -- (C); +\draw (F) -- (D); +\draw (F) -- (E); +} + +\uncover<3->{ + +\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] (A) to[out=90,in=-30] (B); +\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] (A) -- (C); +\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) -- (A); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] (B) to[out=150,in=30] (C); +\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) to[out=-90,in=-150,distance=1cm] (B); +\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) to[out=-60,in=180] (A); +\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) -- (B); + +\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] + (D) to[out=-90,in=150] (E); +\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] + (E) -- (D); +\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] + (E) to[out=-30,in=-150] (F); +\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] + (F) -- (E); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] + (F) to[out=120,in=0] (D); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] + (D) -- (F); +} + +\fill[color=white] (A) circle[radius=0.2]; +\fill[color=white] (B) circle[radius=0.2]; +\fill[color=white] (C) circle[radius=0.2]; +\fill[color=white] (D) circle[radius=0.2]; +\fill[color=white] (E) circle[radius=0.2]; +\fill[color=white] (F) circle[radius=0.2]; + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; +\draw (F) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (F) {$6$}; + +\end{tikzpicture} +\end{center} +\uncover<2->{% +\begin{block}{Irreduzibel} +Graph zusammenhängend $\Rightarrow$ +Keine Zerlegung in Teilgraphen möglich +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<3->{% +\begin{block}{Reduzibel} +Die Zustandsmenge zerfällt in zwei disjunkte Teilmengen $V=V_1\cup V_2$ +und es gibt keine Übergängen zwischen den Mengen: +\uncover<4->{% +\begin{align*} +P +&= +\begin{pmatrix*}[l] +0 &0.2&0.5& & & \\ +0.3&0.2&0.5& & & \\ +0.7&0.6&0 & & & \\ + & & &0 &0.3&0.4\\ + & & &0.4&0 &0.6\\ + & & &0.6&0.7&0 +\end{pmatrix*} +\end{align*}}% +\uncover<5->{% +$P$ zerfällt in zwei Blöcke die unabhängig voneinander analysiert werden können +} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/markov.tex b/vorlesungen/slides/8/markov/markov.tex new file mode 100644 index 0000000..e92ff0f --- /dev/null +++ b/vorlesungen/slides/8/markov/markov.tex @@ -0,0 +1,111 @@ +% +% markov.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\begin{frame}[t] +\frametitle{Markovketten} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!40] + (A) -- (C); +\draw[color=white,line width=8pt] (B) -- (D); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!80] + (B) -- (D); + +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!60] + (A) -- (B); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!20] + (B) -- (C); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (C) -- (D); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (D) -- (E); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (E) -- (A); + +\fill[color=white] (A) circle[radius=0.2]; +\fill[color=white] (B) circle[radius=0.2]; +\fill[color=white] (C) circle[radius=0.2]; +\fill[color=white] (D) circle[radius=0.2]; +\fill[color=white] (E) circle[radius=0.2]; + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; + +\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 0.6$}; +\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 0.2$}; +\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 1$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 1$}; +\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 1$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 0.4$}; +\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 0.8$}; + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\uncover<7->{% +\begin{block}{Verteilung} +\begin{itemize} +\item<8-> +Welche stationäre Verteilung auf den Knoten stellt sich ein? +\item<9-> +$P(i)=?$ +\end{itemize} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<2->{% +\begin{block}{\strut\mbox{Übergang\only<3->{s-/Wahrscheinlichkeit}smatrix}} +$P_{ij} = P(i | j)$, Wahrscheinlichkeit, in den Zustand $i$ überzugehen, +\begin{align*} +P +&= +\begin{pmatrix} + & & & &1\phantom{.0}\\ +0.6& & & & \\ +0.4&0.2& & & \\ + &0.8&1\phantom{.0}& & \\ + & & &1\phantom{.0}& +\end{pmatrix} +\end{align*} +\end{block}} +\vspace{-10pt} +\uncover<4->{% +\begin{block}{Eigenschaften} +\begin{itemize} +\item<5-> $P_{ij}\ge 0\;\forall i,j$ +\item<6-> Spaltensumme: +\( +\displaystyle +\sum_{i=1}^n P_{ij} = 1\;\forall j +\) +\end{itemize} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/pf.tex b/vorlesungen/slides/8/markov/pf.tex new file mode 100644 index 0000000..da2ef2b --- /dev/null +++ b/vorlesungen/slides/8/markov/pf.tex @@ -0,0 +1,53 @@ +% +% pf.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Perron-Frobenius-Theorie} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Positive Matrizen und Vektoren} +$P\in M_{m\times n}(\mathbb{R})$ +\begin{itemize} +\item<2-> +$P$ heisst positiv, $P>0$, wenn $p_{ij}>0\;\forall i,j$ +\item<3-> +$P\ge 0$, wenn $p_{ij}\ge 0\;\forall i,j$ +\end{itemize} +\end{block} +\uncover<4->{% +\begin{block}{Beispiele} +\begin{itemize} +\item<5-> +Adjazenzmatrix $A(G)$ +\item<6-> +Gradmatrix $D(G)$ +\item<7-> +Wahrscheinlichkeitsmatrizen +\end{itemize} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<8->{% +\begin{block}{Satz} +Es gibt einen positiven Eigenvektor $p$ von $P$ zum Eigenwert $1$ +\end{block}} +\uncover<9->{% +\begin{block}{Satz} +$P$ irreduzible Matrix, $P\ge 0$, hat einen Eigenvektor $p$, $p\ge 0$, +zum Eigenwert $1$ +\end{block}} +\uncover<10->{% +\begin{block}{Potenzmethode} +Falls $P\ge 0$ einen eindeutigen Eigenvektor $p$ hat\uncover<11->{, +dann konveriert die rekursiv definierte Folge +\[ +p_{n+1}=\frac{Pp_n}{\|Pp_n\|}, p_0 \ge 0, p_0\ne 0 +\]}% +\uncover<12->{$\displaystyle\lim_{n\to\infty} p_n = p$} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/stationaer.tex b/vorlesungen/slides/8/markov/stationaer.tex new file mode 100644 index 0000000..92fab16 --- /dev/null +++ b/vorlesungen/slides/8/markov/stationaer.tex @@ -0,0 +1,57 @@ +% +% stationaer.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Stationäre Verteilung} +%\vspace{-15pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Zeitentwicklung} +\begin{itemize} +\item<2-> +$P$ eine Wahrscheinlichkeitsmatrix +\item<3-> +$p_0\in\mathbb{R}^n$ Verteilung zur Zeit $t=0$ bekannt +\item<4-> +$p_k\in\mathbb{R}^n$ Verteilung zur Zeit $t=k$ +\end{itemize} +\uncover<5->{% +Entwicklungsgesetz +\begin{align*} +P(i,t=k) +&= +\sum_{j=1}^n P_{ij} P(j,t=k-1) +\\ +\uncover<6->{ +p_k &= Pp_{k-1} +} +\end{align*}} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<7->{% +\begin{block}{Stationär} +Bedingung: $p_{k\mathstrut} = p_{k-1}$ +\uncover<8->{ +\begin{align*} +\Rightarrow +Pp &= p +\end{align*}}\uncover<9->{% +Eigenvektor zum Eigenwert $1$} +\end{block}} +\uncover<10->{% +\begin{block}{Fragen} +\begin{enumerate} +\item<11-> +Gibt es eine stationäre Verteilung? +\item<12-> +Gibt es einen Eigenvektor mit Einträgen $\ge 0$? +\item<13-> +Gibt es mehr als eine Verteilung? +\end{enumerate} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/tokyo/bahn0.tex b/vorlesungen/slides/8/tokyo/bahn0.tex new file mode 100644 index 0000000..9c39712 --- /dev/null +++ b/vorlesungen/slides/8/tokyo/bahn0.tex @@ -0,0 +1,11 @@ +% +% bahn.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\begin{center} +\includegraphics[width=\hsize]{../slides/8/tokyo/tokyosubway.pdf} +\end{center} +\end{frame} + diff --git a/vorlesungen/slides/8/tokyo/bahn1.tex b/vorlesungen/slides/8/tokyo/bahn1.tex new file mode 100644 index 0000000..6ac3344 --- /dev/null +++ b/vorlesungen/slides/8/tokyo/bahn1.tex @@ -0,0 +1,28 @@ +% +% bahn.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% + +\begin{frame} +\frametitle{Tokyo Bahn-Netz} +\begin{center} +\begin{tabular}{rl} +882&Bahnstationen\\ +108&Bahnlinien\\ +29&Bahngesellschaften\\ +20\,000\,000&Passagiere täglich\\ +7\,000\,000&Passagiere alleine in Shinjuku\\ +\end{tabular} +\end{center} +\uncover<2->{ +\begin{block}{Dirichlet-Zerlegung und Bahnhöfe} +\begin{center} +\uncover<3->{Passagiere wählen den nächsten Bahnhöfe}\\ +\uncover<4->{$\Downarrow$}\\ +\uncover<5->{Bahnhöfe definieren eine Dirichletzerlegung der Stadt} +\end{center} +\end{block} +} +\end{frame} + diff --git a/vorlesungen/slides/8/tokyo/bahn2.tex b/vorlesungen/slides/8/tokyo/bahn2.tex new file mode 100644 index 0000000..4adc1bf --- /dev/null +++ b/vorlesungen/slides/8/tokyo/bahn2.tex @@ -0,0 +1,12 @@ +% +% bahn.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% + +\begin{frame} +\begin{center} +\includegraphics[width=\hsize]{../slides/8/tokyo/shinjuku-subway-map.jpg} +\end{center} +\end{frame} + diff --git a/vorlesungen/slides/8/tokyo/google.tex b/vorlesungen/slides/8/tokyo/google.tex new file mode 100644 index 0000000..d37c98d --- /dev/null +++ b/vorlesungen/slides/8/tokyo/google.tex @@ -0,0 +1,11 @@ +% +% google.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\begin{center} +\includegraphics[width=\hsize]{../slides/8/tokyo/transportnetworkgraph.png} +\end{center} +\end{frame} + -- cgit v1.2.1 From 1c1979d3d94a712af2b1c59a78bbf53ac020a86f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 15 Mar 2021 13:25:12 +0100 Subject: add new slide --- vorlesungen/slides/8/Makefile.inc | 1 + vorlesungen/slides/8/chapter.tex | 1 + vorlesungen/slides/8/produkt.tex | 100 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 102 insertions(+) create mode 100644 vorlesungen/slides/8/produkt.tex (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index cc2c497..233835a 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -12,6 +12,7 @@ chapter8 = \ ../slides/8/inzidenzd.tex \ ../slides/8/diffusion.tex \ ../slides/8/laplace.tex \ + ../slides/8/produkt.tex \ ../slides/8/fourier.tex \ ../slides/8/spanningtree.tex \ ../slides/8/pfade/adjazenz.tex \ diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index b29145f..ac06775 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -10,6 +10,7 @@ \folie{8/inzidenzd.tex} \folie{8/diffusion.tex} \folie{8/laplace.tex} +\folie{8/produkt.tex} \folie{8/fourier.tex} \folie{8/spanningtree.tex} diff --git a/vorlesungen/slides/8/produkt.tex b/vorlesungen/slides/8/produkt.tex new file mode 100644 index 0000000..1d8b725 --- /dev/null +++ b/vorlesungen/slides/8/produkt.tex @@ -0,0 +1,100 @@ +% +% produkt.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\frametitle{Inzidenz- und Laplace-Matrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.40\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +\draw[color=white,line width=5pt] (B) -- (D); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D); + +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) -- (D); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (0,0) {$G$}; + +\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 1$}; +\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 2$}; +\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$}; +\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$}; +\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$}; + +\end{tikzpicture} +\end{center} +\vspace{-15pt} +\begin{block}{Berechne} +\vspace{-20pt} +\begin{align*} +\uncover<4->{L(G)}&\uncover<4->{=}B(G)B(G)^t +\end{align*} +\end{block} +\end{column} +\begin{column}{0.58\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\dx{0.84} +\def\dy{0.48} + +\node at (0,0) {$\displaystyle +\begin{aligned} +B(G) +&= +\begin{pmatrix*}[r] +-1& 0& 0& 0&+1&-1& 0\\ ++1&-1& 0& 0& 0& 0&-1\\ + 0&+1&-1& 0& 0&+1& 0\\ + 0& 0&+1&-1& 0& 0&+1\\ + 0& 0& 0&+1&-1& 0& 0 +\end{pmatrix*} +\\[20pt] +\uncover<2->{ +L(G) +&= +\begin{pmatrix*}[r] + 3&\uncover<3->{-1}&\uncover<3->{-1}&\uncover<3->{ 0}&\uncover<3->{-1}\\ +\uncover<3->{-1}& 3&\uncover<3->{-1}&\uncover<3->{-1}&\uncover<3->{ 0}\\ +\uncover<3->{-1}&\uncover<3->{-1}& 3&\uncover<3->{-1}&\uncover<3->{ 0}\\ +\uncover<3->{ 0}&\uncover<3->{-1}&\uncover<3->{-1}& 3&\uncover<3->{-1}\\ +\uncover<3->{-1}&\uncover<3->{ 0}&\uncover<3->{ 0}&\uncover<3->{-1}& 2 +\end{pmatrix*}} +\end{aligned}$}; +\end{tikzpicture} +\end{center} +\end{column} +\end{columns} +\end{frame} +\egroup -- cgit v1.2.1 From 4614294614e6f6b38e0ca86e77871e75b4c26071 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 16 Mar 2021 15:48:10 +0100 Subject: add new slides --- vorlesungen/slides/8/Makefile.inc | 5 - vorlesungen/slides/8/chapter.tex | 7 - vorlesungen/slides/8/fourier.tex | 83 +++++++++++ vorlesungen/slides/8/inzidenz.tex | 4 +- vorlesungen/slides/8/markov/google.tex | 123 ---------------- vorlesungen/slides/8/markov/irreduzibel.tex | 136 ----------------- vorlesungen/slides/8/markov/markov.tex | 111 -------------- vorlesungen/slides/8/markov/pf.tex | 53 ------- vorlesungen/slides/8/markov/stationaer.tex | 57 ------- vorlesungen/slides/8/spanningtree.tex | 164 +++++++++++++++++++++ vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg | Bin 0 -> 231575 bytes vorlesungen/slides/8/tokyo/tokyosubway.pdf | Bin 0 -> 1016965 bytes .../slides/8/tokyo/transportnetworkgraph.png | Bin 0 -> 114239 bytes 13 files changed, 249 insertions(+), 494 deletions(-) create mode 100644 vorlesungen/slides/8/fourier.tex delete mode 100644 vorlesungen/slides/8/markov/google.tex delete mode 100644 vorlesungen/slides/8/markov/irreduzibel.tex delete mode 100644 vorlesungen/slides/8/markov/markov.tex delete mode 100644 vorlesungen/slides/8/markov/pf.tex delete mode 100644 vorlesungen/slides/8/markov/stationaer.tex create mode 100644 vorlesungen/slides/8/spanningtree.tex create mode 100644 vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg create mode 100644 vorlesungen/slides/8/tokyo/tokyosubway.pdf create mode 100644 vorlesungen/slides/8/tokyo/transportnetworkgraph.png (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index 233835a..d46dc7f 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -28,10 +28,5 @@ chapter8 = \ ../slides/8/tokyo/bahn0.tex \ ../slides/8/tokyo/bahn1.tex \ ../slides/8/tokyo/bahn2.tex \ - ../slides/8/markov/google.tex \ - ../slides/8/markov/markov.tex \ - ../slides/8/markov/irreduzibel.tex \ - ../slides/8/markov/stationaer.tex \ - ../slides/8/markov/pf.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index ac06775..6a0b13f 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -30,10 +30,3 @@ \folie{8/tokyo/bahn1.tex} \folie{8/tokyo/bahn2.tex} -\folie{8/markov/google.tex} -\folie{8/markov/markov.tex} -\folie{8/markov/stationaer.tex} -\folie{8/markov/irreduzibel.tex} -\folie{8/markov/pf.tex} - - diff --git a/vorlesungen/slides/8/fourier.tex b/vorlesungen/slides/8/fourier.tex new file mode 100644 index 0000000..86d8086 --- /dev/null +++ b/vorlesungen/slides/8/fourier.tex @@ -0,0 +1,83 @@ +% +% fourier.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Fourier-Transformation} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Algebra} +Die Laplace-Matrix eines Graphen ist symmetrisch +\uncover<2->{% + +$\Rightarrow$ +Es gibt eine Basis aus Eigenvektoren $g_i\in\mathbb{R}^n$ von $L(G)$: +\begin{align*} +L(G)g_i&=\lambda_i g_i +\end{align*}} +\end{block} +\uncover<12->{% +\vspace{-20pt} +\begin{block}{Fourier-Transformation} +Jedes $f\in\mathbb{R}^n$ kann durch die $g_i$ ausgedrückt werden +\begin{align*} +\uncover<13->{ +f&= a_1 g_1 + \dots + a_n g_n +} +\\ +\uncover<14->{ +&= \hat{f}_1 g_1 + \dots + \hat{f}_ng_n = \sum_{k=1}^n \hat{f}_kg_k +} +\end{align*} +\uncover<15->{% +Zerlegung nach Zeitkonstante $\lambda_i$ +} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<3->{% +\begin{block}{Anwendung} +Wärmeleitungsgleichung +\begin{align*} +\uncover<4->{ +\frac{d}{dt}f &= L(G) f +} +\intertext{\uncover<5->{{\usebeamercolor[fg]{title}Ansatz:}}} +\uncover<6->{ +f&=a_1g_1T_1(t)+\dots + a_ng_nT_n(t) +} +\\ +\uncover<7->{ +\frac{d}{dt}f +&= +a_1g_1\dot{T}_1(t) + \dots + a_1g_1 \dot{T}_n(t) +} +\\ +\uncover<8->{ +&= +a_1Lg_1 + \dots + a_nLg_n +} +\\ +\uncover<9->{ +&= +a_1\lambda_1 g_1 + \dots + a_n\lambda_n g_n +} +\\ +\uncover<10->{ +\dot{T}_i(t) &= \lambda_i T_i(t) +} +\uncover<11->{ +\quad +\Rightarrow +\quad +T_i(t) = e^{\lambda_it} \uncover<-9>{T_i(0)} +} +\end{align*} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex index 87578df..952c85b 100644 --- a/vorlesungen/slides/8/inzidenz.tex +++ b/vorlesungen/slides/8/inzidenz.tex @@ -126,8 +126,8 @@ B(G) 1&0&0&1&1&0\\ 1&1&0&0&0&1\\ 0&1&1&0&1&0\\ -0&0&1&0&0&0\\ -0&0&0&1&0&1 +0&0&1&0&0&1\\ +0&0&0&1&0&0 \end{pmatrix} \\[12pt] \uncover<4->{ diff --git a/vorlesungen/slides/8/markov/google.tex b/vorlesungen/slides/8/markov/google.tex deleted file mode 100644 index d1ec31d..0000000 --- a/vorlesungen/slides/8/markov/google.tex +++ /dev/null @@ -1,123 +0,0 @@ -% -% google.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\setlength{\abovedisplayskip}{5pt} -\setlength{\belowdisplayskip}{5pt} -\frametitle{Google-Matrix} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] - -\def\r{2.4} -\coordinate (A) at (0,0); -\coordinate (B) at (0:\r); -\coordinate (C) at (60:\r); -\coordinate (D) at (120:\r); -\coordinate (E) at (180:\r); - -\foreach \a in {2,...,5}{ - \fill[color=white] ({60*(\a-2)}:\r) circle[radius=0.2]; - \draw ({60*(\a-2)}:\r) circle[radius=0.2]; - \node at ({60*(\a-2)}:\r) {$\a$}; -} -\fill[color=white] (A) circle[radius=0.2]; -\draw (A) circle[radius=0.2]; -\node at (A) {$1$}; - -{\color<6>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); -} - -{\color<7>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) to[out=-150,in=-30] (E); -} - -{\color<8>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-90,in=30] (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-30,in=90] (B); -} - -{\color<9>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (C); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); -} - -{\color<10>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) to[out=90,in=-150] (D); -} - -\end{tikzpicture} -\end{center} -\vspace{-10pt} -\renewcommand{\arraystretch}{1.1} -\uncover<5->{ -\begin{align*} -H&=\begin{pmatrix} -\uncover<6->{0 } - &\uncover<7->{0 } - &\uncover<8->{{\color<8>{red}\frac{1}{2}}} - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ -\uncover<6->{{\color<6>{red}\frac{1}{2}}} - &\uncover<7->{0 } - &\uncover<8->{{\color<8>{red}\frac{1}{2}}} - &\uncover<9->{0 } - &\uncover<10->{0 }\\ -\uncover<6->{{\color<6>{red}\frac{1}{2}}} - &\uncover<7->{{\color<7>{red}\frac{1}{2}}} - &\uncover<8->{0 } - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{0 }\\ -\uncover<6->{0 } - &\uncover<7->{0 } - &\uncover<8->{0 } - &\uncover<9->{0 } - &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ -\uncover<6->{0 } - &\uncover<7->{{\color<7>{red}\frac{1}{2}}} - &\uncover<8->{0 } - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{0 } -\end{pmatrix} -\\ -\uncover<11->{ -h_{ij} -&= -\frac{1}{\text{Anzahl Links ausgehend von $j$}} -} -\end{align*}} -\end{column} -\begin{column}{0.48\textwidth} -\begin{block}{Aufgabe} -Bestimme die Wahrscheinlichkeit $p(i)$, mit der sich ein Surfer -auf der Website $i$ befindet -\end{block} -\uncover<2->{ -\begin{block}{Navigation} -$p(i) = P(i,\text{vor Navigation})$, -\uncover<3->{$p'(i)=P(i,\text{nach Navigation})$} -\uncover<4->{ -\[ -p'(i) = \sum_{j=1}^n h_{ij} p(j) -\]} -\end{block}} -\vspace{-15pt} -\begin{block}{Freier Wille} -\vspace{-12pt} -\[ -G = \alpha H + (1-\alpha)\frac{UU^t}{n} -\] -Google-Matrix -\end{block} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/irreduzibel.tex b/vorlesungen/slides/8/markov/irreduzibel.tex deleted file mode 100644 index 87e90e4..0000000 --- a/vorlesungen/slides/8/markov/irreduzibel.tex +++ /dev/null @@ -1,136 +0,0 @@ -% -% irreduzibel.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Irreduzible Markovkette} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] -\def\r{2} -\coordinate (A) at ({\r*cos(0*60)},{\r*sin(0*60)}); -\coordinate (B) at ({\r*cos(1*60)},{\r*sin(1*60)}); -\coordinate (C) at ({\r*cos(2*60)},{\r*sin(2*60)}); -\coordinate (D) at ({\r*cos(3*60)},{\r*sin(3*60)}); -\coordinate (E) at ({\r*cos(4*60)},{\r*sin(4*60)}); -\coordinate (F) at ({\r*cos(5*60)},{\r*sin(5*60)}); - -\uncover<-2>{ -\draw (A) -- (B); -\draw (A) -- (C); -\draw (A) -- (D); -\draw (A) -- (E); -\draw (A) -- (F); - -\draw (B) -- (A); -\draw (B) -- (C); -\draw (B) -- (D); -\draw (B) -- (E); -\draw (B) -- (F); - -\draw (C) -- (A); -\draw (C) -- (B); -\draw (C) -- (D); -\draw (C) -- (E); -\draw (C) -- (F); - -\draw (D) -- (A); -\draw (D) -- (B); -\draw (D) -- (C); -\draw (D) -- (E); -\draw (D) -- (F); - -\draw (E) -- (A); -\draw (E) -- (B); -\draw (E) -- (C); -\draw (E) -- (D); -\draw (E) -- (F); - -\draw (F) -- (A); -\draw (F) -- (B); -\draw (F) -- (C); -\draw (F) -- (D); -\draw (F) -- (E); -} - -\uncover<3->{ - -\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] (A) to[out=90,in=-30] (B); -\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] (A) -- (C); -\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) -- (A); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] (B) to[out=150,in=30] (C); -\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) to[out=-90,in=-150,distance=1cm] (B); -\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) to[out=-60,in=180] (A); -\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) -- (B); - -\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] - (D) to[out=-90,in=150] (E); -\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] - (E) -- (D); -\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] - (E) to[out=-30,in=-150] (F); -\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] - (F) -- (E); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] - (F) to[out=120,in=0] (D); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] - (D) -- (F); -} - -\fill[color=white] (A) circle[radius=0.2]; -\fill[color=white] (B) circle[radius=0.2]; -\fill[color=white] (C) circle[radius=0.2]; -\fill[color=white] (D) circle[radius=0.2]; -\fill[color=white] (E) circle[radius=0.2]; -\fill[color=white] (F) circle[radius=0.2]; - -\draw (A) circle[radius=0.2]; -\draw (B) circle[radius=0.2]; -\draw (C) circle[radius=0.2]; -\draw (D) circle[radius=0.2]; -\draw (E) circle[radius=0.2]; -\draw (F) circle[radius=0.2]; - -\node at (A) {$1$}; -\node at (B) {$2$}; -\node at (C) {$3$}; -\node at (D) {$4$}; -\node at (E) {$5$}; -\node at (F) {$6$}; - -\end{tikzpicture} -\end{center} -\uncover<2->{% -\begin{block}{Irreduzibel} -Graph zusammenhängend $\Rightarrow$ -Keine Zerlegung in Teilgraphen möglich -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<3->{% -\begin{block}{Reduzibel} -Die Zustandsmenge zerfällt in zwei disjunkte Teilmengen $V=V_1\cup V_2$ -und es gibt keine Übergängen zwischen den Mengen: -\uncover<4->{% -\begin{align*} -P -&= -\begin{pmatrix*}[l] -0 &0.2&0.5& & & \\ -0.3&0.2&0.5& & & \\ -0.7&0.6&0 & & & \\ - & & &0 &0.3&0.4\\ - & & &0.4&0 &0.6\\ - & & &0.6&0.7&0 -\end{pmatrix*} -\end{align*}}% -\uncover<5->{% -$P$ zerfällt in zwei Blöcke die unabhängig voneinander analysiert werden können -} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/markov.tex b/vorlesungen/slides/8/markov/markov.tex deleted file mode 100644 index e92ff0f..0000000 --- a/vorlesungen/slides/8/markov/markov.tex +++ /dev/null @@ -1,111 +0,0 @@ -% -% markov.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\bgroup -\setlength{\abovedisplayskip}{5pt} -\setlength{\belowdisplayskip}{5pt} -\begin{frame}[t] -\frametitle{Markovketten} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] - -\def\r{2.2} - -\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); -\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); -\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); -\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); -\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); - -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!40] - (A) -- (C); -\draw[color=white,line width=8pt] (B) -- (D); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!80] - (B) -- (D); - -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!60] - (A) -- (B); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!20] - (B) -- (C); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (C) -- (D); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (D) -- (E); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (E) -- (A); - -\fill[color=white] (A) circle[radius=0.2]; -\fill[color=white] (B) circle[radius=0.2]; -\fill[color=white] (C) circle[radius=0.2]; -\fill[color=white] (D) circle[radius=0.2]; -\fill[color=white] (E) circle[radius=0.2]; - -\draw (A) circle[radius=0.2]; -\draw (B) circle[radius=0.2]; -\draw (C) circle[radius=0.2]; -\draw (D) circle[radius=0.2]; -\draw (E) circle[radius=0.2]; - -\node at (A) {$1$}; -\node at (B) {$2$}; -\node at (C) {$3$}; -\node at (D) {$4$}; -\node at (E) {$5$}; - -\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 0.6$}; -\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 0.2$}; -\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 1$}; -\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 1$}; -\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 1$}; -\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 0.4$}; -\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 0.8$}; - -\end{tikzpicture} -\end{center} -\vspace{-10pt} -\uncover<7->{% -\begin{block}{Verteilung} -\begin{itemize} -\item<8-> -Welche stationäre Verteilung auf den Knoten stellt sich ein? -\item<9-> -$P(i)=?$ -\end{itemize} -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<2->{% -\begin{block}{\strut\mbox{Übergang\only<3->{s-/Wahrscheinlichkeit}smatrix}} -$P_{ij} = P(i | j)$, Wahrscheinlichkeit, in den Zustand $i$ überzugehen, -\begin{align*} -P -&= -\begin{pmatrix} - & & & &1\phantom{.0}\\ -0.6& & & & \\ -0.4&0.2& & & \\ - &0.8&1\phantom{.0}& & \\ - & & &1\phantom{.0}& -\end{pmatrix} -\end{align*} -\end{block}} -\vspace{-10pt} -\uncover<4->{% -\begin{block}{Eigenschaften} -\begin{itemize} -\item<5-> $P_{ij}\ge 0\;\forall i,j$ -\item<6-> Spaltensumme: -\( -\displaystyle -\sum_{i=1}^n P_{ij} = 1\;\forall j -\) -\end{itemize} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/pf.tex b/vorlesungen/slides/8/markov/pf.tex deleted file mode 100644 index da2ef2b..0000000 --- a/vorlesungen/slides/8/markov/pf.tex +++ /dev/null @@ -1,53 +0,0 @@ -% -% pf.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Perron-Frobenius-Theorie} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{block}{Positive Matrizen und Vektoren} -$P\in M_{m\times n}(\mathbb{R})$ -\begin{itemize} -\item<2-> -$P$ heisst positiv, $P>0$, wenn $p_{ij}>0\;\forall i,j$ -\item<3-> -$P\ge 0$, wenn $p_{ij}\ge 0\;\forall i,j$ -\end{itemize} -\end{block} -\uncover<4->{% -\begin{block}{Beispiele} -\begin{itemize} -\item<5-> -Adjazenzmatrix $A(G)$ -\item<6-> -Gradmatrix $D(G)$ -\item<7-> -Wahrscheinlichkeitsmatrizen -\end{itemize} -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<8->{% -\begin{block}{Satz} -Es gibt einen positiven Eigenvektor $p$ von $P$ zum Eigenwert $1$ -\end{block}} -\uncover<9->{% -\begin{block}{Satz} -$P$ irreduzible Matrix, $P\ge 0$, hat einen Eigenvektor $p$, $p\ge 0$, -zum Eigenwert $1$ -\end{block}} -\uncover<10->{% -\begin{block}{Potenzmethode} -Falls $P\ge 0$ einen eindeutigen Eigenvektor $p$ hat\uncover<11->{, -dann konveriert die rekursiv definierte Folge -\[ -p_{n+1}=\frac{Pp_n}{\|Pp_n\|}, p_0 \ge 0, p_0\ne 0 -\]}% -\uncover<12->{$\displaystyle\lim_{n\to\infty} p_n = p$} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/stationaer.tex b/vorlesungen/slides/8/markov/stationaer.tex deleted file mode 100644 index 92fab16..0000000 --- a/vorlesungen/slides/8/markov/stationaer.tex +++ /dev/null @@ -1,57 +0,0 @@ -% -% stationaer.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Stationäre Verteilung} -%\vspace{-15pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{block}{Zeitentwicklung} -\begin{itemize} -\item<2-> -$P$ eine Wahrscheinlichkeitsmatrix -\item<3-> -$p_0\in\mathbb{R}^n$ Verteilung zur Zeit $t=0$ bekannt -\item<4-> -$p_k\in\mathbb{R}^n$ Verteilung zur Zeit $t=k$ -\end{itemize} -\uncover<5->{% -Entwicklungsgesetz -\begin{align*} -P(i,t=k) -&= -\sum_{j=1}^n P_{ij} P(j,t=k-1) -\\ -\uncover<6->{ -p_k &= Pp_{k-1} -} -\end{align*}} -\end{block} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<7->{% -\begin{block}{Stationär} -Bedingung: $p_{k\mathstrut} = p_{k-1}$ -\uncover<8->{ -\begin{align*} -\Rightarrow -Pp &= p -\end{align*}}\uncover<9->{% -Eigenvektor zum Eigenwert $1$} -\end{block}} -\uncover<10->{% -\begin{block}{Fragen} -\begin{enumerate} -\item<11-> -Gibt es eine stationäre Verteilung? -\item<12-> -Gibt es einen Eigenvektor mit Einträgen $\ge 0$? -\item<13-> -Gibt es mehr als eine Verteilung? -\end{enumerate} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/spanningtree.tex b/vorlesungen/slides/8/spanningtree.tex new file mode 100644 index 0000000..425fe1c --- /dev/null +++ b/vorlesungen/slides/8/spanningtree.tex @@ -0,0 +1,164 @@ +% +% spanningtree.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\frametitle{Spannbäume} + +\vspace{-16pt} + +\begin{columns}[t] + +\begin{column}{0.40\hsize} +\begin{block}{Netzwerk} +Alle Knoten erreichen, Schleifen vermeiden $\Rightarrow$ Spannbaum +\vspace{-15pt} +\begin{center} +\begin{tikzpicture}[>=latex,scale=0.18] + +\coordinate (A) at ( 1.2927,-15.0076); +\coordinate (B) at ( 5.0261,- 7.7143); +\coordinate (C) at ( 4.9260,-13.0335); +\coordinate (D) at (12.2094,-22.9960); +\coordinate (F) at (17.8334,-13.4687); +\coordinate (G) at ( 6.4208,-10.2438); +\coordinate (H) at (17.2367,- 3.1047); +\coordinate (K) at (24.3760,- 3.0293); +\coordinate (L) at (23.2834,- 1.3563); +\coordinate (M) at (28.7093,- 4.0627); + +\fill (A) circle[radius=0.5]; +\fill (B) circle[radius=0.5]; +\fill (C) circle[radius=0.5]; +\fill (D) circle[radius=0.5]; +\fill (F) circle[radius=0.5]; +\fill (G) circle[radius=0.5]; +\fill (H) circle[radius=0.5]; +\fill (K) circle[radius=0.5]; +\fill (L) circle[radius=0.5]; +\fill (M) circle[radius=0.5]; + +%\uncover<1-4>{ +%\node at (A) [above] {$A$}; +%\node at (B) [above] {$B$}; +%\node at (C) [below] {$C$}; +%\node at (D) [below] {$D$}; +%\node at (F) [below right] {$F$}; +%\node at (G) [above] {$G$}; +%\node at (H) [above] {$H$}; +%\node at (K) [above right] {$K$}; +%\node at (L) [above] {$L$}; +%\node at (M) [above] {$M$}; +%} + +\uncover<5->{ +\node at (A) [above] {$1$}; +\node at (B) [above] {$2$}; +\node at (C) [below] {$3$}; +\node at (D) [below] {$4$}; +\node at (F) [below right] {$5$}; +\node at (G) [above] {$6$}; +\node at (H) [above] {$7$}; +\node at (K) [above right] {$8$}; +\node at (L) [above] {$9$}; +\node at (M) [above] {$10$}; +} + +\draw (L)--(H); +\draw (L)--(K); +\draw (L)--(M); + +\draw (H)--(B); +\draw (H)--(G); +\draw (H)--(F); +\draw (H)--(K); + +\draw (K)--(F); +\draw (K)--(M); + +\draw (M)--(F); +\draw (M)--(D); + +\draw (B)--(A); +\draw (B)--(C); +\draw (B)--(G); + +\draw (G)--(C); +\draw (G)--(F); + +\draw (F)--(D); + +\draw (C)--(F); +\draw (C)--(A); +\draw (C)--(D); + +\draw (A)--(D); + +\uncover<2>{ +\draw[line width=2pt,join=round] + (A)--(D)--(C)--(F)--(G)--(B)--(H)--(K)--(L)--(M); +} + +\uncover<3>{ +\draw[line width=2pt,join=round] + (M)--(D)--(A)--(C)--(G)--(B)--(H)--(L)--(K)--(F); +} + +\uncover<4->{ +\draw[line width=2pt] (M)--(K)--(L)--(H)--(F)--(D); +\draw[line width=2pt] (F)--(G)--(C)--(A); +\draw[line width=2pt] (G)--(B); +} + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +Wieviele Spannbäume gibt es? +\end{block} +\end{column} + +\begin{column}{0.56\hsize} +\uncover<5->{% +\begin{block}{Laplace-Matrix} +\vspace{-15pt} +\[ +L= +\tiny +\begin{pmatrix} + 3&-1&-1&-1& 0& 0& 0& 0& 0& 0\\ +-1& 4&-1& 0& 0&-1&-1& 0& 0& 0\\ +-1&-1& 5&-1&-1&-1& 0& 0& 0& 0\\ +-1& 0&-1& 4&-1& 0& 0& 0& 0&-1\\ + 0& 0&-1&-1& 6&-1&-1&-1& 0&-1\\ + 0&-1&-1& 0&-1& 4&-1& 0& 0& 0\\ + 0&-1& 0& 0&-1&-1& 5&-1&-1& 0\\ + 0& 0& 0& 0&-1& 0&-1& 4&-1&-1\\ + 0& 0& 0& 0& 0& 0&-1&-1& 3&-1\\ + 0& 0& 0&-1&-1& 0& 0&-1&-1& 4\\ +\end{pmatrix} +\] +\end{block}} +\vspace{-15pt} +\uncover<6->{% +\begin{block}{Satz von Kirchhoff} +Die Anzahl der Spannbäume eines Netzwerkes ist ein Kofaktor +des Laplaceoperators +\vspace{-5pt} +\[ +\det L_{ij} = +\left| +L\text{ ohne }\left\{\begin{array}{c}\text{Zeile $i$}\\\text{Spalte $j$}\end{array}\right. +\right| +\] +\end{block}} +\vspace{-12pt} +\uncover<7->{% +{\usebeamercolor[fg]{title}Beispiel:} 41524 +} + +\end{column} + +\end{columns} + +\end{frame} diff --git a/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg b/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg new file mode 100644 index 0000000..1c513da Binary files /dev/null and b/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg differ diff --git a/vorlesungen/slides/8/tokyo/tokyosubway.pdf b/vorlesungen/slides/8/tokyo/tokyosubway.pdf new file mode 100644 index 0000000..6b84a8d Binary files /dev/null and b/vorlesungen/slides/8/tokyo/tokyosubway.pdf differ diff --git a/vorlesungen/slides/8/tokyo/transportnetworkgraph.png b/vorlesungen/slides/8/tokyo/transportnetworkgraph.png new file mode 100644 index 0000000..4a11183 Binary files /dev/null and b/vorlesungen/slides/8/tokyo/transportnetworkgraph.png differ -- cgit v1.2.1