blob: 8c0dd0d6867d5db5bb8d5830cfd50a9080cba235 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
|
