From 8c5d6d7b31f052bd90010a0ed182ac6468c10bc4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 24 May 2021 09:41:46 +0200 Subject: abschnitt spektrale Graphentheorie --- buch/chapters/70-graphen/Makefile.inc | 1 + buch/chapters/70-graphen/chapter.tex | 1 + buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/petersonchrind.pdf | Bin 0 -> 15217 bytes buch/chapters/70-graphen/images/petersonchrind.tex | 142 +++++++++++ buch/chapters/70-graphen/spektral.tex | 269 ++++++++------------- buch/chapters/70-graphen/waerme.tex | 184 ++++++++++++++ 7 files changed, 434 insertions(+), 168 deletions(-) create mode 100644 buch/chapters/70-graphen/images/petersonchrind.pdf create mode 100644 buch/chapters/70-graphen/images/petersonchrind.tex create mode 100644 buch/chapters/70-graphen/waerme.tex (limited to 'buch') diff --git a/buch/chapters/70-graphen/Makefile.inc b/buch/chapters/70-graphen/Makefile.inc index d8fe742..2a7d9a6 100644 --- a/buch/chapters/70-graphen/Makefile.inc +++ b/buch/chapters/70-graphen/Makefile.inc @@ -7,5 +7,6 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/70-graphen/beschreibung.tex \ chapters/70-graphen/spektral.tex \ + chapters/70-graphen/waerme.tex \ chapters/70-graphen/wavelets.tex \ chapters/70-graphen/chapter.tex diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index b6e02c9..6def393 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -65,5 +65,6 @@ Basis zur Beschreibung von Funktionen auf dem Graphen. \input{chapters/70-graphen/beschreibung.tex} \input{chapters/70-graphen/spektral.tex} +\input{chapters/70-graphen/waerme.tex} \input{chapters/70-graphen/wavelets.tex} diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index bd77756..8f98134 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,11 +3,14 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf +all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf \ + petersonchrind.pdf peterson.pdf: peterson.tex pdflatex peterson.tex +petersonchrind.pdf: petersonchrind.tex + pdflatex petersonchrind.tex adjazenzu.pdf: adjazenzu.tex pdflatex adjazenzu.tex diff --git a/buch/chapters/70-graphen/images/petersonchrind.pdf b/buch/chapters/70-graphen/images/petersonchrind.pdf new file mode 100644 index 0000000..23ef6e9 Binary files /dev/null and b/buch/chapters/70-graphen/images/petersonchrind.pdf differ diff --git a/buch/chapters/70-graphen/images/petersonchrind.tex b/buch/chapters/70-graphen/images/petersonchrind.tex new file mode 100644 index 0000000..4ae9f39 --- /dev/null +++ b/buch/chapters/70-graphen/images/petersonchrind.tex @@ -0,0 +1,142 @@ +% +% 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\Ra{2} +\def\Ri{1} +\def\e{1.0} +\def\r{0.2} + +\begin{scope}[xshift=-3.5cm] + +\definecolor{rot}{rgb}{0.8,0,0.8} +\definecolor{gruen}{rgb}{0.2,0.6,0.2} +\definecolor{blau}{rgb}{1,0.6,0.2} + +\coordinate (PA) at ({\Ri*sin(0*72)},{\e*\Ri*cos(0*72)}); +\coordinate (PB) at ({\Ri*sin(1*72)},{\e*\Ri*cos(1*72)}); +\coordinate (PC) at ({\Ri*sin(2*72)},{\e*\Ri*cos(2*72)}); +\coordinate (PD) at ({\Ri*sin(3*72)},{\e*\Ri*cos(3*72)}); +\coordinate (PE) at ({\Ri*sin(4*72)},{\e*\Ri*cos(4*72)}); + +\coordinate (QA) at ({\Ra*sin(0*72)},{\e*\Ra*cos(0*72)}); +\coordinate (QB) at ({\Ra*sin(1*72)},{\e*\Ra*cos(1*72)}); +\coordinate (QC) at ({\Ra*sin(2*72)},{\e*\Ra*cos(2*72)}); +\coordinate (QD) at ({\Ra*sin(3*72)},{\e*\Ra*cos(3*72)}); +\coordinate (QE) at ({\Ra*sin(4*72)},{\e*\Ra*cos(4*72)}); + +\draw (PA)--(PC)--(PE)--(PB)--(PD)--cycle; +\draw (QA)--(QB)--(QC)--(QD)--(QE)--cycle; +\draw (PA)--(QA); +\draw (PB)--(QB); +\draw (PC)--(QC); +\draw (PD)--(QD); +\draw (PE)--(QE); + +\fill[color=blau] (PA) circle[radius=\r]; +\fill[color=rot] (PB) circle[radius=\r]; +\fill[color=rot] (PC) circle[radius=\r]; +\fill[color=gruen] (PD) circle[radius=\r]; +\fill[color=gruen] (PE) circle[radius=\r]; + +\fill[color=rot] (QA) circle[radius=\r]; +\fill[color=blau] (QB) circle[radius=\r]; +\fill[color=gruen] (QC) circle[radius=\r]; +\fill[color=rot] (QD) circle[radius=\r]; +\fill[color=blau] (QE) circle[radius=\r]; + +\draw (PA) circle[radius=\r]; +\draw (PB) circle[radius=\r]; +\draw (PC) circle[radius=\r]; +\draw (PD) circle[radius=\r]; +\draw (PE) circle[radius=\r]; + +\draw (QA) circle[radius=\r]; +\draw (QB) circle[radius=\r]; +\draw (QC) circle[radius=\r]; +\draw (QD) circle[radius=\r]; +\draw (QE) circle[radius=\r]; + +\node at (0,{-\Ra}) [below] {$\operatorname{chr}P=3\mathstrut$}; + +\end{scope} + +\begin{scope}[xshift=3.5cm] +\definecolor{rot}{rgb}{0.8,0,0.8} +\definecolor{gruen}{rgb}{0.2,0.6,0.2} +\definecolor{blau}{rgb}{1,0.6,0.2} +\definecolor{gelb}{rgb}{0,0,1} + +\coordinate (PA) at ({\Ri*sin(0*72)},{\e*\Ri*cos(0*72)}); +\coordinate (PB) at ({\Ri*sin(1*72)},{\e*\Ri*cos(1*72)}); +\coordinate (PC) at ({\Ri*sin(2*72)},{\e*\Ri*cos(2*72)}); +\coordinate (PD) at ({\Ri*sin(3*72)},{\e*\Ri*cos(3*72)}); +\coordinate (PE) at ({\Ri*sin(4*72)},{\e*\Ri*cos(4*72)}); + +\coordinate (QA) at ({\Ra*sin(0*72)},{\e*\Ra*cos(0*72)}); +\coordinate (QB) at ({\Ra*sin(1*72)},{\e*\Ra*cos(1*72)}); +\coordinate (QC) at ({\Ra*sin(2*72)},{\e*\Ra*cos(2*72)}); +\coordinate (QD) at ({\Ra*sin(3*72)},{\e*\Ra*cos(3*72)}); +\coordinate (QE) at ({\Ra*sin(4*72)},{\e*\Ra*cos(4*72)}); + +\draw (PA)--(PC)--(PE)--(PB)--(PD)--cycle; +\draw (QA)--(QB)--(QC)--(QD)--(QE)--cycle; +\draw (PA)--(QA); +\draw (PB)--(QB); +\draw (PC)--(QC); +\draw (PD)--(QD); +\draw (PE)--(QE); + +\fill[color=rot] (QA) circle[radius={1.5*\r}]; +\fill[color=rot!40] (QB) circle[radius=\r]; +\fill[color=rot!40] (QE) circle[radius=\r]; +\fill[color=rot!40] (PA) circle[radius=\r]; + +\fill[color=blau] (PB) circle[radius={1.5*\r}]; +\fill[color=blau!40] (PD) circle[radius=\r]; +\fill[color=blau!40] (PE) circle[radius=\r]; +\fill[color=blau!80,opacity=0.5] (QB) circle[radius=\r]; + +\fill[color=gruen] (PC) circle[radius={1.5*\r}]; +\fill[color=gruen!40] (QC) circle[radius=\r]; +\fill[color=gruen!80,opacity=0.5] (PA) circle[radius=\r]; +\fill[color=gruen!80,opacity=0.5] (PE) circle[radius=\r]; + +\fill[color=gelb] (QD) circle[radius={1.5*\r}]; +\fill[color=gelb!80,opacity=0.5] (QC) circle[radius=\r]; +\fill[color=gelb!80,opacity=0.5] (QE) circle[radius=\r]; +\fill[color=gelb!80,opacity=0.5] (PD) circle[radius=\r]; + +\draw (PA) circle[radius=\r]; +\draw (PB) circle[radius={1.5*\r}]; +\draw (PC) circle[radius={1.5*\r}]; +\draw (PD) circle[radius=\r]; +\draw (PE) circle[radius=\r]; + +\draw (QA) circle[radius={1.5*\r}]; +\draw (QB) circle[radius=\r]; +\draw (QC) circle[radius=\r]; +\draw (QD) circle[radius={1.5*\r}]; +\draw (QE) circle[radius=\r]; + +\node at (0,{-\Ra}) [below] {$\operatorname{ind}P=4\mathstrut$}; + +\end{scope} + + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index f68c814..bc5c425 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -1,198 +1,133 @@ % -% spektral.tex +% spektral.tex -- spektrale Graphentheorie % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Spektrale Graphentheorie \label{buch:section:spektrale-graphentheorie}} \rhead{Spektrale Graphentheorie} -Die Laplace-Matrix codiert alle wesentliche Information eines +Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch +die Laplace-Matrix codieren alle wesentliche Information eines ungerichteten Graphen. Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine Komponente haben. Dies eröffnet die Möglichkeit, den Graphen über die linearalgebraischen -Eigenschaften der Laplace-Matrix zu studieren. +Eigenschaften dieser Matrizen zu studieren. +Dieser Abschnitt soll diese Idee an dem ziemlich übersichtlichen Beispiel +der chromatischen Zahl eines Graphen illustrieren. -\subsection{Grapheigenschaften und Spektrum von $L$ -\label{buch:subsection:grapheigenschaften-und-spektrum-von-l}} -TODO XXX +\subsection{Chromatische Zahl und Unabhängigkeitszahl +\label{buch:subsection:chromatische-zahl}} +Der Grad eines Knotens ist ein mass dafür, wie stark ein Graph +``vernetzt'' ist. +Je höher der Grad, desto mehr direkte Verbindungen zwischen Knoten gibt es. +Noch etwas präziser können diese Idee die beiden mit Hilfe der +chromatischen zahl und der Unabhängigkeitszahl erfasst werden. -\subsection{Wärmeleitung auf einem Graphen -\label{buch:subsection:waermeleitung-auf-einem-graphen}} -Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet -werden als Funktionen, die jedem Knoten einen Wert zuordnen. -Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung -auf dem Graphen. -Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten -zu einem anderen zu fliessen. -Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto -grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur -der beteiligten Knoten. -Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional -\[ -\frac{dT_i}{dt} -= -\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i) -= -- -\kappa -\biggl( -d_iT_i -- -\sum_{\text{$j$ Nachbar von $i$}} T_j -\biggr) -\] -Der Term auf der rechten Seite ist genau die Wirkung der -Laplace-Matrix auf dem Vektor $T$ der Temperaturen: -\begin{equation} -\frac{dT}{dt} -= --\kappa L T. -\label{buch:graphen:eqn:waermeleitung} -\end{equation} -Der Wärmefluss, der durch die -Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben -wird, codiert ebenfalls wesentliche Informationen über den Graphen. -Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt, -desto schneller findet der Wärmeaustausch zwischen diesen Teilen -statt. -Die Lösungen der Wärmeleitungsgleichung liefern also Informationen -über den Graphen. +\begin{definition} +Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist +die minimale Anzahl von Farben, die Einfärben der Knoten eines Graphen +nötig sind, sodass benachbarte Knoten verschiedene Farben haben. +\index{chromatische Zahl} +\end{definition} -\subsection{Eigenwerte und Eigenvektoren -\label{buch:subsection:ein-zyklischer-graph}} -Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} -ist eine lineare Differentialgleichung mit konstanten Koeffizienten, -die mit der Matrixexponentialfunktion gelöst werden. -Die Lösung ist -\[ -f(t) = e^{-\kappa Lt}f(0). -\] +\begin{definition} +Eine Menge von Knoten eines Graphen heisst {\em unabhängig}, wenn +keine zwei Knoten im Graphen verbunden sind. +Die {\em Unabhängigkeitszahl} $\operatorname{ind}G$ eines Graphen $G$ +ist die maximale Anzahl Knoten einer unabhängigen Menge. +\index{Unabhängigkeitszahl} +\end{definition} -Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich -ineffizient, da grosse Matrizenprodukte berechnet werden müssen. -Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus -orthonormierten Eigenvektoren und die Eigenwerte sind reell. -Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$ und die -zugehörigen Eigenwerte mit $\lambda_i$. -Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung -der Wärmeleitungsgleichung, denn die beiden Seiten +Zwischen der chromatischen Zahl und der Unabhängigkeitszahl eines Graphen +muss es einen Zusammenhang geben. +Je mehr Verbingungen es im Graphen gibt, desto grösser wird die chromatische +Zahl. +Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein. + +\begin{satz} +\label{buch:satz:chrind} +Ist $G$ ein Graph mit $n$ Knoten, dann gilt +$\operatorname{chr}G\cdot\operatorname{ind}G\ge n$. +\end{satz} + +\begin{proof}[Beweis] +Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben +teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit +gleicher Farbe $f$ ein. +Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also +höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt. +Die Gesamtzahl der Knoten ist also \begin{align*} -\frac{d}{dt}f_i(t) +V +&= +\bigcup_{\text{$f$ eine Farbe}} V_f +&&\Rightarrow& +n &= --\kappa\lambda_ie^{-\kappa\lambda_it}f_i +\sum_{\text{$f$ eine Farbe}} |V_f| +\le +\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G = --\kappa\lambda_i f_i(t) +(\text{Anzahl Farben})\cdot \operatorname{ind}G \\ --\kappa Lf_i(t) +& +&&& &= --\kappa e^{-\kappa\lambda_it} Lf_i -= --\kappa e^{-\kappa\lambda_it} \lambda_i f_i -= --\kappa \lambda_i f_i(t) +\operatorname{chr}G \cdot \operatorname{ind}G \end{align*} -von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein. +Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt. +\qedhere +\end{proof} -Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen -Anfangstemperaturverteilung $f$ kann durch Linearkombination aus -den Lösungen $f_i(t)$ zusammengesetzt werden. -Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren. -Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach, -die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren: -\[ -f=\sum_{i=1}^n \langle f_i,f\rangle f_i. -\] -Daraus kann man die allgmeine Lösungsformel -\begin{equation} -f(t) -= -\sum_{i=1}^n \langle f_i,f\rangle f_i(t) -= -\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i -\label{buch:graphen:eqn:eigloesung} -\end{equation} -ableiten. +\begin{beispiel} +In einem vollständigen Graphen ist jeder Knoten mit jedem anderen verbunden. +Jede Menge mit zwei oder mehr Knoten kann daher nicht unabhängig sein, die +Unabhängigkeitszahl ist daher $\operatorname{ind}G=1$. +Andererseits ist für jeden Knoten eine eigene Farbe nötig, daher ist die +chromatische Zahl $\operatorname{chr}G=n$. +Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar mit +Gleichheit. +Das Beispiel zeigt, dass die Ungleichung nicht ohne zusätzliche Annahmen +verbessert werden kann. +\end{beispiel} -\subsection{Beispiel: Ein zyklischer Graph} \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}} +\includegraphics{chapters/70-graphen/images/petersonchrind.pdf} +\caption{Chromatische Zahl und Unabhängigkeitszahl des Peterson-Graphen. +Die chromatische Zahl ist $3$, da der Graph sich mit drei Farben einfärben +lässt (links). +Die Unabhängigkeitszahl ist $4$, die vier grösseren Knoten im rechten +Graphen sind unabhängig. +Die Farben der kleinen Knoten sind die additive Mischung der Farben +der grossen Knoten, mit denen sie verbunden sind. +\label{buch:graphen:fig:chrindpeterson}} \end{figure} -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. +\begin{beispiel} +Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson} +hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl +$\operatorname{ind}P=4$. +Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar als +Ungleichung: $\operatorname{chr}P\cdot\operatorname{ind}P=3\cdot 4=12>10=n$. +\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'). -\] +Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer +unabhängigen Menge von Punkten. +Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die +chromatische Zahl als ein Mass dafür, wieviele solche anabhängige +Mengen in einem Grapehn untergebracht werden können. + +\subsection{Chromatische Zahl und maximaler Grad +\label{buch:subsection:chr-und-maximaler-grad}} + +\subsection{Maximaler Eigenwert von $A(G)$ maximaler Grad +\label{buch:subsection:maximaler-eigenwert}} -\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{$\alpha_{\text{max}}$ eines Untegraphen +\label{buch:subsection:alphamax-eines-untergraphen}} +\subsection{Chromatische Zahl und $\alpha_{\text{max}}$ +\label{buch:subsection:chr-und-alpha-max}} diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex new file mode 100644 index 0000000..e7fc023 --- /dev/null +++ b/buch/chapters/70-graphen/waerme.tex @@ -0,0 +1,184 @@ +% +% waerme.tex +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Wärmeleitung auf einem Graphen +\label{buch:section:waermeleitung-auf-einem-graphen}} +Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet +werden als Funktionen, die jedem Knoten einen Wert zuordnen. +Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung +auf dem Graphen. +Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten +zu einem anderen zu fliessen. +Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto +grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur +der beteiligten Knoten. +Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional +\[ +\frac{dT_i}{dt} += +\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i) += +- +\kappa +\biggl( +d_iT_i +- +\sum_{\text{$j$ Nachbar von $i$}} T_j +\biggr) +\] +Der Term auf der rechten Seite ist genau die Wirkung der +Laplace-Matrix auf dem Vektor $T$ der Temperaturen: +\begin{equation} +\frac{dT}{dt} += +-\kappa L T. +\label{buch:graphen:eqn:waermeleitung} +\end{equation} +Der Wärmefluss, der durch die +Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben +wird, codiert ebenfalls wesentliche Informationen über den Graphen. +Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt, +desto schneller findet der Wärmeaustausch zwischen diesen Teilen +statt. +Die Lösungen der Wärmeleitungsgleichung liefern also Informationen +über den Graphen. + +\subsection{Eigenwerte und Eigenvektoren +\label{buch:subsection:ein-zyklischer-graph}} +Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} +ist eine lineare Differentialgleichung mit konstanten Koeffizienten, +die mit der Matrixexponentialfunktion gelöst werden. +Die Lösung ist +\[ +f(t) = e^{-\kappa Lt}f(0). +\] + +Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich +ineffizient, da grosse Matrizenprodukte berechnet werden müssen. +Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus +orthonormierten Eigenvektoren und die Eigenwerte sind reell. +Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$ und die +zugehörigen Eigenwerte mit $\lambda_i$. +Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung +der Wärmeleitungsgleichung, denn die beiden Seiten +\begin{align*} +\frac{d}{dt}f_i(t) +&= +-\kappa\lambda_ie^{-\kappa\lambda_it}f_i += +-\kappa\lambda_i f_i(t) +\\ +-\kappa Lf_i(t) +&= +-\kappa e^{-\kappa\lambda_it} Lf_i += +-\kappa e^{-\kappa\lambda_it} \lambda_i f_i += +-\kappa \lambda_i f_i(t) +\end{align*} +von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein. + +Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen +Anfangstemperaturverteilung $f$ kann durch Linearkombination aus +den Lösungen $f_i(t)$ zusammengesetzt werden. +Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren. +Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach, +die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren: +\[ +f=\sum_{i=1}^n \langle f_i,f\rangle f_i. +\] +Daraus kann man die allgmeine Lösungsformel +\begin{equation} +f(t) += +\sum_{i=1}^n \langle f_i,f\rangle f_i(t) += +\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i +\label{buch:graphen:eqn:eigloesung} +\end{equation} +ableiten. + +\subsection{Beispiel: Ein zyklischer Graph} +\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} +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. + + +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} +\] + + -- cgit v1.2.1 From 18fb6543de96f23cfa254005a045e1595f48cff2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 24 May 2021 13:58:26 +0200 Subject: =?UTF-8?q?Kapitel=20=C3=BCber=20spektrale=20Graphentheorie?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/nine.pdf | Bin 0 -> 2136 bytes buch/chapters/70-graphen/images/nine.tex | 67 +++++++ buch/chapters/70-graphen/spektral.tex | 335 ++++++++++++++++++++++++++++++- 4 files changed, 403 insertions(+), 4 deletions(-) create mode 100644 buch/chapters/70-graphen/images/nine.pdf create mode 100644 buch/chapters/70-graphen/images/nine.tex (limited to 'buch') diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index 8f98134..d34247b 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -4,7 +4,7 @@ # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf \ - petersonchrind.pdf + petersonchrind.pdf nine.pdf peterson.pdf: peterson.tex pdflatex peterson.tex @@ -23,3 +23,6 @@ kreis.pdf: kreis.tex fundamental.pdf: fundamental.tex pdflatex fundamental.tex +nine.pdf: nine.tex + pdflatex nine.tex + diff --git a/buch/chapters/70-graphen/images/nine.pdf b/buch/chapters/70-graphen/images/nine.pdf new file mode 100644 index 0000000..2ae9f68 Binary files /dev/null and b/buch/chapters/70-graphen/images/nine.pdf differ diff --git a/buch/chapters/70-graphen/images/nine.tex b/buch/chapters/70-graphen/images/nine.tex new file mode 100644 index 0000000..f214c1e --- /dev/null +++ b/buch/chapters/70-graphen/images/nine.tex @@ -0,0 +1,67 @@ +% +% nine.tex -- Nine node graph to illustrate Wilf's theorem +% +% (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} +\def\kante#1#2{ + \draw[shorten >= 0.2cm,shorten <= 0.2cm] (#1) -- (#2); +} +\def\knoten#1#2{ + \fill[color=#2!30] (#1) circle[radius=0.2]; + \draw[color=#2] (#1) circle[radius=0.2]; + \draw (#1) circle[radius=0.2]; +} +\def\R{1.5} +\definecolor{rot}{rgb}{1,0,0} +\definecolor{gruen}{rgb}{0,0.6,0} +\definecolor{blau}{rgb}{0,0,1} + +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\coordinate (A) at (0:\R); +\coordinate (B) at (40:\R); +\coordinate (C) at (80:\R); +\coordinate (D) at (120:\R); +\coordinate (E) at (160:\R); +\coordinate (F) at (200:\R); +\coordinate (G) at (240:\R); +\coordinate (H) at (280:\R); +\coordinate (I) at (320:\R); + +\knoten{A}{rot} +\knoten{B}{blau} +\knoten{C}{gruen} +\knoten{D}{blau} +\knoten{E}{rot} +\knoten{F}{blau} +\knoten{G}{rot} +\knoten{H}{gruen} +\knoten{I}{blau} + +\kante{A}{B} +\kante{B}{C} +\kante{C}{D} +\kante{D}{E} +\kante{E}{F} +\kante{F}{G} +\kante{G}{H} +\kante{H}{I} +\kante{I}{A} + +\kante{A}{C} +\kante{A}{D} +\kante{D}{G} + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index bc5c425..571b7e1 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -119,15 +119,344 @@ Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die chromatische Zahl als ein Mass dafür, wieviele solche anabhängige Mengen in einem Grapehn untergebracht werden können. +% +% Chromatische Zahl und maximaler Grad +% \subsection{Chromatische Zahl und maximaler Grad \label{buch:subsection:chr-und-maximaler-grad}} +Wenn kein Knoten mehr als $d$ Nachbarn hat, dann reichen +$d+1$ Farben immer, um diesen Knoten und seine Nachbarn einzufärben. +Das heisst aber noch nicht, dass dann auch $d+1$ Farben zur +Einfärbung des ganzen Graphen reichen. +Genau dies garantiert jedoch der folgende Satz. + +\begin{definition} +Der {\em maximale Grad} +\( +\max_{v\in V} \deg(v) +\) +wird mit $d$ bezeichnet. +\end{definition} + +\begin{satz} +\label{buch:graphen:satz:chrmaxgrad} +Ist $G$ ein Graph mit maximalem Grad $d$, dann gilt +$\operatorname{chr}G \le d+1$. +\end{satz} + +\begin{proof}[Beweis] +Wir führen den Beweis mit Hilfe von vollständiger Induktion nach der +Anzahl Knoten eines Graphen. +Ein Graph mit nur einem Knoten hat keine Kanten, der maximale Grad ist +daher $0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des +einen Knotens. -\subsection{Maximaler Eigenwert von $A(G)$ maximaler Grad +Wir nehmen jetzt an, die Behaupt sei für Graphen mit $n-1$ Knoten bereits +bewiesen, ein Graph $G'$ mit $n-1$ Knoten und maximalem Grad $d'$ erfüllt +also die Ungleichung $\operatorname{chr}G'\le d'+1$. + +Wir wählen jetzt einen beleibigen Knoten $v$ des Graphen $G$ und bilden +den Graphen $G'$, der aus $G$ entsteht, indem man den Knoten $v$ +entfernt: $G'=G\setminus\{v\}$. +Der maximale Grad $d'$ von $G'$ kann dabei nicht grösser werden, es ist +also $d'\le d$. +Da $G'$ genau $n-1$ Knoten hat, lässt er sich mit höchstens $d'+1\le d+1$ +Farben einfärben. +Es muss jetzt also nur noch eine Farbe für den Knoten $v$ gefunden werden. +Da $d$ der maximale Grad ist, hat $v$ höchstens $d$ Nachbarn, die höchstens +$d$ verschiedene Farben haben können. +Von den $d+1$ zur Verfügung stehenden Farben bleibt also mindestens eine +übrig, mit der man den Knoten $v$ einfärben kann. +Damit ist der Induktionsschritt gelungen und somit der Satz bewiesen. +\end{proof} + +Das Argument im Beweis von Satz~\ref{buch:graphen:satz:chrmaxgrad} +ist für alle Begriffe anwendbar, die sich bei der Bildung eines +Untergraphen auf ``monotone'' Art ändern. +Die chromatische Zahl eines Untergraphen ist höchstens so gross wie die +des ganzen Graphen. +Dann kann man eine Ungleichung für grosse Graphen schrittweise aus +entsprechenden Ungleichungen für die kleineren Teilgraphen gewinnen. +Ziel der folgenden Abschnitte ist zu zeigen, dass sich eine Grösse +mit ähnlichen Eigenschaften aus dem Eigenwertspektrum der Adjazenzmatrix +ablesen lässt. +Daraus ergibt sich dann eine bessere Abschätzung der chromatischen Zahl +eines Graphen. + +% +% maximaler Eigenwert und maximaler Grad +% +\subsection{Maximaler Eigenwert von $A(G)$ und maximaler Grad \label{buch:subsection:maximaler-eigenwert}} +Die Adjazenzmatrix $A(G)$ eines Graphen $G$ mit $n$ Knoten enthält unter +anderem auch die Information über den Grad eines Knotens. +Die Summe der Elemente einer Zeile oder einer Spalte ergibt einen Vektor, +der die Grade der Knoten als Komponenten enthält. +Ist $U$ ein $n$-dimensionaler Vektor aus lauter Einsen, dann ist +ist $A(G)U$ ein Spaltenvektor bestehend aus den Zeilensummen der Matrix +$A(G)$ und +$U^tA(G)$ ein Zeilenvektor bestehend aus den Spaltensummen. +$A(G)U$ ist also der Vektor der Grade der Knoten. + +Das Skalarprodukt von $A(G)U$ mit $U$ ist die Summe der Grade. +Somit ist +\begin{equation} +\frac{\langle A(G)U,U\rangle}{\langle U,U\rangle} += +\frac{1}{\langle U,U\rangle}\sum_{v\in V}\deg(v) += +\frac{1}{n}(d_1+\dots+d_n) +\label{buch:graphen:eqn:AUdavg} +\end{equation} +der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll. -\subsection{$\alpha_{\text{max}}$ eines Untegraphen +Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar, +die Eigenwerte sind also alle reell. +Es ist ausserdem bekannt, dass der Eigenvektor $f$ zum grössten Eigenwert +$\alpha_{\text{max}}$ von $A(G)$ +den Bruch +\[ +\frac{\langle A(G)f,f\rangle}{\langle f,f\rangle} +\] +für Vektoren $f\ne 0$ maximiert. +Aus~\eqref{buch:graphen:eqn:AUdavg} folgt damit, dass +\begin{equation} +\overline{d} +\le +\alpha_{\text{max}} +\label{buch:graphen:eqn:dqueramax} +\end{equation} +ist. + +In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} +des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver +Matrizen vorgestellt, welche einer Reihe interessanter Aussagen +über den betragsgrössten Eigenwert und den zugehörigen Eigenvektor +macht. +Die Adjazenz-Matrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$ +ist der grösste Eigenwert, also genau die Grösse, auf die die +Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} +und \label{buch:wahrscheinlichkeit:satz:perron-frobenius2} +anwendbar sind. +Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend +ist damit, dass der Graph zusammenhängend ist. +Im folgenden soll dies daher jeweils angenommen werden. + +\begin{satz} +Ist $G$ ein zusammenhänger Graph mit $n$ Knoten und maximalem Grad $d$, +dann gilt +\[ +\frac1n\sum_{v\in V} \deg(v) += +\overline{d} +\le \alpha_{\text{max}} \le d. +\] +\end{satz} + +\begin{proof}[Beweis] +Wir wissen aus \eqref{buch:graphen:eqn:dqueramax} bereits, dass +$\overline{d}\le\alpha_{\text{max}}$ gilt, es bleibt also nur noch +$\alpha_{\text{max}}\le d$ zu beweisen. + +Sei $f$ der Eigenvektor zum Eigenwert $\alpha_{\text{max}}$. +Nach Satz~\label{buch:wahrscheinlichkeit:satz:perron-frobenius2} +ist $f$ ein positiver Vektor mit der Eigenschaft $A(G)f=\alpha_{\text{max}}f$. +Der Eigenvektor $f$ ist eine Funktion auf den Knoten des Graphen, +die $v$-Komponente des Vektors $f$ für einen Vertex $v\in V$ ist $f(v)$. +Die Eigenvektoreigenschaft bedeutet $(A(G)f)(v)=\alpha_{\text{max}} f(v)$. +Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ Einsen genau für diejenigen +Knoten $u\in V$, die zu $v$ benachbart sind. +Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist +\[ +(A(G)f)(v) += +\sum_{u\sim v} f(u). +\] +Die Summe der Komponenten $A(G)f$ kann man erhalten durch Multiplikation +von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen, also +\begin{equation} +\begin{aligned} +\sum_{v\in V}\sum_{u\sim v}f(v) +&= +U^tA(G)f += +(U^tA(G))f += +\begin{pmatrix}d_1&d_2&\dots&d_n\end{pmatrix} f +\\ +&= +\sum_{v\in V}\deg (v) f(v) +\le +\sum_{v\in V}df(v) += +d +\sum_{v\in V}f(v). +\end{aligned} +\label{buch:graphen:eqn:sumkomp} +\end{equation} +Andererseits ist $A(G)f=\alpha_{\text{max}}f$, die linke Seite +von~\eqref{buch:graphen:eqn:sumkomp} ist daher +\begin{equation} +\sum_{v\in V}\sum_{u\sim v}f(v) += +U^tA(G)f += +\alpha_{\text{max}} +U^tf += +\alpha_{\text{max}} \sum_{v\in V}f(v). +\label{buch:graphen:eqn:sumkomp2} +\end{equation} +Die Ungleichung~\eqref{buch:graphen:eqn:sumkomp} +und die Gleichung~\eqref{buch:graphen:eqn:sumkomp2} ergeben zusammen +die Ungleichung +\[ +\alpha_{\text{max}} \sum_{v\in V}f(v) +\le d\sum_{v\in V}f(v) +\qquad\Rightarrow\qquad +\alpha_{\text{max}} \le d, +\] +da die Summe der Komponenten des positiven Vektors $f$ nicht verschwinden +kann. +Damit ist die Ungleichung bewiesen. +\end{proof} + +% +% alpha_max eines Untergraphen +% +\subsection{$\alpha_{\text{max}}$ eines Untergraphen \label{buch:subsection:alphamax-eines-untergraphen}} +Der grösste Eigenwert $\alpha_{\text{max}}$ ist ein potentieller +Anwärter für eine bessere Abschätzung der chromatischen Zahl. +Bereits früher wurde bemerkt, dass dies auch bedeutet, dass man +das Verhalten des grössten Eigenwerts bei einem Übergang zu einem +Untergraphen verstehen muss. -\subsection{Chromatische Zahl und $\alpha_{\text{max}}$ +\begin{satz} +\label{buch:graphen:satz:amaxuntergraph} +Sei $G'$ ein echter Untergraph von $G$ mit Adjazenzmatrix $A(G')$ und +grösstem Eigenwert $\alpha_{\text{max}}'=\varrho(A(G'))$, dann ist +$\alpha_{\text{max}}' \le \alpha_{\text{max}}$. +\end{satz} + +\begin{proof}[Beweis] +Sei $f'$ der positive Eigenvektor zum Eigenwert $\alpha_{\text{max}}'$ +der Matrix $A(G')$. +$f'$ ist definiert auf der Menge $V'$ der Knoten von $G'$. +Aus $f'$ lässt sich ein Vektor $g$ mit den Werten +\[ +g(v) += +\begin{cases} +f'(v)&\qquad v\in V'\\ + 0&\qquad\text{sonst} +\end{cases} +\] +konstruieren, der auf ganz $V$ definiert ist. + +Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch +$\langle f',f'\rangle = \langle g,g\rangle$. +Die Matrixelemente von $A(G')$ und $A(G)$ auf gemeinsamen Knoten $u,v\in V'$ +erfüllen $A(G')_{uv}\le A(G)_{uv}$, da jede Kante von $G'$ auch in $G$ ist. +Daher gilt +\[ +\langle A(G')f',f'\rangle +\le +\langle A(G)g,g\rangle, +\] +woraus sich die Ungleichung +\[ +\alpha_{\text{max}}' += +\frac{\langle A(G')f',f'\rangle}{\langle f',f'\rangle} += +\frac{\langle A(G)g,g\rangle}{\langle g,g\rangle} +\le +\alpha_{\text{max}} +\] +ergibt, da $\alpha_{\text{max}}$ das Maximum von +$\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist. +\end{proof} + +% +% Der Satz von Wilf +% +\subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf \label{buch:subsection:chr-und-alpha-max}} +Die in Satz~\ref{buch:graphen:satz:amaxuntergraph} beschriebene +Eigenschaft von $\alpha_{\text{max}}$ beim Übergang zu einem Untergraphen +ermöglich jetzt, eine besser Abschätzung für die chromatische Zahl +zu finden. + +\begin{satz}[Wilf] +\label{buch:graphen:satz:wilf} +Sie $G$ ein zusammenhängder Graph und $\alpha_{\text{max}}$ der grösste +Eigenwert seiner Adjazenzmatrix. Dann gilt +\[ +\operatorname{chr}G\le \alpha_{\text{max}}+1. +\] +\end{satz} + +\begin{proof}[Beweis] +Wie der Satz~\ref{buch:graphen:satz:chrmaxgrad} kann auch der Satz von Wilf +mit Hilfe von vollständiger Induktion über die Anzahl $n$ der Knoten +bewiesen werden. + +Ein Graph mit nur einem Knoten hat die $0$-Matrix als Adjazenzmatrix, +der maximale Eigenwert ist $\alpha_{\text{max}}=0$, und tatsächlich reicht +$\alpha_{\text{max}}+1=1$ Farbe, um den einen Knoten einzufärben. + +Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits +beweisen. +Wir müssen dann zeigen, dass der Satz dann auch für Graphen mit $n$ Knoten +gilt. + +Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus{v}$ der +Untergraph, der entsteht, wenn der Knoten $v$ entfernt wird. +Da $G'$ genau $n-1$ Knoten hat, gilt der Satz von Wilf für $G'$ +und daher kann $G'$ mit höchstens +\[ +\operatorname{chr}G' \le 1 + \alpha_{\text{max}}' +\] +Farben eingefärbt werden. +Nach Satz~\ref{buch:graphen:satz:amaxuntergraph} ist +$\alpha_{\text{max}}'\le \alpha_{\text{max}}$, +Also kann $G'$ mit höchstens $\alpha_{\text{max}}+1$ Farben eingefärbt werden. + +Da $v$ ein Knoten minimalen Grades ist, ist sein Grad +$d(v)\le \overline{d}\le \alpha_{\text{max}}$. +Die Nachbarn von $v$ haben also hächstens $\alpha_{\text{max}}$ verschiedene +Farben, mit einer weiteren Farbe lässt sich also auch $G$ einfärben. +Daraus folgt $\operatorname{chr}G\le \alpha_{\text{max}}+1$. +\end{proof} + +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/nine.pdf} +\caption{Beispiel für einen Graphen, für den der +Satz~\ref{buch:graphen:satz:wilf} von Wilf die bessere +Abschätzung für die chromatische Zahl eines Graphen gibt als der +maximale Grad. +\label{buch:graphen:fig:wilfexample}} +\end{figure} + +\begin{beispiel} +Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9 +Knoten, daher ist $\overline{d}\le \frac{24}{9}$. +Der maximale Grad ist $4$ und durch explizite Rechnung mit Hilfe zum Beispiel +von Octave ergibt, dass $\alpha_{\text{max}}\approx 2.9565$. +Aus dem Satz von Wilf folgt, dass +$\operatorname{chr}G\le \alpha_{\text{max}}+1$, und daraus ergibt sich +$\operatorname{chr}G\le 3$. +Tatsächlich ist die chromatische Zahl $\operatorname{chr}G=3$, da +der Graph mindestens ein Dreieck enthält. +Der maximale Grad ist 4, somit gibt der +Satz~\ref{buch:graphen:satz:chrmaxgrad} +die Schranke +$\operatorname{chr}G\le 4+1=5$ +für die chromatische Zahl. +Der Satz von Wilf ist also eine wesentliche Verbesserung. +\end{beispiel} + + -- cgit v1.2.1 From 2cad7439d48a67af39b7b5ec03f8874ec9d9a3c6 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:35:18 +0200 Subject: Update section 1 of paper --- buch/papers/verkehr/teil0.tex | 69 ++++++++++++++++++++++++++++++------------- 1 file changed, 49 insertions(+), 20 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/teil0.tex b/buch/papers/verkehr/teil0.tex index 5031841..78d9311 100644 --- a/buch/papers/verkehr/teil0.tex +++ b/buch/papers/verkehr/teil0.tex @@ -1,22 +1,51 @@ -% -% einleitung.tex -- Beispiel-File für die Einleitung -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 0\label{verkehr:section:teil0}} -\rhead{Teil 0} -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua \cite{verkehr:bibtex}. -At vero eos et accusam et justo duo dolores et ea rebum. -Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum -dolor sit amet. - -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua. -At vero eos et accusam et justo duo dolores et ea rebum. Stet clita -kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit -amet. +\section{Versuchsreihe} +\label{section:verkehr/versuchsreihe} +Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. +Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. +Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. +Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. + +\subsection{Einfluss der Knotenzahl auf die Rechenzeit} +\label{verkehr:Knotenzahl} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr1.png} + +\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr1} +\end{wrapfigure} + +In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. +Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. +Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_pathDiff.png} + +\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} +\label{verkehr:pathDifference} +\end{wrapfigure} + + +\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr2} +\end{wrapfigure} + +Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ +Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. + +\begin{wrapfigure}{} +\includegraphics[width=6cm]{figures/network_dij.png}\qquad +\includegraphics[width=6cm]{figures/network_aStar.png} +\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} +\label{verkehr:Comparison} +\end{wrapfigure} + +In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. -- cgit v1.2.1 From 7e4a7b847c63064a40fd7a4d3829eddb4191aa9e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 24 May 2021 20:36:06 +0200 Subject: Wavelets auf einem Graphen --- buch/chapters/70-graphen/beschreibung.tex | 2 +- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/gh.pdf | Bin 0 -> 26177 bytes buch/chapters/70-graphen/images/gh.tex | 55 +++++++ buch/chapters/70-graphen/spektral.tex | 25 ++-- buch/chapters/70-graphen/wavelets.tex | 228 ++++++++++++++++++++++++++++-- buch/chapters/references.bib | 6 + 7 files changed, 298 insertions(+), 23 deletions(-) create mode 100644 buch/chapters/70-graphen/images/gh.pdf create mode 100644 buch/chapters/70-graphen/images/gh.tex (limited to 'buch') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 25cfcc0..a0f46da 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -401,7 +401,7 @@ Sie hat für $i\ne j$ die Einträge \\ &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden} \\ -&=a_{ij} +&=a_{ij}. \end{align*} Die Adjazenzmatrix eines Graphen lässt sich also aus der Inzidenzmatrix berechnen. diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile index d34247b..5db54c8 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -4,7 +4,7 @@ # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf \ - petersonchrind.pdf nine.pdf + petersonchrind.pdf nine.pdf gh.pdf peterson.pdf: peterson.tex pdflatex peterson.tex @@ -26,3 +26,6 @@ fundamental.pdf: fundamental.tex nine.pdf: nine.tex pdflatex nine.tex +gh.pdf: gh.tex + pdflatex gh.tex + diff --git a/buch/chapters/70-graphen/images/gh.pdf b/buch/chapters/70-graphen/images/gh.pdf new file mode 100644 index 0000000..c6e48d7 Binary files /dev/null and b/buch/chapters/70-graphen/images/gh.pdf differ diff --git a/buch/chapters/70-graphen/images/gh.tex b/buch/chapters/70-graphen/images/gh.tex new file mode 100644 index 0000000..fcceb5f --- /dev/null +++ b/buch/chapters/70-graphen/images/gh.tex @@ -0,0 +1,55 @@ +% +% gh.tex -- Lokalsierungsfunktionen für Wavelets auf einem 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} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\def\kurve#1#2{ + \draw[color=#2,line width=1.4pt] + plot[domain=0:6.3,samples=400] + ({\x},{7*\x*exp(-(\x/#1)*(\x/#1))/#1}); +} + +\begin{scope} + +\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}]; + +\kurve{1}{red} +\foreach \k in {0,...,4}{ + \pgfmathparse{0.30*exp(ln(2)*\k)} + \xdef\l{\pgfmathresult} + \kurve{\l}{blue} +} + +\node[color=red] at ({0.7*1},3) [above] {$g(\lambda)$}; +\node[color=blue] at ({0.7*0.3*16},3) [above] {$g_i(\lambda)$}; + +\draw[->] (0,-0.1) -- (0,3.3); +\end{scope} + +\begin{scope}[xshift=7cm] + +\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}]; + +\draw[color=darkgreen,line width=1.4pt] + plot[domain=0:6.3,samples=100] + ({\x},{3*exp(-(\x/0.5)*(\x/0.5)}); + +\draw[->] (0,-0.1) -- (0,3.3) coordinate[label={right:$\color{darkgreen}h(\lambda)$}]; + +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index 571b7e1..5fb3056 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -56,8 +56,10 @@ Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit gleicher Farbe $f$ ein. Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also -höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt. -Die Gesamtzahl der Knoten ist also +höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt, +also $|V_f|\le \operatorname{ind}G$. +Da die Menge aller Knoten die Vereinigung der Mengen $V_f$ ist, +ist die Gesamtzahl der Knoten \begin{align*} V &= @@ -66,15 +68,15 @@ V n &= \sum_{\text{$f$ eine Farbe}} |V_f| -\le -\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G -= -(\text{Anzahl Farben})\cdot \operatorname{ind}G \\ & &&& -&= -\operatorname{chr}G \cdot \operatorname{ind}G +&\le +\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G += +(\text{Anzahl Farben})\cdot \operatorname{ind}G += +\operatorname{chr}G \cdot \operatorname{ind}G. \end{align*} Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt. \qedhere @@ -117,7 +119,7 @@ Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer unabhängigen Menge von Punkten. Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die chromatische Zahl als ein Mass dafür, wieviele solche anabhängige -Mengen in einem Grapehn untergebracht werden können. +Mengen in einem Graphen untergebracht werden können. % % Chromatische Zahl und maximaler Grad @@ -131,7 +133,7 @@ Einfärbung des ganzen Graphen reichen. Genau dies garantiert jedoch der folgende Satz. \begin{definition} -Der {\em maximale Grad} +Der maximale Grad \( \max_{v\in V} \deg(v) \) @@ -455,7 +457,8 @@ Satz~\ref{buch:graphen:satz:chrmaxgrad} die Schranke $\operatorname{chr}G\le 4+1=5$ für die chromatische Zahl. -Der Satz von Wilf ist also eine wesentliche Verbesserung. +Der Satz von Wilf ist also eine wesentliche Verbesserung, er liefert in +diesem Fall den exakten Wert der chromatischen Zahl. \end{beispiel} diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 9c88c08..ae065bc 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -103,22 +103,230 @@ aus der sich alle Vektoren linear kombinieren lassen, in der aber auch auf die für die Anwendung interessante Längenskala angepasste Funktionen gefunden werden können. -\subsection{Wavelets und Frequenzspektrum} -Eine Wavelet-Basis der Funktionen auf $\mathbb{R}$ zerlegt +\subsection{Wavelets auf einem Graphen} +Die Fourier-Theorie analysiert Funktionen nach Frequenzen, wobei die +zeitliche Position von interessanten Stellen der Funktion in der Phase +der einzelnen Komponenten verschwindet. +Die Lokalisierung geht also für viele praktische Zwecke verloren. +Umgekehrt haben einzelne Ereignisse wie eine $\delta$-Funktion keine +charakteristische Frequenz, sie sind daher im Frequenzraum überhaupt +nicht lokalisierbar. +Die Darstellung im Frequenzraum und in der Zeit sind also extreme +Darstellungen, entweder Frequenzlokalisierung oder zeitliche Lokalisierung +ermöglichen, sich aber gegenseitig ausschliessen. +\subsubsection{Dilatation} +Eine Wavelet-Basis für die $L^2$-Funktionen auf $\mathbb{R}$ erlaubt +eine Funktion auf $\mathbb{R}$ auf eine Art zu analysieren, die eine +ungenaue zeitliche Lokalisierung bei entsprechend ungenauer +Frequenzbestimmung ermöglicht. +Ausserdem entstehen die Wavelet-Funktionen aus einer einzigen Funktion +$\psi(t)$ durch Translation um $b$ und Dilatation mit dem Faktor $a$: +\[ +\psi_{a,b}(t) += +\frac{1}{\sqrt{|a|}} \psi\biggl(\frac{t-b}a\biggr) += +T_bD_a\psi(t) +\] +in der Notation von \cite{buch:mathsem-wavelets}. +Auf einem Graphen ist so eine Konstruktion grundsätzlich nicht möglich, +da es darauf weder eine Translations- noch eine Streckungsoperation gibt. + +In der Theorie der diskreten Wavelet-Transformation ist es üblich, sich +auf Zweierpotenzen als Streckungsfaktoren zu beschränken. +Ein Gitter wird dadurch auf sich selbst abgebildet, aber auf einem +Graphen gibt es keine Rechtfertigung für diese spezielle Wahl von +Streckungsfaktoren mehr. +Es stellt sich daher die Frage, ob man für eine beliebige Menge +\( +T= \{ t_1,t_2,\dots\} \} +\) +von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ zu finden +derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus +$\chi_0$ durch Dilatation entstanden vorstellen kann. -\subsection{Frequenzspektrum -\label{buch:subsection:frequenzspektrum}} -Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches -wie $e^{-k^2}$ gegen $0$ geht. +Die Dilatation kann natürlich nicht von einer echten +Dilatation im Ortsraum herstammen, aber man kann wenigstens versuchen, die +Dilatation im Frequenzraum nachzubilden. +Für Funktionen in $L^2(\mathbb{R})$ entspricht die Dilatation mit dem +Faktor $a$ im Ortsraum der Dilatation mit dem Faktor $1/a$ im Frequenzraum: +\[ +\widehat{D_af}(\omega) = D_{1/a}\hat{f}(\omega). +\] +\cite[Satz~3.14]{buch:mathsem-wavelets}. +Es bleibt aber das Problem, dass sich auch die Skalierung im Frequenzraum +nicht durchführen lässt, da auch das Frequenzspektrum des Graphen nur eine +Menge von reellen Zahlen ohne innere algebraische Struktur ist. + +\subsubsection{Mutterwavelets} +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/gh.pdf} +\caption{Lokalisierungsfunktion $g(\lambda)$ für die Dilatation (links). +Die Dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren +die Frequenzen jeweils um die Frequenzen $a_i$ im Frequenzraum. +Der Konstante Vektor ist vollständig delokalisiert, die Funktion $h$ +in der rechten Abbildung entfernt die hohen Frequenzen und liefert Funktionen, +die in der Umgebung eines Knotens wie die Konstante Funktion aussehen. +\label{buch:graphs:fig:lokalisierung}} +\end{figure} +Das Mutter-Wavelet einer Wavelet-Analyse zeichnet definiert, in welchem Mass +sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen. +Die Standardbasis der Funktionen auf einem Graphen repräsentieren die +perfekte örtliche Lokalisierung, Eigenbasis der Laplace-Matrix repräsentiert +die perfekte Lokalisierung im Frequenzraum. +Sei $g(\lambda)\ge 0$ eine Funktion im Frequenzraum, die für $\lambda\to0$ und +$\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen +(Abbildung~\ref{buch:graphs:fig:lokalisierung}). +Sie kann als eine Lokalisierungsfunktion im Frequenzraum betrachtet werden. -Die Fundamentallösung entsteht dadurch, dass die hohen Frequenzen -schneller dämpft als die tiefen Frequenzen. +Die Matrix $g(I)$ bildet entfernt aus einer Funktion die ganz hohen und +die ganz tiefen Frequenz, lokalisiert also die Funktionen im Frequenzraum. +Die Standardbasisvektoren werden dabei zu Funktionen, die nicht mehr nur +auf einem Knoten von $0$ verschieden sind, aber immer noch einigermassen +auf dem Graphen lokalisiert sind. +Natürlich sind vor allem die Werte auf den Eigenwerten +$\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix +von Interesse. +Die Matrix $g(I)$ kann mit Hilfe der Spektraltheorie berechnet werden, +was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren von +der Laplace-Matrix bereits bekannt sind. +Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die +Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab, +$\chi$ vermittelt die Umkehrabbildung. +Mit der Spektraltheorie findet man für die Abbildung $g(I)$ die Matrix +\begin{equation} +g(I) += +\chi +\begin{pmatrix} +g(\lambda_0)&0&\dots&0\\ +0&g(\lambda_1)&\dots&0\\ +\vdots&\vdots&\ddots&\vdots\\ +0&0&\dots&g(\lambda_n) +\end{pmatrix} +\chi^t. +\label{buch:graphen:eqn:mutterwavelet} +\end{equation} -\subsection{Wavelet-Basen -\label{buch:subsection:}} +\subsubsection{Dilatation} +Die Dilatation um $a$ im Ortsraum wird zu einer Dilatation um $1/a$ im +Frequenzraum. +Statt also nach einer echten Dilatation der Spaltenvektoren in $g(I)$ +zu suchen, kann man sich darauf verlegen, Funktionen zu finden, deren +Spektrum von einer Funktionen lokalisiert worden ist, die eine Dilatation +von $g$ ist. +Man wählt daher eine ansteigende Folge $A=(a_1,\dots)$ von Streckungsfaktoren +und betrachtet anstelle von $g$ die dilatierten Funktionen +$g_i=\tilde{D}_{1/a_i}g$. +Die zugehörigen Wavelet-Funktionen auf dem Graphen können wieder mit +der Formel~\eqref{buch:graphen:eqn:mutterwavelet} berechnet werden, +man erhält +\begin{equation} +\tilde{D}_{1/a_i}g(I) += +g_i(I) += +\chi +\begin{pmatrix} +g(a_i\lambda_0)&0&\dots&0\\ +0&g(a_i\lambda_1)&\dots&0\\ +\vdots&\vdots&\ddots&\vdots\\ +0&0&\dots&g(a_i\lambda_n) +\end{pmatrix} +\chi^t . +\end{equation} +Die Spalten von $g_i(I)$ bilden wieder eine Menge von Funktionen, die +eine gemäss $g_i$ lokalisiertes Spektrum haben. +\subsubsection{Vater-Wavelet} +Wegen $g(0)=0$ wird die konstante Funktion, die Eigenvektor zum Eigenwert +$\lambda_0=0$ ist, von den Abbildungen $g_i(I)$ auf $0$ abgebildet. +Andererseits ist diese Funktion nicht lokalisiert, man möchte Sie also +für die Analyse nicht unbedingt verwenden. +Man wählt daher eine Funktion $h(\lambda)$ mit $h(0)=1$ so, dass +für $\lambda\to \infty$ der Wert $h(\lambda)$ genügend rasch gegen $0$ +geht. +Die Matrix $h(I)$ bildet daher den konstanten Vektor nicht auf $0$ ab, +sondern lokalisiert ihn im Ortsraum. +Wir erhalten daher in den Spalten von $h(I)$ Vektoren, die um die +einzelnen Knoten lokalisiert sind. + +\subsubsection{Rekonstruktion} +Die Operatoren $h(I)$ und $g_i(I)$ erzeugen analysieren eine Funktion +nach den verschiedenen Frequenzen mit den Skalierungsfaktoren $a_i$, +aber die Rekonstruktion ist noch nicht klar. +Diese wäre einfacher, wenn die Operatoren zusammen die identische +Abbildung ergäben, wenn also +\[ +h(I) + \sum_{i}g_i(I)=I +\] +gelten würde. +Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte +$\lambda_k$, $k=1,\dots,n$ +\[ +h(\lambda_k) + \sum_ig(a_i\lambda_k)=1 +\] +gilt. +Für beleibige Funktionen $g$ und $h$ kann man nicht davon ausgehen, +aber man kann erwarten. +Man muss daher zusätzlich verlangen, dass +\[ +h(\lambda_k) + \sum_{i} g(a_i\lambda_k) > 0 +\] +ist für alle Eigenwerte $\lambda_k$. + +\subsubsection{Frame} +Die Menge von Vektoren, die in der vorangegangenen Konstruktion gefunden +wurden, ist zu gross, um eine Basis zu sein. +Vektoren lassen sich darin auf verschiedene Art darstellen. +Wir verlangen aber auch keine eindeutige Darstellung, nur eine +Darstellung, in der wir die ``dominierenden'' Komponenten in jeder +Frequenzskala identifizieren können. + +\begin{definition} +\label{buch:graphen:def:frame} +Ein Frame des Vektorraumes $\mathbb{R}^n$ ist eine Menge +$F=\{e_k\;|\; k=1,\dots,N\}$ von Vektoren mit der Eigenschaft +\begin{equation} +A\|v\|^2 +\le +\sum_{k=1}^N |\langle v,e_k\rangle|^2 +\le +B\|v\|^2 +\label{buch:graphen:eqn:frame} +\end{equation} +Die Zahlen $A$ und $B$ heissen die {\em Frame-Konstanten} des Frames. +\end{definition} + +Die oben gefundenen Vektoren, die Spalten Vektoren von $h(I)$ und $g_i(I)$ +bilden daher ein Frame. +Die Frame-Konstanten kann man unmittelbar ausrechnen. +Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist +\[ +\|h(I) v\|^2 ++ +\sum_{i} \|g_i(I)v\|^2, +\] +die durch die Funktion +\[ +f(\lambda) += +h(\lambda)^2 + \sum_i g_i(\lambda)^2 +\] +abgeschätzt werden kann. +Die Frame-Konstanten sind daher +\begin{align*} +A&=\min_{k} f(\lambda_k) +& +&\text{und}& +B&=\max_{k} f(\lambda_k). +\end{align*} +Die Konstruktion hat also ein Frame für die Funktionen auf dem Graphen +etabliert, die viele Eigenschaften einer Multiskalenanalyse in diese +wesentlich weniger symmetrische Situation rettet. diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index a4579e7..a5d0201 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -21,6 +21,12 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc } +@book{buch:mathsem-wavelets, + title = {Mathematisches Seminar Wavelets}, + author = { Andreas M"uller and others }, + year = {2019}, +} + @book{buch:mathsem-dgl, title = {Mathematisches Seminar Differentialgleichungen}, author = { Andreas M"uller and others }, -- cgit v1.2.1 From 1d1a334cce74e76b5ae18701b39d379580e07edb Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:36:50 +0200 Subject: Update section 2 of paper --- buch/papers/verkehr/teil1.tex | 102 ++++++++++++++++++++---------------------- 1 file changed, 49 insertions(+), 53 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/teil1.tex b/buch/papers/verkehr/teil1.tex index 855aef8..78d9311 100644 --- a/buch/papers/verkehr/teil1.tex +++ b/buch/papers/verkehr/teil1.tex @@ -1,55 +1,51 @@ -% -% teil1.tex -- Beispiel-File für das Paper -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 1 -\label{verkehr:section:teil1}} -\rhead{Problemstellung} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. -Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit -aut fugit, sed quia consequuntur magni dolores eos qui ratione -voluptatem sequi nesciunt -\begin{equation} -\int_a^b x^2\, dx -= -\left[ \frac13 x^3 \right]_a^b -= -\frac{b^3-a^3}3. -\label{verkehr:equation1} -\end{equation} -Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, -consectetur, adipisci velit, sed quia non numquam eius modi tempora -incidunt ut labore et dolore magnam aliquam quaerat voluptatem. - -Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis -suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? -Quis autem vel eum iure reprehenderit qui in ea voluptate velit -esse quam nihil molestiae consequatur, vel illum qui dolorem eum -fugiat quo voluptas nulla pariatur? - -\subsection{De finibus bonorum et malorum -\label{verkehr:subsection:finibus}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga \eqref{000tempmlate:equation1}. - -Et harum quidem rerum facilis est et expedita distinctio -\ref{verkehr:section:loesung}. -Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil -impedit quo minus id quod maxime placeat facere possimus, omnis -voluptas assumenda est, omnis dolor repellendus -\ref{verkehr:section:folgerung}. -Temporibus autem quibusdam et aut officiis debitis aut rerum -necessitatibus saepe eveniet ut et voluptates repudiandae sint et -molestiae non recusandae. -Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis -voluptatibus maiores alias consequatur aut perferendis doloribus -asperiores repellat. +\section{Versuchsreihe} +\label{section:verkehr/versuchsreihe} +Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. +Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. +Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. +Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. + +\subsection{Einfluss der Knotenzahl auf die Rechenzeit} +\label{verkehr:Knotenzahl} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr1.png} + +\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr1} +\end{wrapfigure} + +In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. +Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. +Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_pathDiff.png} + +\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} +\label{verkehr:pathDifference} +\end{wrapfigure} + + +\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr2} +\end{wrapfigure} + +Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ +Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. + +\begin{wrapfigure}{} +\includegraphics[width=6cm]{figures/network_dij.png}\qquad +\includegraphics[width=6cm]{figures/network_aStar.png} +\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} +\label{verkehr:Comparison} +\end{wrapfigure} + +In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. -- cgit v1.2.1 From 61c60ad40387ed1401f6685a152529874c07d63d Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:37:23 +0200 Subject: Update section 3 of paper --- buch/papers/verkehr/teil2.tex | 46 +++++++------------------------------------ 1 file changed, 7 insertions(+), 39 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/teil2.tex b/buch/papers/verkehr/teil2.tex index 5170ded..99a0d92 100644 --- a/buch/papers/verkehr/teil2.tex +++ b/buch/papers/verkehr/teil2.tex @@ -1,40 +1,8 @@ -% -% teil2.tex -- Beispiel-File für teil2 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 2 -\label{verkehr:section:teil2}} -\rhead{Teil 2} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{verkehr:subsection:bonorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - +\section{Ausblick} +\subsection{Optimierungsprobleme bei Graphen} +Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Grafen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.\\ +Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein. Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem \emph{Dijkstra}, oder dem \emph{A*}-Algorithmus anstelle der Graph-Matrix (mit Kantengewichten als Einträgen) die Adjazenz-Matrix als Argument übergeben wird. Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten. +\subsection{Wahl der Heuristik} +Ein grundlegendes Problem bei der Anwendung des \emph{A*} oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik. Bei einem physischen Verkehrsnetz kann bspw. die euklidische Distanz problems ermittelt werde. Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend. Dies gilt z.B. auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.} Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig. Anonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.\\ +In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik. Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen. Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik. Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden. -- cgit v1.2.1 From 0cd2f753702cc0ce0c74a281c4b7146ca96ae78f Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:40:11 +0200 Subject: delete 4th section 4th section not needed --- buch/papers/verkehr/teil3.tex | 40 ---------------------------------------- 1 file changed, 40 deletions(-) delete mode 100644 buch/papers/verkehr/teil3.tex (limited to 'buch') diff --git a/buch/papers/verkehr/teil3.tex b/buch/papers/verkehr/teil3.tex deleted file mode 100644 index 8f79154..0000000 --- a/buch/papers/verkehr/teil3.tex +++ /dev/null @@ -1,40 +0,0 @@ -% -% teil3.tex -- Beispiel-File für Teil 3 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 3 -\label{verkehr:section:teil3}} -\rhead{Teil 3} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{verkehr:subsection:malorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - - -- cgit v1.2.1 From e43c4b251bbed04a843a3b4b13f2c2ae25bc7181 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:45:52 +0200 Subject: added /figure folder and figures --- buch/papers/verkehr/figures/chart_Vr1.png | Bin 0 -> 74176 bytes buch/papers/verkehr/figures/chart_Vr2.png | Bin 0 -> 64237 bytes buch/papers/verkehr/figures/chart_pathDiff.png | Bin 0 -> 36673 bytes buch/papers/verkehr/figures/dist_display6.png | Bin 0 -> 399354 bytes buch/papers/verkehr/figures/network_aStar.png | Bin 0 -> 79386 bytes buch/papers/verkehr/figures/network_dij.png | Bin 0 -> 77108 bytes 6 files changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/verkehr/figures/chart_Vr1.png create mode 100644 buch/papers/verkehr/figures/chart_Vr2.png create mode 100644 buch/papers/verkehr/figures/chart_pathDiff.png create mode 100644 buch/papers/verkehr/figures/dist_display6.png create mode 100644 buch/papers/verkehr/figures/network_aStar.png create mode 100644 buch/papers/verkehr/figures/network_dij.png (limited to 'buch') diff --git a/buch/papers/verkehr/figures/chart_Vr1.png b/buch/papers/verkehr/figures/chart_Vr1.png new file mode 100644 index 0000000..14d4eca Binary files /dev/null and b/buch/papers/verkehr/figures/chart_Vr1.png differ diff --git a/buch/papers/verkehr/figures/chart_Vr2.png b/buch/papers/verkehr/figures/chart_Vr2.png new file mode 100644 index 0000000..2d68681 Binary files /dev/null and b/buch/papers/verkehr/figures/chart_Vr2.png differ diff --git a/buch/papers/verkehr/figures/chart_pathDiff.png b/buch/papers/verkehr/figures/chart_pathDiff.png new file mode 100644 index 0000000..02bded7 Binary files /dev/null and b/buch/papers/verkehr/figures/chart_pathDiff.png differ diff --git a/buch/papers/verkehr/figures/dist_display6.png b/buch/papers/verkehr/figures/dist_display6.png new file mode 100644 index 0000000..3056f43 Binary files /dev/null and b/buch/papers/verkehr/figures/dist_display6.png differ diff --git a/buch/papers/verkehr/figures/network_aStar.png b/buch/papers/verkehr/figures/network_aStar.png new file mode 100644 index 0000000..5a681bd Binary files /dev/null and b/buch/papers/verkehr/figures/network_aStar.png differ diff --git a/buch/papers/verkehr/figures/network_dij.png b/buch/papers/verkehr/figures/network_dij.png new file mode 100644 index 0000000..d9348d7 Binary files /dev/null and b/buch/papers/verkehr/figures/network_dij.png differ -- cgit v1.2.1 From 26ecbb9559558f40e5e05a84ceb8622c5c9bd182 Mon Sep 17 00:00:00 2001 From: Pascal Schmid Date: Mon, 24 May 2021 20:57:36 +0200 Subject: renamed section files --- buch/papers/verkehr/section1.tex | 51 ++++++++++++++++++++++++++++++++++++++++ buch/papers/verkehr/section2.tex | 51 ++++++++++++++++++++++++++++++++++++++++ buch/papers/verkehr/section3.tex | 8 +++++++ buch/papers/verkehr/teil0.tex | 51 ---------------------------------------- buch/papers/verkehr/teil1.tex | 51 ---------------------------------------- buch/papers/verkehr/teil2.tex | 8 ------- 6 files changed, 110 insertions(+), 110 deletions(-) create mode 100644 buch/papers/verkehr/section1.tex create mode 100644 buch/papers/verkehr/section2.tex create mode 100644 buch/papers/verkehr/section3.tex delete mode 100644 buch/papers/verkehr/teil0.tex delete mode 100644 buch/papers/verkehr/teil1.tex delete mode 100644 buch/papers/verkehr/teil2.tex (limited to 'buch') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex new file mode 100644 index 0000000..78d9311 --- /dev/null +++ b/buch/papers/verkehr/section1.tex @@ -0,0 +1,51 @@ +\section{Versuchsreihe} +\label{section:verkehr/versuchsreihe} + +Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. +Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. +Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. + +Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. + +\subsection{Einfluss der Knotenzahl auf die Rechenzeit} +\label{verkehr:Knotenzahl} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr1.png} + +\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr1} +\end{wrapfigure} + +In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. +Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. +Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_pathDiff.png} + +\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} +\label{verkehr:pathDifference} +\end{wrapfigure} + + +\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr2} +\end{wrapfigure} + +Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ +Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. + +\begin{wrapfigure}{} +\includegraphics[width=6cm]{figures/network_dij.png}\qquad +\includegraphics[width=6cm]{figures/network_aStar.png} +\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} +\label{verkehr:Comparison} +\end{wrapfigure} + +In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex new file mode 100644 index 0000000..78d9311 --- /dev/null +++ b/buch/papers/verkehr/section2.tex @@ -0,0 +1,51 @@ +\section{Versuchsreihe} +\label{section:verkehr/versuchsreihe} + +Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. +Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. +Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. +Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. + +Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. + +\subsection{Einfluss der Knotenzahl auf die Rechenzeit} +\label{verkehr:Knotenzahl} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr1.png} + +\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr1} +\end{wrapfigure} + +In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. +Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. +Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_pathDiff.png} + +\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} +\label{verkehr:pathDifference} +\end{wrapfigure} + + +\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} + +\begin{wrapfigure}{} +\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} +\label{verkehr:Vr2} +\end{wrapfigure} + +Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ +Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. + +\begin{wrapfigure}{} +\includegraphics[width=6cm]{figures/network_dij.png}\qquad +\includegraphics[width=6cm]{figures/network_aStar.png} +\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} +\label{verkehr:Comparison} +\end{wrapfigure} + +In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. diff --git a/buch/papers/verkehr/section3.tex b/buch/papers/verkehr/section3.tex new file mode 100644 index 0000000..99a0d92 --- /dev/null +++ b/buch/papers/verkehr/section3.tex @@ -0,0 +1,8 @@ +\section{Ausblick} +\subsection{Optimierungsprobleme bei Graphen} +Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Grafen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.\\ +Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein. Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem \emph{Dijkstra}, oder dem \emph{A*}-Algorithmus anstelle der Graph-Matrix (mit Kantengewichten als Einträgen) die Adjazenz-Matrix als Argument übergeben wird. Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten. + +\subsection{Wahl der Heuristik} +Ein grundlegendes Problem bei der Anwendung des \emph{A*} oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik. Bei einem physischen Verkehrsnetz kann bspw. die euklidische Distanz problems ermittelt werde. Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend. Dies gilt z.B. auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.} Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig. Anonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.\\ +In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik. Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen. Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik. Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden. diff --git a/buch/papers/verkehr/teil0.tex b/buch/papers/verkehr/teil0.tex deleted file mode 100644 index 78d9311..0000000 --- a/buch/papers/verkehr/teil0.tex +++ /dev/null @@ -1,51 +0,0 @@ -\section{Versuchsreihe} -\label{section:verkehr/versuchsreihe} - -Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. -Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. -Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. -Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. - -Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. - -\subsection{Einfluss der Knotenzahl auf die Rechenzeit} -\label{verkehr:Knotenzahl} - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_Vr1.png} - -\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} -\label{verkehr:Vr1} -\end{wrapfigure} - -In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. -Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. -Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_pathDiff.png} - -\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} -\label{verkehr:pathDifference} -\end{wrapfigure} - - -\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ -\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} -\label{verkehr:Vr2} -\end{wrapfigure} - -Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ -Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. - -\begin{wrapfigure}{} -\includegraphics[width=6cm]{figures/network_dij.png}\qquad -\includegraphics[width=6cm]{figures/network_aStar.png} -\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} -\label{verkehr:Comparison} -\end{wrapfigure} - -In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. diff --git a/buch/papers/verkehr/teil1.tex b/buch/papers/verkehr/teil1.tex deleted file mode 100644 index 78d9311..0000000 --- a/buch/papers/verkehr/teil1.tex +++ /dev/null @@ -1,51 +0,0 @@ -\section{Versuchsreihe} -\label{section:verkehr/versuchsreihe} - -Um zwei der vorgestellten Suchalgorithmen zu vergleichen, wurden zwei Versuchsreihen erstellt. Dazu wurden in einem ersten Schritt zufällige Netzwerke generiert und anschliessend der \emph{Dijkstra}-, sowie der \emph{$A^*$}-Algorithmus auf das Netzwerk angewandt. -Dieser Vorgang wurde für die zufällig generierten Netzwerke mit einer Knotenzahl von 10, 20 50, 100, 200, 500 und 1000 je zehnmal repetiert. -Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenzeit aus. Der \emph{Dijkstra}-Algorithmus weist eine Zeitkomplexität von $\mathcal{O}(E\log{}V)$ auf, wobei $E$ die Anzahl Kanten (engl. \emph{edges}) und $V$ die Anzahl Knoten (engl. \emph{vertices}) darstellt. -Für den \emph{A*}-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine defintive Angabe zu $\mathcal{O}$ machen. - -Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. - -\subsection{Einfluss der Knotenzahl auf die Rechenzeit} -\label{verkehr:Knotenzahl} - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_Vr1.png} - -\caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} -\label{verkehr:Vr1} -\end{wrapfigure} - -In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. -Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. -Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_pathDiff.png} - -\caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} -\label{verkehr:pathDifference} -\end{wrapfigure} - - -\subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} - -\begin{wrapfigure}{} -\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ -\caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} -\label{verkehr:Vr2} -\end{wrapfigure} - -Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ -Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. - -\begin{wrapfigure}{} -\includegraphics[width=6cm]{figures/network_dij.png}\qquad -\includegraphics[width=6cm]{figures/network_aStar.png} -\caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} -\label{verkehr:Comparison} -\end{wrapfigure} - -In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. diff --git a/buch/papers/verkehr/teil2.tex b/buch/papers/verkehr/teil2.tex deleted file mode 100644 index 99a0d92..0000000 --- a/buch/papers/verkehr/teil2.tex +++ /dev/null @@ -1,8 +0,0 @@ -\section{Ausblick} -\subsection{Optimierungsprobleme bei Graphen} -Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Grafen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen.\\ -Im Bereich vom Computernetzwerken könnte zum Beispiel die Minimierung der Knotenzahl zur Datenübbertragung von Interesse sein. Dabei lässt sich dieses Problem einfach dadurch lösen, dass dem \emph{Dijkstra}, oder dem \emph{A*}-Algorithmus anstelle der Graph-Matrix (mit Kantengewichten als Einträgen) die Adjazenz-Matrix als Argument übergeben wird. Der gefundene kürzeste Pfad enstpricht der Anzahl benutzter Kanten, bzw. der Anzahl besuchter Knoten. - -\subsection{Wahl der Heuristik} -Ein grundlegendes Problem bei der Anwendung des \emph{A*} oder ähnlicher informierter Suchalgorithmen ist die Wahl der Heurstik. Bei einem physischen Verkehrsnetz kann bspw. die euklidische Distanz problems ermittelt werde. Bei einem regionalen Netzwerk ist die Annahme eines orthogonalen X-Y-Koordinatenetzes absolut ausreichend. Dies gilt z.B. auch für das Vernessungsnetz der Schweiz\footnote{Die aktuelle Schweizer Referenzsystem LV95 benutzt ein E/N-Koordinatennetz, wobei aufgrund zunehmender Abweichung vom Referenzellipsoid bei grosser Entfernung vom Nullpunkt ein Korrekturfaktor für die Höhe angebracht werden muss.} Bei überregionalen Netzwerken (Beispiel: Flugverbindungen) ist hingegen eine Berechnung im dreidimensionalen Raum, oder vereinfacht als Projektion auf das Geoid notwendig. Anonsten ist der Ablauf bei der Ausführung des Algorithmus allerdings identisch.\\ -In nicht-physischen Netzwerken stellt sich jedoch eine zweite Problematik. Da eine physische Distanz entweder nicht ermittelt werden kann, oder aber nicht ausschlaggebend ist, sind andere Netzwerk-Eigenschaften zur Beurteilung beizuziehen. Die Zuverlässigkeit ist dabei aber in den meisten Fällen nicht vergleichbar hoch, wie bei der euklidischen Heuristik. Oftmals werden deshalb bei derartigen Problem auch Algorithmen angewendet, die eine deutlich optimierte Zeitkomplexität aufweisen, dafür aber nicht mit Sicherheit den effizienstesten Pfad finden. -- cgit v1.2.1 From f5ac886bcfec175d61bbcb9fef9dd56c394bbf03 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 20:59:00 +0200 Subject: adjusted input-section names --- buch/papers/verkehr/main.tex | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/main.tex b/buch/papers/verkehr/main.tex index 332ee7e..01de182 100644 --- a/buch/papers/verkehr/main.tex +++ b/buch/papers/verkehr/main.tex @@ -27,10 +27,9 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern. \end{itemize} -\input{papers/verkehr/teil0.tex} -\input{papers/verkehr/teil1.tex} -\input{papers/verkehr/teil2.tex} -\input{papers/verkehr/teil3.tex} +\input{papers/verkehr/section1.tex} +\input{papers/verkehr/section2.tex} +\input{papers/verkehr/section3.tex} \printbibliography[heading=subbibliography] \end{refsection} -- cgit v1.2.1 From 50995d1062d097f67afc8a11f9d7808539aa1e82 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 21:18:46 +0200 Subject: added chapter title, author --- buch/papers/verkehr/main.tex | 23 ++--------------------- 1 file changed, 2 insertions(+), 21 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/main.tex b/buch/papers/verkehr/main.tex index 01de182..6348993 100644 --- a/buch/papers/verkehr/main.tex +++ b/buch/papers/verkehr/main.tex @@ -4,28 +4,9 @@ % (c) 2020 Hochschule Rapperswil % \chapter{Thema\label{chapter:verkehr}} -\lhead{Thema} +\lhead{Verkehrsfluss und Verkehrsnetze} \begin{refsection} -\chapterauthor{Hans Muster} - -Ein paar Hinweise für die korrekte Formatierung des Textes -\begin{itemize} -\item -Absätze werden gebildet, indem man eine Leerzeile einfügt. -Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet. -\item -Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende -Optionen werden gelöscht. -Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen. -\item -Beginnen Sie jeden Satz auf einer neuen Zeile. -Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen -in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt -anzuwenden. -\item -Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren -Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern. -\end{itemize} +\chapterauthor{Pascal Andreas Schmid und Robine Luchsinger} \input{papers/verkehr/section1.tex} \input{papers/verkehr/section2.tex} -- cgit v1.2.1 From c639d259a74ab2fae3a85bc861e0bc5070800b13 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 21:24:56 +0200 Subject: adjusted figures in section 1 --- buch/papers/verkehr/section1.tex | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 78d9311..9e40553 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -11,41 +11,45 @@ Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- \subsection{Einfluss der Knotenzahl auf die Rechenzeit} \label{verkehr:Knotenzahl} -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_Vr1.png} \caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr1} -\end{wrapfigure} +\end{figure} In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_pathDiff.png} \caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} \label{verkehr:pathDifference} -\end{wrapfigure} +\end{figure} \subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_Vr2.png}\\ \caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr2} -\end{wrapfigure} +\end{figure} Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=6cm]{figures/network_dij.png}\qquad \includegraphics[width=6cm]{figures/network_aStar.png} \caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} \label{verkehr:Comparison} -\end{wrapfigure} +\end{figure} In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. -- cgit v1.2.1 From b5bdeb425d4e8d509ba4d786fab3b167ff48d767 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Mon, 24 May 2021 21:25:54 +0200 Subject: adjusted figures in section 2 --- buch/papers/verkehr/section2.tex | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index 78d9311..9e40553 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -11,41 +11,45 @@ Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- \subsection{Einfluss der Knotenzahl auf die Rechenzeit} \label{verkehr:Knotenzahl} -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_Vr1.png} \caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr1} -\end{wrapfigure} +\end{figure} In \ref{verkehr:Vr1} ist ersichtlich, dass der Unterschied in der Rechenzeit zwischen \emph{Dijkstra} und \emph{A*} erst aber einer Knotenzahl von ca. $n=500$ merklich ansteigt. Dieses etwas überraschende Resultat ist darauf zurückzuführen, dass bei steigender Knotenzahl die Abweichung des effektiven kürzesten Pfades von der Distanz der Luftlinie abnimmt. Die Effektivität von \emph{A*} mit euklidischer Heuristik ist wiederum grösser, wenn die Abweichung des kürzesten Pfads von der Luftlinie minimal ist. Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei die relative Abweichung erstaunlicherweise bei einer Knotenzahl von $n=100$ maximal ist und nach $n=500$ nur noch marginal abnimmt. -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_pathDiff.png} \caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} \label{verkehr:pathDifference} -\end{wrapfigure} +\end{figure} \subsection{Einfluss der Position der Start- und Zielknoten auf die Rechenzeit} -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=12cm]{figures/chart_Vr2.png}\\ \caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr2} -\end{wrapfigure} +\end{figure} Zum Vergleich der Resultate in \ref{verkehr:Knotenzahl} zeigt \ref{verkehr:Vr2} die Rechenzeiten der zweiten Versuchsreihe, in welcher die Start- und Zielknoten zufällig im Netzwerk ausgewählt wurden. Einerseits ist eine reduzierte durchschnittliche Rechenzeit festzustellen, was schlicht daran liegt, dass die zufällige Wahl der Knoten dazu führt, dass diese tendenziell weniger weit auseinander liegen.\\ Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwischen \emph{Dijkstra} und \emph{A*} deutlich früher abzeichnen. Dieses Phänomen lässt sich leicht durch die zielgerichtete Suche des \emph{A*}-Algorithmus erklären. -\begin{wrapfigure}{} +\begin{figure} +\centering \includegraphics[width=6cm]{figures/network_dij.png}\qquad \includegraphics[width=6cm]{figures/network_aStar.png} \caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} \label{verkehr:Comparison} -\end{wrapfigure} +\end{figure} In \ref{verkehr:Comparison} ist ersichtlich, dass bei einem im Netzwerk liegenden Startknoten die zielgerichtete Suche von \emph{A*} deutlich ausgeprägter zum Zuge kommt, als wenn dieser am Rand des Netzwerks liegen würde. -- cgit v1.2.1 From c4cd9d1d746d382c4afe67078cb31997db1a5f9c Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Tue, 25 May 2021 00:53:59 +0200 Subject: Typos in chapter Vectore und Matrizen --- buch/chapters/10-vektorenmatrizen/gruppen.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'buch') diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index 9848469..6453566 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -313,14 +313,14 @@ auf einem geeigneten Vektorraum. \begin{definition} \label{buch:vektorenmatrizen:def:darstellung} Eine Darstellung einer Gruppe $G$ ist ein Homomorphismus -$G\to\operatorname{GL}_(\mathbb{R})$. +$G\to\operatorname{GL}_n(\mathbb{R})$. \index{Darstellung} \end{definition} \begin{beispiel} Die Gruppen $\operatorname{GL}_n(\mathbb{Z})$, $\operatorname{SL}_n(\mathbb{Z})$ oder $\operatorname{SO}(n)$ -sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R}$. + sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R})$. Die Einbettungsabbildung $G\hookrightarrow \operatorname{GL}_n(\mathbb{R})$ ist damit automatisch eine Darstellung, sie heisst auch die {\em reguläre Darstellung} der Gruppe $G$. -- cgit v1.2.1 From f1229a2d10f67eaefa4903a1e94d8259517bdd1c Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Tue, 25 May 2021 00:56:22 +0200 Subject: Remove whitespace Made a typo while fixing one ... --- buch/chapters/10-vektorenmatrizen/gruppen.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch') diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index 6453566..dfa7ab9 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -320,7 +320,7 @@ $G\to\operatorname{GL}_n(\mathbb{R})$. \begin{beispiel} Die Gruppen $\operatorname{GL}_n(\mathbb{Z})$, $\operatorname{SL}_n(\mathbb{Z})$ oder $\operatorname{SO}(n)$ - sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R})$. +sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R})$. Die Einbettungsabbildung $G\hookrightarrow \operatorname{GL}_n(\mathbb{R})$ ist damit automatisch eine Darstellung, sie heisst auch die {\em reguläre Darstellung} der Gruppe $G$. -- cgit v1.2.1 From 74e9f65ccf48e09553690d5b9560e1b9c5be84f1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 25 May 2021 07:45:53 +0200 Subject: fix image paths --- buch/papers/verkehr/Makefile.inc | 12 +++++------- buch/papers/verkehr/section1.tex | 10 +++++----- buch/papers/verkehr/section2.tex | 10 +++++----- 3 files changed, 15 insertions(+), 17 deletions(-) (limited to 'buch') diff --git a/buch/papers/verkehr/Makefile.inc b/buch/papers/verkehr/Makefile.inc index 7bd8de1..876d0df 100644 --- a/buch/papers/verkehr/Makefile.inc +++ b/buch/papers/verkehr/Makefile.inc @@ -3,12 +3,10 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -dependencies-verkehr = \ +dependencies-verkehr = \ papers/verkehr/packages.tex \ - papers/verkehr/main.tex \ - papers/verkehr/references.bib \ - papers/verkehr/teil0.tex \ - papers/verkehr/teil1.tex \ - papers/verkehr/teil2.tex \ - papers/verkehr/teil3.tex + papers/verkehr/main.tex \ + papers/verkehr/section1.tex \ + papers/verkehr/section2.tex \ + papers/verkehr/references.bib diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 9e40553..638d9dd 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -13,7 +13,7 @@ Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_Vr1.png} +\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr1.png} \caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr1} @@ -25,7 +25,7 @@ Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei di \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_pathDiff.png} +\includegraphics[width=12cm]{papers/verkehr/figures/chart_pathDiff.png} \caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} \label{verkehr:pathDifference} @@ -36,7 +36,7 @@ Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei di \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr2.png}\\ \caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr2} \end{figure} @@ -46,8 +46,8 @@ Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwis \begin{figure} \centering -\includegraphics[width=6cm]{figures/network_dij.png}\qquad -\includegraphics[width=6cm]{figures/network_aStar.png} +\includegraphics[width=6cm]{papers/verkehr/figures/network_dij.png}\qquad +\includegraphics[width=6cm]{papers/verkehr/figures/network_aStar.png} \caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} \label{verkehr:Comparison} \end{figure} diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index 9e40553..638d9dd 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -13,7 +13,7 @@ Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_Vr1.png} +\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr1.png} \caption{Gemessene Rechenzeiten der ersten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr1} @@ -25,7 +25,7 @@ Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei di \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_pathDiff.png} +\includegraphics[width=12cm]{papers/verkehr/figures/chart_pathDiff.png} \caption{Relative Abweichung des kürzesten Pfads von der Luftlinie.} \label{verkehr:pathDifference} @@ -36,7 +36,7 @@ Bei Betrachtung von \ref{verkehr:pathDifference} wird dies ersichtlich, wobei di \begin{figure} \centering -\includegraphics[width=12cm]{figures/chart_Vr2.png}\\ +\includegraphics[width=12cm]{papers/verkehr/figures/chart_Vr2.png}\\ \caption{Gemessene Rechenzeiten der zweiten Versuchsreihe in Abhängigkeit der Knotenzahl.} \label{verkehr:Vr2} \end{figure} @@ -46,8 +46,8 @@ Des weiteren ist festzustellen, dass sich die Unterschiede der Rechenzeiten zwis \begin{figure} \centering -\includegraphics[width=6cm]{figures/network_dij.png}\qquad -\includegraphics[width=6cm]{figures/network_aStar.png} +\includegraphics[width=6cm]{papers/verkehr/figures/network_dij.png}\qquad +\includegraphics[width=6cm]{papers/verkehr/figures/network_aStar.png} \caption{Suchpfad in grün mit \emph{Dijkstra} (links), und \emph{A*} (rechts). Besuchte Knoten sind in blau, resp. rot markiert.} \label{verkehr:Comparison} \end{figure} -- cgit v1.2.1 From 0c790bc7f4a0e39efc45b5aa007a4e0d94ae5b74 Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Wed, 26 May 2021 15:48:00 +0200 Subject: Typo in lie groups --- buch/chapters/60-gruppen/lie-gruppen.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch') diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index d6fc007..e92c254 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -29,7 +29,7 @@ wenn es gelingt, eine Karte für eine Umgebung des neutralen Elements zu finden. Dazu muss gezeigt werden, dass sich aus einer solchen Karte für jedes andere Gruppenelement eine Karte für eine Umgebung ableiten lässt. -Sei also $\varphi_e\colon U_e\mathbb{R}^N$ eine Karte für die Umgebung +Sei also $\varphi_e\colon U_e \to \mathbb{R}^N$ eine Karte für die Umgebung $U_e\subset G$ von $e\in G$. Für $g\in G$ ist dann die Abbildung \[ -- cgit v1.2.1