diff options
Diffstat (limited to 'vorlesungen/slides/8')
| -rw-r--r-- | vorlesungen/slides/8/Makefile.inc | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/8/chapter.tex | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/8/grad.tex | 84 | ||||
| -rw-r--r-- | vorlesungen/slides/8/inzidenz.tex | 131 |
4 files changed, 219 insertions, 0 deletions
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 |