From d5941693bb5ceeb6d7f3178c42855cfb4fea1f59 Mon Sep 17 00:00:00 2001 From: Roy Seitz Date: Wed, 3 Feb 2021 14:17:05 +0100 Subject: Typos --- buch/chapters/70-graphen/beschreibung.tex | 31 ++++++++++++++++--------------- buch/chapters/70-graphen/chapter.tex | 9 +++++---- 2 files changed, 21 insertions(+), 19 deletions(-) (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index f027932..6e8e59b 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -17,7 +17,7 @@ dann Beziehungen zwischen diesen Objekten. \label{subsection:definition-von-graphen}} In der Einleitung zu diesem Abschnitt wurde bereits eine informelle Beschreibung des Konzeptes eines Graphen gegeben. -Um zu einer Beschreibung mit Hilfe von Matrizen kommen können, +Um zu einer Beschreibung mit Hilfe von Matrizen zu kommen, wird eine exakte Definition benötigt. Dabei werden sich einige Feinheiten zeigen, die für Anwendungen wichtig sind und sich in Unterschieden in der Definition der zugehörigen Matrix @@ -29,7 +29,7 @@ auch {\em Vertices} genannt. \index{Knoten}% \index{Vertex}% Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten -mit sogenannten die Kanten +mit sogenannten Kanten \index{Kante}% verbunden werden. Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante @@ -63,9 +63,10 @@ durch die Widerstände ab. Will man Spannungen und Ströme in einem solchen Netzwerk berechnen, ist auch das Fehlen von Schleifen, die von $a$ zu $a$ führen, kein Verlust. -Die Endpunkte solcher Widerstände wären immer auf gleichem Potential, -es würde daher kein Strom fliessen, sie haben daher keinen Einfluss auf -das Verhalten des Netzwerkes und können weggelassen werden. +Die Endpunkte solcher Widerstände wären immer auf dem gleichen Potential. +Folglich würde kein Strom fliessen und sie hätten keinen Einfluss auf +das Verhalten des Netzwerkes. +Sie können einfach weggelassen werden. \subsubsection{Gerichtete Graphen} In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar. @@ -98,7 +99,7 @@ In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung und die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll geworden. Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom -Knoten $a$ wieder zu $a$ zurückführen. +Knoten $a$ wieder zu $a$ zurückführt. Man kann einen ungerichteten Graphen in einen gerichteten Graphen verwandeln, indem wir jede Kante $\{a,b\}$ durch zwei Kanten @@ -115,11 +116,11 @@ E' \{a,e\}\in E \}. \end{equation*} -Eine umgekehrte Zuordnung eines ungerichteten Graphen zu einem gerichteten -Graphen ist nicht möglich, da eine ``Schleife'' $(a,a)$ nicht in Kante +Eine umgekehrte Zuordnung eines gerichteten zu einem ungerichteten +Graphen ist nicht möglich, da eine ``Schleife'' $(a,a)$ nicht in eine Kante des ungerichteten Graphen abgebildet werden kann. -In einem gerichteten Graphen kann man sinnvoll von gerichteten Pfad +In einem gerichteten Graphen kann man sinnvoll von gerichteten Pfaden sprechen. \index{Pfad}% Ein {\em Pfad} $\gamma$ in einem gerichteten Graphen $(V,E)$ ist eine Folge @@ -158,7 +159,7 @@ Der gerichtete Graph $([n],E)$ werde beschrieben durch die Matrix $G$. Dann gibt das Element in Zeile $j$ und Spalte $i$ von $G^n$ die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix} -formulieruen als in Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl +formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl der Pfade der Länge $1$, die $i$ mit $j$ verbinden. \end{satz} @@ -334,10 +335,10 @@ Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix} Knoten herstellt. Damit ist sie keine geeignete Grundlage, um beschriftete Graphen einer Matrixbeschreibung zuzuführen. -Eine solche muss eine Matrix verwenden, nicht nur das Vorhandensein einer +Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden Knoten miteinander verbindet. -Dies führt auf die sogenannte Ajazenz-Matrix. +Dies führt zur sogenannten Adjazenz-Matrix. \begin{definition} \label{buch:def:adjazenz-matrix} @@ -358,11 +359,11 @@ a_{ik} \end{equation} \end{definition} -Der wesentliche Unterschied dieser Definition von der Matrix $H$ +Der wesentliche Unterschied dieser Definition von der Matrix $G$ liegt in der Bedeutung der Einträge. -Für $H$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein +Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten -eine Kante endet. +eine Kante beginnt oder endet. Es ist natürlich möglich, aus der Adjazenz-Matrix auch die Link-Matrix zu rekonstruieren. diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index ae1bb9c..b6e02c9 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -14,18 +14,19 @@ aber auch viele andere Datenstrukturen. \index{Graph}% Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben dann Beziehungen zwischen diesen Objekten. -Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber als -erste Approximation auch dreidimensionaler Objekte dienen. +Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber auch als +erste Approximation dreidimensionaler Objekte dienen. Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl -von Fragestellungen, die über Graphen gestellt worden sind und der +von Fragestellungen, die über Graphen gestellt, und der zugehöriten Lösungsalgorithmen, die zu ihrer Beantwortung gefunden worden sind. Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete Problem in ein Graphenproblem umformulieren lässt. \index{Komplexitätstheorie}% + Das Problem, einen Stundenplan zu finden, der sicherstellt, dass -alle Studierenden an jedes Fach besuchen können, für die sie sich +alle Studierenden jedes Fach besuchen können, für die sie sich angemeldet haben, lässt sich zum Beispiel wie folgt als ein Graphenproblem formulieren. Die Fächer betrachten wir als Knoten des Graphen. -- cgit v1.2.1 From ada53a9c225b896c8d7608300427aac475bb7045 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 9 Feb 2021 21:52:16 +0100 Subject: move all iamges to separate files --- buch/chapters/70-graphen/beschreibung.tex | 21 +-------------- buch/chapters/70-graphen/images/Makefile | 10 +++++++ buch/chapters/70-graphen/images/peterson.pdf | Bin 0 -> 10833 bytes buch/chapters/70-graphen/images/peterson.tex | 38 +++++++++++++++++++++++++++ 4 files changed, 49 insertions(+), 20 deletions(-) create mode 100644 buch/chapters/70-graphen/images/Makefile create mode 100644 buch/chapters/70-graphen/images/peterson.pdf create mode 100644 buch/chapters/70-graphen/images/peterson.tex (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 6e8e59b..2dcc78f 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -236,26 +236,7 @@ sind. \begin{beispiel} \begin{figure} \centering -\begin{tikzpicture}[>=latex,thick] -\def\l{0.25} -\def\r{1} -\def\punkt#1{({\r*sin(((#1)-1)*72)},{\r*cos(((#1)-1)*72)})} -\def\R{2} -\def\Punkt#1{({\R*sin(((#1)-6)*72)},{\R*cos(((#1)-6)*72)})} -\draw \Punkt{6} -- \Punkt{7} -- \Punkt{8} -- \Punkt{9} -- \Punkt{10} -- cycle; -\draw \punkt{1} -- \punkt{3} -- \punkt{5} -- \punkt{2} -- \punkt{4} -- cycle; -\foreach \k in {1,...,5}{ - \draw \punkt{\k} -- \Punkt{(\k+5)}; - \fill[color=white] \punkt{\k} circle[radius=\l]; - \node at \punkt{\k} {$\k$}; - \draw \punkt{\k} circle[radius=\l]; -} -\foreach \k in {6,...,10}{ - \fill[color=white] \Punkt{\k} circle[radius=\l]; - \node at \Punkt{\k} {$\k$}; - \draw \Punkt{\k} circle[radius=\l]; -} -\end{tikzpicture} +\includegraphics{chapters/70-graphen/images/peterson.pdf} \caption{Peterson-Graph mit zehn Knoten. \label{buch:figure:peterson}} \end{figure} diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile new file mode 100644 index 0000000..2199ddc --- /dev/null +++ b/buch/chapters/70-graphen/images/Makefile @@ -0,0 +1,10 @@ +# +# Makefile -- Bilder für Kapitel Graphen +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: peterson.pdf + +peterson.pdf: peterson.tex + pdflatex peterson.tex + diff --git a/buch/chapters/70-graphen/images/peterson.pdf b/buch/chapters/70-graphen/images/peterson.pdf new file mode 100644 index 0000000..259d808 Binary files /dev/null and b/buch/chapters/70-graphen/images/peterson.pdf differ diff --git a/buch/chapters/70-graphen/images/peterson.tex b/buch/chapters/70-graphen/images/peterson.tex new file mode 100644 index 0000000..c0af98b --- /dev/null +++ b/buch/chapters/70-graphen/images/peterson.tex @@ -0,0 +1,38 @@ +% +% tikztemplate.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\l{0.25} +\def\r{1} +\def\punkt#1{({\r*sin(((#1)-1)*72)},{\r*cos(((#1)-1)*72)})} +\def\R{2} +\def\Punkt#1{({\R*sin(((#1)-6)*72)},{\R*cos(((#1)-6)*72)})} +\draw \Punkt{6} -- \Punkt{7} -- \Punkt{8} -- \Punkt{9} -- \Punkt{10} -- cycle; +\draw \punkt{1} -- \punkt{3} -- \punkt{5} -- \punkt{2} -- \punkt{4} -- cycle; +\foreach \k in {1,...,5}{ + \draw \punkt{\k} -- \Punkt{(\k+5)}; + \fill[color=white] \punkt{\k} circle[radius=\l]; + \node at \punkt{\k} {$\k$}; + \draw \punkt{\k} circle[radius=\l]; +} +\foreach \k in {6,...,10}{ + \fill[color=white] \Punkt{\k} circle[radius=\l]; + \node at \Punkt{\k} {$\k$}; + \draw \Punkt{\k} circle[radius=\l]; +} + +\end{tikzpicture} +\end{document} + -- cgit v1.2.1 From b8f090eb8c7b621a98fc58ce50d0af1fe246f684 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 16:37:34 +0100 Subject: add new graph --- buch/chapters/70-graphen/beschreibung.tex | 199 +++++++++++++++++++++----- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/adjazenzu.pdf | Bin 0 -> 19952 bytes buch/chapters/70-graphen/images/adjazenzu.tex | 87 +++++++++++ 4 files changed, 251 insertions(+), 40 deletions(-) create mode 100644 buch/chapters/70-graphen/images/adjazenzu.pdf create mode 100644 buch/chapters/70-graphen/images/adjazenzu.tex (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 2dcc78f..174102a 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -130,14 +130,36 @@ Dies bedeutet, dass der Endpunkt jeder Kante mit dem Anfangspunkt der nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. -Eine naheliegende Beschreibung eines gerichteten Graphen mit Hilfe einer +\subsubsection{Adjazenzmatrix} +Eine naheliegende Beschreibung eines Graphen mit Hilfe einer Matrix kann man wie folgt erhalten. Zunächst werden die Knoten aus der Menge $V$ durch die Zahlen $1,\dots,n$ mit $n=|V|$ ersetzt. Diese Zahlen werden dann als Zeilen- uns Spaltenindizes interpretiert. -Die zum Graphen gehörige Matrix enthält die Einträge +Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$ +enthält die Einträge \begin{equation} -g_{ij} +a_{ij} += +\begin{cases} +1&\qquad \{j,i\} \in E\\ +0&\qquad \text{sonst.} +\end{cases} +\label{buch:graphen:eqn:linkmatrix} +\end{equation} +Die Matrix hat also genau dann einen von Null verschiedenen Eintrag +in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$ +im Graphen verbunden sind. +Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch. + +Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert +werden. +Ihre Einträge sind in diesem Fall definiert mit Hilfe der +gerichteten Kanten als +\begin{equation} +A(G)_{ij} += +a_{ij} = \begin{cases} 1&\qquad (j,i) \in E\\ @@ -145,18 +167,22 @@ g_{ij} \end{cases} \label{buch:graphen:eqn:linkmatrix} \end{equation} -Die Matrix $G$ hat also genau dann einen nicht verschwindenden +Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung von Knoten $j$ zu Knoten $i$ gibt. + % XXX Abbildung Graph und Verbindungs-Matrix -Die Beschreibung des Graphen mit der Matrix $G$ nach + +\subsubsection{Adjazenzmatrix und die Anzahl der Pfade} +Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach \eqref{buch:graphen:eqn:linkmatrix} ermöglicht bereits, eine interessante Aufgabe zu lösen. \begin{satz} \label{buch:graphen:pfade-der-laenge-n} -Der gerichtete Graph $([n],E)$ werde beschrieben durch die Matrix $G$. -Dann gibt das Element in Zeile $j$ und Spalte $i$ von $G^n$ die Anzahl +Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix +$A=A(G)$. +Dann gibt das Element in Zeile $j$ und Spalte $i$ von $A^n$ die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix} formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl @@ -164,57 +190,49 @@ der Pfade der Länge $1$, die $i$ mit $j$ verbinden. \end{satz} \begin{proof}[Beweis] -Es ist klar, dass $G^1$ die genannte Eigenschaft hat. -Wir beweisen, dass $G^n$ Pfade der Länge $n$ zählt, mit Hilfe von +Es ist klar, dass $A^1$ die genannte Eigenschaft hat. +Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von vollständiger Induktion. -Zur Unterscheidung schreiben wir $G^{(n)}$ für die Matrix, die in Zeile +Zur Unterscheidung schreiben wir $A^{(n)}$ für die Matrix, die in Zeile $j$ und Spalte $i$ die Anzahl der Pfade der Länge $n$ von $i$ nach $j$ enhält. -Die zugehörigen Matrixelemente schreiben wir $g_{ji}^{n}$ bzw.~$g_{ji}^{(n)}$. -Wir haben also zu zeigen, dass $G^n = G^{(n)}$. +Die zugehörigen Matrixelemente schreiben wir $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$. +Wir haben also zu zeigen, dass $A^n = A^{(n)}$. Wir nehmen daher an, dass bereits bewiesen ist, dass das Element in Zeile -$j$ und Spalte $i$ von $G^{n-1}$ die Anzahl der Pfade der Länge $n-1$ -zählt, dass also $G^{n-1}=G^{(n-1)}$. +$j$ und Spalte $i$ von $A^{n-1}$ die Anzahl der Pfade der Länge $n-1$ +zählt, dass also $A^{n-1}=A^{(n-1)}$. Dies ist die Induktionsannahme. Wir bilden jetzt alle Pfade der Länge $n$ von $i$ nach $k$. Ein Pfad der Länge besteht aus einem Pfad der Länge $n-1$, der von $i$ zu einem beliebigen Knoten $j$ führt, gefolgt von einer einzelnen Kante, die von $j$ nach $k$ führt. -Ob es eine solche Kante gibt, zeigt das Matrixelement $g_{kj}$ an. -Das Element in Zeile $j$ und Spalte $i$ der Matrix $G^{(n-1)}$ gibt +Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{kj}$ an. +Das Element in Zeile $j$ und Spalte $i$ der Matrix $A^{(n-1)}$ gibt die Anzahl der Wege von $i$ nach $j$ an. -Es gibt also $g_{kj}\cdot g_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ +Es gibt also $a_{kj}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ nach $k$ führen, aber als zweitletzten Knoten über den Knoten $j$ führen. Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher \[ -g_{ki}^{(n)} +a_{ki}^{(n)} = -\sum_{j=1}^n g_{kj} g_{ji}^{(n-1)}. +\sum_{j=1}^n a_{kj} a_{ji}^{(n-1)}. \] In Matrixschreibweise bedeutet dies \[ -G^{(n)} +A^{(n)} = -G\cdot G^{(n-1)} +A\cdot A^{(n-1)} = -G\cdot G^{n-1} +A\cdot A^{n-1} = -G^n. +A^n. \] Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme verwendet. \end{proof} -Die Definition~\eqref{buch:graphen:eqn:linkmatrix} der Matrix, die den -Graphen beschreibt, lässt sich natürlich auch auf einen ungerichteten -Graphen verallgemeinern. -Die entstehende Matrix hat dann aber die zusätzlichen Eigenschaften, dass -alle Diagonalelemente $0$ sind und dass die Matrix symmetrisch ist. -Auch im Fall eines ungerichteten Graphen kann die Matrix dazu verwendet -werden, die Anzahl der Pfade zu zählen. - Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren. @@ -226,11 +244,11 @@ es zwischen zwei beliebigen Knoten einen Pfad der Länge $\le d$ gibt. \end{definition} Der Durchmesser $d$ eines Graphen ist der kleinste Exponent derart, -dass $G^d$ keine ausserdiagonalen Einträge $0$ hat. -Die Diagonalelemente von $G^n$ zählen die Anzahl der geschlossenen Pfade +dass $A^d$ keine ausserdiagonalen Einträge $0$ hat. +Die Diagonalelemente von $A^n$ zählen die Anzahl der geschlossenen Pfade der Länge $n$, die durch einen Knoten führen. Diese können für den Durchmesser ignoriert werden. -Man kann also Potenzen $G^n$ berechnen bis keine Einträge $0$ mehr vorhanden +Man kann also Potenzen $A^n$ berechnen bis keine Einträge $0$ mehr vorhanden sind. \begin{beispiel} @@ -240,7 +258,7 @@ sind. \caption{Peterson-Graph mit zehn Knoten. \label{buch:figure:peterson}} \end{figure} -Der Peterson-Graph hat die Matrix +Der Peterson-Graph hat die Adjazenzmatrix \[ G = @@ -309,7 +327,110 @@ eines gerichteten oder ungerichteten Graphen $G=(V,E)$ ist eine Abbildung $l\colon E\to L$. \end{definition} -\subsection{Die Adjazenz-Matrix und Laplace-Matrix +\subsection{Inzidenzmatrix} +Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise +mit den Kanten verbunden ist, nicht mehr darstellen. +Dies tritt zum Beispiel in der Informatik bei der Beschreibung +endlicher Automaten auf, wo zu jeder gerichteten Kante auch noch +Buchstaben gehören, für die der Übergang entlang dieser Kante +möglich ist. + +Die {\em Inzidenzmatrix} löst dieses Problem. +Dazu werden zunächst die Kanten numeriert $1,\dots,m$ +numeriert. +Die Matrixeinträge +\[ +a_{ij} = \begin{cases} +1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} +\\ +0\qquad&\text{sonst} +\end{cases} +\] +stellen die Beziehung zwischen Kanten und Knoten her. + +\subsubsection{Beschriftete Graphen} +Die Inzidenzmatrix kann auch einen erweiterten Graphenbegriff abbilden, +in dem zwischen zwei Kanten mehrere Verbindungen möglich sind. +Graphen mit beschrifteten Kanten gehören dazu. + +\begin{definition} +Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von +Knoten und eine Menge von beschrifteten Kanten der Form +\[ +E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}. +\] +\end{definition} + +Für einen gerichteten Graphen wird in der Inzidenzmatrix für +den Anfangspunkt einer Kante $-1$ eingetragen und für den +Endpunkt $+1$. +% XXX Beispiel + +\subsubsection{Inzidenzmatrix und Adjazenzmatrix} +Sei $B(G)$ die Inzidenzmatrix eines Graphen $G$. +Die Spalten von $B(G)$ sind mit den Kanten des Graphen indiziert. +Die Matrix $B(G)B(G)^t$ ist eine quadratische Matrix, deren +Zeilen und Spalten mit den Knoten des Graphen indiziert sind. +In dieser Matrix geht die Informatione über die individuellen +Kanten wieder verloren. +Sie hat für $i\ne j$ die Einträge +\begin{align*} +(B(G)B(G)^t)_{ij} +&= +\sum_{\text{$k$ Kante}} b_{ik}b_{jk} +\\ +&=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden} +\\ +&=a_{ij} +\end{align*} +Die Adjazenzmatrix eines Graphen lässt sich also aus der +Inzidenzmatrix berechnen. + +\subsubsection{Gradmatrix} +Die Diagonale von $B(G)B(G)^t$ enthält die Werte +\begin{align*} +(B(G)B(G)^t)_{ii} +&= +\sum_{\text{$k$ Kante}} b_{ik}^2 += +\text{Anzahl Kanten, die im Knoten $i$ enden} +\end{align*} +Der {\em Grad} eines Knoten eines Graphen ist die Anzahl der +\index{Grad eines Knotens}% +Kanten, die in diesem Knoten enden. +Die Diagonalmatrix die aus den Graden der Knoten besteht, heisst die +Gradmatrix $D(G)$ des Graphen. +Es gilt daher $B(G)B(G)^t = A(G) + D(G)$. + +\subsubsection{Gerichtete Graphen} +Für einen gerichteten Graphen ändert sich an der Diagonalen +der Matrix $B(G)B(G)^t$ nichts. +Da es in einem gerichteten Graphen nur eine einzige Kante $k$ gibt, die zwei +Knoten $i$ und $j$ verbinden kann, muss das zugehörige +Ausserdiagonalelement +\[ +a_{ij} +=b_{ik}b_{jk} += +-1 +\] +sein. +Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente +negativ und es gilt $B(G)B(G)^t = D(G)-A(G)$. + +\subsubsection{Anwendung: Netlist} +Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen +ist eine eletronische Schaltung. +Die Knoten des Graphen sind untereinander verbundene Leiter, sie werden +auch {\em nets} genannt. +Die beschrifteten Kanten sind die elektronischen Bauteile, die solche +Nets miteinander verbinden. +Die Inzidenzmatrix beschreibt, welche Anschlüsse eines Bauteils mit +welchen Nets verbunden werden müssen. +Die Informationen in der Inzidenzmatrix werden also in einer +Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben. + +\subsection{Die Adjazenzmatrix und Laplace-Matrix \label{subsection:adjazenz-und-laplace-matrix}} Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix} ``vergisst'' den ``Namen'' der Kante, die eine Verbindung zwischen zwei @@ -319,12 +440,12 @@ Matrixbeschreibung zuzuführen. Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden Knoten miteinander verbindet. -Dies führt zur sogenannten Adjazenz-Matrix. +Dies führt zur sogenannten Adjazenzmatrix. \begin{definition} \label{buch:def:adjazenz-matrix} Ist $G=(V,E)$ ein gerichteter Graph mit $n=|G|$ Vertizes und $m=|E|$ Kanten, -dann ist die zugehörige {\em Adjazenz-Matrix} $A=A(G)$ eine $n\times m$-Matrix. +dann ist die zugehörige {\em Adjazenzmatrix} $A=A(G)$ eine $n\times m$-Matrix. In der Spalte $k$ wird der Anfangspunkt der Kante $k$ mit $-1$, der Endpunkt mit $+1$ angezeigt, die übrigen Einträge sind $0$. $A$ hat also die Matrixelemente @@ -346,7 +467,7 @@ Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten eine Kante beginnt oder endet. -Es ist natürlich möglich, aus der Adjazenz-Matrix auch die Link-Matrix +Es ist natürlich möglich, aus der Adjazenzmatrix auch die Link-Matrix zu rekonstruieren. Dazu muss für jedes Paar $(j,i)$ von Knoten festgestellt werden, ob die Adjazenzmatrix eine entsprechende Verbindung enthält, also ob der diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index 2199ddc..9e61446 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,8 +3,11 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf +all: peterson.pdf adjazenzu.pdf peterson.pdf: peterson.tex pdflatex peterson.tex +adjazenzu.pdf: adjazenzu.tex + pdflatex adjazenzu.tex + diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf new file mode 100644 index 0000000..c24335a Binary files /dev/null and b/buch/chapters/70-graphen/images/adjazenzu.pdf differ diff --git a/buch/chapters/70-graphen/images/adjazenzu.tex b/buch/chapters/70-graphen/images/adjazenzu.tex new file mode 100644 index 0000000..29e094f --- /dev/null +++ b/buch/chapters/70-graphen/images/adjazenzu.tex @@ -0,0 +1,87 @@ +% +% adjazenzu.tex -- Adjazenz-Matrix für einen ungerichten Graphen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\r{1.8} + +\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)}); + +\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)$) [above right] {$1$}; +\node at ($0.5*(B)+0.5*(C)$) [above left] {$2$}; +\node at ($0.5*(C)+0.5*(D)$) [left] {$3$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$4$}; +\node at ($0.5*(E)+0.5*(A)$) [below right] {$5$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$6$}; +\node at ($0.4*(B)+0.6*(D)$) [left] {$7$}; + +\end{scope} + +\begin{scope}[xshift=3cm,yshift=-1.1cm] +\node at (0,0) [right] {$\displaystyle +B(G) += +\begin{pmatrix} +1&0&0&0&1&0&0\\ +1&1&0&0&0&1&0\\ +0&1&1&0&0&0&1\\ +0&0&1&1&0&1&0\\ +0&0&0&1&1&0&1 +\end{pmatrix}$}; +\end{scope} + +\begin{scope}[xshift=3cm,yshift=1.1cm] +\node at (0,0) [right] {$\displaystyle +A(G) += +\begin{pmatrix} +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{scope} + +\end{tikzpicture} +\end{document} + -- cgit v1.2.1 From 1cc24c040d12a725be56d4439d87f1201ff72be1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 16:41:10 +0100 Subject: Abbildung Graph mit Adj/Inz --- buch/chapters/70-graphen/beschreibung.tex | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 174102a..70dc296 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -131,6 +131,13 @@ nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. \subsubsection{Adjazenzmatrix} +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/adjazenzu.pdf} +\caption{Adjazenz- und Inzidenzmatrix eines ungerichteten +Graphen mit $5$ Knoten und $7$ Kanten. +\label{buch:graphen:fig:adjazenzu}} +\end{figure} Eine naheliegende Beschreibung eines Graphen mit Hilfe einer Matrix kann man wie folgt erhalten. Zunächst werden die Knoten aus der Menge $V$ durch die Zahlen @@ -151,6 +158,8 @@ Die Matrix hat also genau dann einen von Null verschiedenen Eintrag in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$ im Graphen verbunden sind. Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch. +Ein Beispiel ist in Abbildung~\ref{buch:graphen:fig:adjazenzu} +dargestellt. Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert werden. -- cgit v1.2.1 From 4e04665947e8b2e625dc53ba7c597171e7d9de7d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 19:20:23 +0100 Subject: add new images --- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/adjazenzd.pdf | Bin 0 -> 23490 bytes buch/chapters/70-graphen/images/adjazenzd.tex | 100 ++++++++++++++++++++++++++ buch/chapters/70-graphen/images/adjazenzu.pdf | Bin 19952 -> 21744 bytes buch/chapters/70-graphen/images/adjazenzu.tex | 27 ++++--- 5 files changed, 123 insertions(+), 9 deletions(-) create mode 100644 buch/chapters/70-graphen/images/adjazenzd.pdf create mode 100644 buch/chapters/70-graphen/images/adjazenzd.tex (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index 9e61446..529f314 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,7 +3,7 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf adjazenzu.pdf +all: peterson.pdf adjazenzu.pdf adjazenzd.pdf peterson.pdf: peterson.tex pdflatex peterson.tex @@ -11,3 +11,6 @@ peterson.pdf: peterson.tex adjazenzu.pdf: adjazenzu.tex pdflatex adjazenzu.tex +adjazenzd.pdf: adjazenzd.tex + pdflatex adjazenzd.tex + diff --git a/buch/chapters/70-graphen/images/adjazenzd.pdf b/buch/chapters/70-graphen/images/adjazenzd.pdf new file mode 100644 index 0000000..dc3dd8f Binary files /dev/null and b/buch/chapters/70-graphen/images/adjazenzd.pdf differ diff --git a/buch/chapters/70-graphen/images/adjazenzd.tex b/buch/chapters/70-graphen/images/adjazenzd.tex new file mode 100644 index 0000000..5cef18e --- /dev/null +++ b/buch/chapters/70-graphen/images/adjazenzd.tex @@ -0,0 +1,100 @@ +% +% adjazenzd.tex -- Adjazenz-Matrix für einen gerichten Graphen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\r{1.8} + +\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)}); + +\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{scope} + +\begin{scope}[xshift=3cm,yshift=-1.1cm] +\node at (0,0) [right] {$\displaystyle +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*}$}; +\end{scope} + +\begin{scope}[xshift=3cm,yshift=1.1cm] +\node at (0,0) [right] {$\displaystyle +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*}, +\quad +D(G) += +\begin{pmatrix*}[r] +3&0&0&0&0\\ +0&3&0&0&0\\ +0&0&3&0&0\\ +0&0&0&3&0\\ +0&0&0&0&1 +\end{pmatrix*} +$}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf index c24335a..d3f255e 100644 Binary files a/buch/chapters/70-graphen/images/adjazenzu.pdf and b/buch/chapters/70-graphen/images/adjazenzu.pdf differ diff --git a/buch/chapters/70-graphen/images/adjazenzu.tex b/buch/chapters/70-graphen/images/adjazenzu.tex index 29e094f..b6d129d 100644 --- a/buch/chapters/70-graphen/images/adjazenzu.tex +++ b/buch/chapters/70-graphen/images/adjazenzu.tex @@ -46,13 +46,13 @@ \node at (E) {$5$}; \node at (0,0) {$G$}; -\node at ($0.5*(A)+0.5*(B)$) [above right] {$1$}; -\node at ($0.5*(B)+0.5*(C)$) [above left] {$2$}; -\node at ($0.5*(C)+0.5*(D)$) [left] {$3$}; -\node at ($0.5*(D)+0.5*(E)$) [below] {$4$}; -\node at ($0.5*(E)+0.5*(A)$) [below right] {$5$}; -\node at ($0.6*(A)+0.4*(C)$) [above] {$6$}; -\node at ($0.4*(B)+0.6*(D)$) [left] {$7$}; +\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{scope} @@ -79,7 +79,18 @@ A(G) 1&1&0&1&0\\ 0&1&1&0&1\\ 1&0&0&1&0 -\end{pmatrix}$}; +\end{pmatrix}, +\quad +D(G) += +\begin{pmatrix} +3&0&0&0&0\\ +0&3&0&0&0\\ +0&0&3&0&0\\ +0&0&0&3&0\\ +0&0&0&0&2 +\end{pmatrix} +$}; \end{scope} \end{tikzpicture} -- cgit v1.2.1 From d2fecb0eeb3854c999108aa224cdcd260bed7ef0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 20:41:15 +0100 Subject: =?UTF-8?q?Beispiele=20von=20Basen=20f=C3=BCr=20Wavelets=20auf=20G?= =?UTF-8?q?raphen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/70-graphen/beschreibung.tex | 16 +++- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/kreis.pdf | Bin 0 -> 23540 bytes buch/chapters/70-graphen/images/kreis.tex | 47 +++++++++++ buch/chapters/70-graphen/wavelets.tex | 125 ++++++++++++++++++++++++++++++ 5 files changed, 190 insertions(+), 3 deletions(-) create mode 100644 buch/chapters/70-graphen/images/kreis.pdf create mode 100644 buch/chapters/70-graphen/images/kreis.tex (limited to 'buch/chapters/70-graphen') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 70dc296..25cfcc0 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -134,7 +134,7 @@ Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. \begin{figure} \centering \includegraphics{chapters/70-graphen/images/adjazenzu.pdf} -\caption{Adjazenz- und Inzidenzmatrix eines ungerichteten +\caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten Graphen mit $5$ Knoten und $7$ Kanten. \label{buch:graphen:fig:adjazenzu}} \end{figure} @@ -161,8 +161,16 @@ Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch. Ein Beispiel ist in Abbildung~\ref{buch:graphen:fig:adjazenzu} dargestellt. +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/adjazenzd.pdf} +\caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten +Graphen mit $5$ Knoten und $7$ Kanten. +\label{buch:graphen:fig:adjazenzd}} +\end{figure} Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert -werden. +werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzu} +illustriert ist. Ihre Einträge sind in diesem Fall definiert mit Hilfe der gerichteten Kanten als \begin{equation} @@ -334,6 +342,7 @@ Dies ist, was eine Beschriftung einer Kante bewerkstelligt. Eine Beschriftung mit Elementen der Menge $L$ eines gerichteten oder ungerichteten Graphen $G=(V,E)$ ist eine Abbildung $l\colon E\to L$. +\index{Beschriftung}% \end{definition} \subsection{Inzidenzmatrix} @@ -345,6 +354,7 @@ Buchstaben gehören, für die der Übergang entlang dieser Kante möglich ist. Die {\em Inzidenzmatrix} löst dieses Problem. +\index{Inzidenzmatrix}% Dazu werden zunächst die Kanten numeriert $1,\dots,m$ numeriert. Die Matrixeinträge @@ -368,6 +378,7 @@ Knoten und eine Menge von beschrifteten Kanten der Form \[ E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}. \] +Die Menge $L$ enthält die möglichen Beschriftungen der Kanten. \end{definition} Für einen gerichteten Graphen wird in der Inzidenzmatrix für @@ -396,6 +407,7 @@ Die Adjazenzmatrix eines Graphen lässt sich also aus der Inzidenzmatrix berechnen. \subsubsection{Gradmatrix} +\index{Gradmatrix}% Die Diagonale von $B(G)B(G)^t$ enthält die Werte \begin{align*} (B(G)B(G)^t)_{ii} diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index 529f314..b42cbae 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,7 +3,7 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf adjazenzu.pdf adjazenzd.pdf +all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf peterson.pdf: peterson.tex pdflatex peterson.tex @@ -14,3 +14,6 @@ adjazenzu.pdf: adjazenzu.tex adjazenzd.pdf: adjazenzd.tex pdflatex adjazenzd.tex +kreis.pdf: kreis.tex + pdflatex kreis.tex + diff --git a/buch/chapters/70-graphen/images/kreis.pdf b/buch/chapters/70-graphen/images/kreis.pdf new file mode 100644 index 0000000..f7ed37a Binary files /dev/null and b/buch/chapters/70-graphen/images/kreis.pdf differ diff --git a/buch/chapters/70-graphen/images/kreis.tex b/buch/chapters/70-graphen/images/kreis.tex new file mode 100644 index 0000000..a926839 --- /dev/null +++ b/buch/chapters/70-graphen/images/kreis.tex @@ -0,0 +1,47 @@ +% +% tikztemplate.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{mathtools} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\r{3} + +\foreach \w in {0,20,...,340}{ + \draw (\w:\r) circle[radius=0.2]; + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (\w:\r) -- ({\w+20}:\r); +} + +\foreach \x in {1,...,15}{ + \node at ({20*(\x-1)}:\r) {$\scriptstyle \x$}; +} +\node at (340:\r) {$\scriptstyle n$}; +\node at (320:\r) {$\scriptstyle \dots$}; +\node at (300:\r) {$\scriptstyle \dots$}; + +\begin{scope}[xshift=4cm] +\node at (0,0) [right] {$\displaystyle +L=\begin{pmatrix*}[r] + 2&-1& 0& 0&\dots& 0&-1\\ +-1& 2&-1& 0&\dots& 0& 0\\ + 0&-1& 2&-1&\dots& 0& 0\\ + 0& 0&-1& 2&\dots& 0& 0\\ +\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ + 0& 0& 0& 0&\dots& 2&-1\\ +-1& 0& 0& 0&\dots&-1& 2 +\end{pmatrix*}$}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 6a4876a..0739f14 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -6,3 +6,128 @@ \section{Wavelets auf Graphen \label{buch:section:wavelets-auf-graphen}} \rhead{Wavelets auf Graphen} +Graphen werden oft verwendet um geometrische Objekte zu approximieren. +Funktionen auf einem Graphen können dann Approximationen von physikalischen +Grössen wie zum Beispiel der Temperatur auf dem geometrischen Objekt +interpretiert werden. +Verschiedene Basen für die Beschreibung solcher Funktionen sind im Laufe +der Zeit verwendet worden, doch Wavelets auf einem Graphen sind eine +neuere Idee, mit der man aus der Laplace-Matrix Basen gewinnen kann, +die die Idee von langsam sich ausbreitenden Störungen besonders gut +wiederzugeben in der Lage sind. + +In diesem Abschnitt werden erst Funktionen auf einem Graphen genauer +definiert. +In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} +wird die Eigenbasis mit dem Laplace-Operator konstruiert und mit +der Standarbasis verglichen. +Schliesslich werden in Abschnitt~\ref{buch:subsection:wavelet-basen} +verschiedene Wavelet-Basen konstruiert. + +\subsection{Funktionen auf einem Graphen und die Laplace-Matrix} +Sei $G$ ein Graph mit der Knotenmenge $V$. +Eine Funktion $f$ auf einem Graphen ist eine Funktion $f\colon V\to\mathbb{R}$. +Funktionen auf $G$ sind also Vektoren, die mit den Knoten $V$ indiziert +sind. + +Es gibt auch ein Skalarprodukt für Funktionen auf dem Graphen. +Sind $f$ und $g$ zwei Funktionen auf $G$, dann ist das Skalarprodukt +definiert durch +\[ +\langle f,g\rangle += +\frac{1}{|V|}\sum_{v\in V} \overline{f}(v) g(v) +\] +Dies ist das bekannte Skalarprodukt der Vektoren mit Komponenten $f(v)$. + +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/kreis.pdf} +\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem +Graphen. +\label{buch:graphen:fig:kreis}} +\end{figure} +\begin{beispiel} +Wir illustrieren die im folgenden entwickelte Theorie an dem Beispielgraphen +von Abbildung~\ref{buch:graphen:fig:kreis}. +Besonders interessant sind die folgenden Funktionen: +\[ +\left. +\begin{aligned} +s_m(k) +&= +\sin\frac{2\pi mk}{n} +\\ +c_m(k) +&= +\cos\frac{2\pi mk}{n} +\end{aligned} +\; +\right\} +\quad +\Rightarrow +\quad +e_m(k) += +e^{2\pi imk/n} += +c_m(k) + is_m(k). +\] +Das Skalarprodukt dieser Funktionen ist +\[ +\langle e_m, e_{m'}\rangle += +\frac1n +\sum_{k=1}^n +\overline{e^{2\pi i km/n}} +e^{2\pi ikm'/n} += +\frac1n +\sum_{k=1}^n +e^{\frac{2\pi i}{n}(m'-m)k} += +\delta_{mm'} +\] +Die Funktionen bilden daher eine Orthonormalbasis des Raums der +Funktionen auf $G$. +Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$ +die Funktionen +\[ +c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2} +\] +eine orthonormierte Basis. +\end{beispiel} + + +Die Laplace-Matrix kann mit der folgenden Definition zu einer linearen +Abbildung auf Funktionen auf dem Graphen gemacht werden. +Sei $f\colon V\to \mathbb{R}$ und $L$ die Laplace-Matrix mit +Matrixelementen $l_{vv'}$ wobei $v,v'\in V$ ist. +Dann definieren wir die Funktion $Lf$ durch +\[ +(Lf)(v) += +\sum_{v'\in V} l_{vv'}f(v'). +\] + +\subsection{Standardbasis und Eigenbasis +\label{buch:subsection:standardbasis-und-eigenbasis}} +Die einfachste Basis, aus der siche Funktionen auf dem Graphen linear +kombinieren lassen, ist die Standardbasis. +Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten +\[ +e_v\colon V\to\mathbb R:v'\mapsto \begin{cases} +1\qquad&v=v'\\ +0\qquad&\text{sonst.} +\end{cases} +\] + + +\subsection{Wavelet-Basen +\label{buch:subsection:wavelet-basen}} + + + + + + -- cgit v1.2.1