diff options
Diffstat (limited to 'vorlesungen/slides/8')
19 files changed, 1945 insertions, 11 deletions
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 Binary files differnew file mode 100644 index 0000000..cf4211d --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/burgerking.png 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 Binary files differnew file mode 100644 index 0000000..c442dfb --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/macdonalds.png 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 Binary files differnew file mode 100644 index 0000000..a28dbf7 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/starbucks.png 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 Binary files differnew file mode 100644 index 0000000..33aebe3 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg 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 |
