\documentclass[headsepline,11pt]{scrbook}
\usepackage[a4paper]{geometry}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage[ngerman]{babel}
%
\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}[lem]{Satz}
\theoremstyle{definition}
\newtheorem{df}[lem]{Definition}
%
\def\R{\mathbb R}
\def\C{\mathbb C}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diam}{diam}
%
\usepackage{tikz}
%
\begin{document}
%
%%%%% KEiNE AENDERUNGEN UEBER DIESER ZEILE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\chapter*{Notation}

{\bfseries\sffamily Die hier angegebene Notation weicht von der im Buch ab, im Seminar sollte dies berücksichtigt werden. Dies betrifft insbesondere Normen und Skalarprodukte und die Dirichletformen.}

\begin{enumerate}
\item
Ein \emph{Graph} $G=(V,E,\iota)$ besteht aus Knotenmenge $V$ und Kantenmenge $E$, jeder Kante $e\in E$ sind Anfangs- und Endpunkte als Knoten $\iota : E\ni e \mapsto \{u,v\}\subset V$ zugeordnet.  Die Abbildung $\iota$ heißt Inzidenzabbildung. 

Graphen sollte man sich als Bilder vorstellen. Für unsere Zwecke sind $V$ und $E$ endlich.
Ein Graph heißt einfach, falls zu zwei Knoten höchstens eine zugeordnete Kante existiert und für keine Kante Anfangs- und Endpunkte zusammenfallen. 

In einem gerichteten Graphen haben Kanten Richtungen, ihnen ist also statt einer Menge von bis zu zwei Knoten stets ein Paar von Knoten $E\ni e \mapsto (u,v)\in V\times V$ zugeordnet.  Ungerichtete Graphen können auch als gerichtete Graphen mit Kanten in jeweils beide Richtungen aufgefasst werden. Die angegebene Notation in diesem Abschnitt bezieht sich auf ungerichtete Graphen. 

\item
Wir schreiben $u\sim v$ falls es ein $e\in E$ mit $\{u,v\}=\iota(e)$ gibt.

Die \emph{Adjazenzmatrix} $A:\in \C^{V\times V}$ ist definiert durch ihre Einträge  $A = (a_{u,v}) _{u,v\in V}$
\[
    a_{u,v} = \begin{cases} 1 , \qquad & u\sim v \\ 0, &\text{sonst.} \end{cases}
\]

\item
Die Menge der Kanten, die zu einem gegebenen Knoten inzident sind sei
\[ E^u = \{ e\in E \mid u \in\iota(e) \}.\]
Dann ist der \emph{Knotengrad} von $u\in V$ definiert als 
\[ \deg (u) = \# E^u = \# \{ e\in E \mid u \in\iota(e) \}\]

\item
\emph{Volumen} des Graphen \[\vol(G) = \sum_{u\in V} \deg(u) \]

\item 
Funktionen und Vektorräume von Funktionen auf dem Graphen. Wir betrachten $f : V\to \C$ und versehen den Vektorraum
\[
    \mathrm L^2 :=  \C^V = \{ f : V\to \C \}
\]
mit Norm $\|\cdot\|$ und Skalarprodukt definiert durch
\[
    \|f \|^2 = \sum_{v\in V} |f(v)|^2 \deg(u) ,\qquad    \langle f,g\rangle = \sum_{u\in V} f(u) \overline{g(u)} \deg(u).
\]
Die Funktionen $\delta_u : V\to \C$
\[
   \delta_u (v) = \begin{cases} \frac1{\sqrt{\deg u}} ,\qquad &u=v\\ 0 ,&u\ne v \end{cases}
\]
parametrisiert durch $u\in V$ bilden eine Orthonormalbasis von $\mathrm L^2$. 

\item 
\emph{Dirichletform}
\[
   \mathcal E[f,g] =  \sum_{u\sim v} (f(u)-f(v)) \overline{(g(u)-g(v))},\qquad  \mathcal E[f] := \mathcal E[f,f] =   \sum_{u\sim v} |f(u)-f(v)|^2
\]
und (normierter) \emph{kombinatorischer Laplace} $\mathcal L : \C^V\to\C^V$ bestimmt durch
\[
   \mathcal E[f,g] = \langle \mathcal L f,g\rangle
\]

Dabei bezeichne $\sum_{u\sim v} = \sum_{e\in E}$ die Summe über alle Kanten des Graphen. Für jede Kante $e\in E$ sei dabei $\iota(e)=\{u,v\}$.

\item
Sei $G$ (vollständiger) Graph und  $\omega : V\times V\to[0,\infty)$ eine Gewichtsfunktion
mit 
\[
   \omega(u,v)=\omega(v,u) .
\]

Dann setzen wir
\[
    \deg_\omega(u) = \sum_v \omega(u,v) ,
   \qquad
   \vol_\omega(G) = \sum_u \deg_\omega(u)
\]
und nutzen
\[
    \|f\|_\omega^2 = \sum_u |f(u)|^2 \deg_\omega(u),\qquad \langle f,g\rangle_\omega = \sum_u f(u) \overline{g(u)} \deg_\omega(u) 
\]
als Norm und Skalarprodukt auf $\C^V$.


Für diesen gewichteten Graphen definiert man die gewichtete Dirichletform
\[
   \mathcal E_\omega [f]  =  \sum_{u, v}  |f(u)-f(v)|^2\, \omega(u,v) .
\]

Der (normierte) gewichtete kombinatorische Laplace $\mathcal L_\omega : \C^V\to\C^V$ erfüllt
\[
   \mathcal E_\omega[f,g] = \langle \mathcal L_\omega f,g\rangle_\omega
\]

\section*{Teilgraphen, Pfade}

\item
Ein \emph{Teilgraph} $G' \le G$ ist ein Tripel $(V',E',\iota')$ mit $V'\subset V$, $E'\subset E$ und $\iota' = \iota|_{E'}$.

\item
Ein \emph{Weg} in $G$ mit Endpunkten $u,v\in V$ und ist ein Teilgraph von $G$ in welchem alle von $u,v$ verschiedenen Knoten den Grad zwei besitzen. Der Graph $G$ heißt zusammenhängend, falls es zu jedem $u,v\in V$ einen Weg $P\le G$ mit Endpunkten $u$ und $v$ gibt.

Die \emph{Länge} $\ell(P)$ eines Weges $P$ ist die Anzahl seiner Kanten.
\item
Für einen Weg $P$  gilt $\vol(P) = 2 \ell(P)$. 

\item
Für $u,v\in V$ sei 
\[
   \dist(u,v) = \min \{ \ell(P) \mid \text{$P$ Weg mit Endpunkten $u,v$} \} 
\]
der \emph{Abstand} von $u$ und $v$ und
\[
    \mathcal P_{u,v} = \{ P\le G \mid  \text{$P$ Weg mit Endpunkten $u,v$ und Länge $\ell(P)=\dist(u,v)$} \} 
\] 
die Menge der kürzesten Wege von $u$ nach $v$.

\item
Für einen zusammenhängenden Graphen sei
\[ \diam (G)  = \max\{\dist(u,v) \mid u,v \in V \} \]
der \emph{Durchmesser}.
\item 
Für eine Teilmenge $S\subset V$ sei 
$( S, E|_{S}, \iota')$ mit
\[
    E|_{S}  = \{ e\in E : \iota(E) \subset S\} ,\qquad \iota' = \iota |_{E|_S}
\]
der induzierte Teilgraph. 

Wenn der Graph $G$ fest ist, wird der von $S$ induzierte Teilgraph ebenso mit $S$ bezeichnet. $\overline S$ sei dann der Teilgraph, der von $V\setminus S$ induziert wird.

\item 
Rand eines induzierten Teilgraphen:
\[
\partial S = \{ v\in G \mid \exists e\in E^v : \iota(e) \cap S \ne \varnothing \quad \text{und}\quad   \iota(e) \cap (V\setminus S) \ne \varnothing  \}
\]
Damit gilt $\partial S = \partial \overline{S}$, ebenso gilt $\partial G = \varnothing = \partial\varnothing$. 

\item
\[ E(S,\overline S) = \{ e\in E \mid \iota(e) \cap S \ne \varnothing \quad \text{und}\quad   \iota(e) \cap (\overline S) \ne \varnothing  \} \]

\section*{Funktionenräume} 

\item

Für $1\le p\le \infty$ versehen wir $\mathrm L^p :=\C^V$ entsprechend mit der Norm 
\[
\begin{split}
    \|f \|_p^p &= \sum_{v\in V} |f(v)|^p \deg(u)\qquad \text{für $1\le p<\infty$},\\
    \|f\|_\infty  &= \max_{v\in V} |f(v)| 
\end{split}
\] 
Obwohl auf $\C^V$ alle Normen äquivalent sind, ist es mitunter interessant diese Normen zu verwenden!


\end{enumerate}
\end{document}