%% LyX 1.3 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[10pt,twoside,twocolumn,german]{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{geometry} \geometry{verbose,a4paper,tmargin=20mm,bmargin=20mm,lmargin=20mm,rmargin=20mm,headheight=5mm,headsep=5mm,footskip=5mm} \pagestyle{headings} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \usepackage{float} \usepackage{amsmath} \usepackage{color} \usepackage{makeidx} \makeindex \usepackage{amssymb} \IfFileExists{url.sty}{\usepackage{url}} {\newcommand{\url}{\texttt}} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. \newcommand{\noun}[1]{\textsc{#1}} \floatstyle{ruled} \newfloat{algorithm}{tbp}{loa} \floatname{algorithm}{Algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \usepackage{gastex} %\renewcommand{\thesubsubsection}{\alph{subsubsection})} \usepackage[linktocpage,pdfpagelabels,colorlinks,hyperindex]{hyperref} \usepackage[T1]{fontenc} \usepackage{ae,aecompl} \usepackage{babel} \makeatother \begin{document} \title{Formelsammlung\\ diskrete Strukturen I} \author{} \date{Stand: 27.05.2005 - Version: 1.0.0\\ \noun{Erhältlich unter \url{http://privat.macrolab.de}}} \maketitle Diese Formelsammlung basiert auf der Vorlesung {}``Diskrete Strukturen 1 für Informatiker'' von Dr. Markus Wessler an der Universität Kassel im Sommersemester 2004. Die folgende Formelsammlung steht zum kostenlosen Download zur Verfügung. Das Urheberrecht und sonstige Rechte an dem Text verbleiben beim Verfasser, der keine Gewähr für die Richtigkeit und Vollständigkeit der Inhalte übernehmen kann. \tableofcontents{} Die hinter den Überschriften angegebenen Nummern beziehen sich auf die Seitenzahlen des Buches {}``Diskrete Mathematik'' von Martin Aigner (5. Auflage). Grundlagen der Logik und der Mengenlehre sind in meiner {}``Formelsammlung Mathe I/II für Informatiker'' nach zuschlagen. \section{Grundlagen\index{Grundlagen}} \subsection{Logik\index{Logik} \& Aussagen\index{Aussagen}} Eine \emph{Aussage} ist ein Sprachkonstrukt, das entweder wahr oder falsch ist. Für zwei Aussagen $A$ und $B$ exisiteren Verknüpfungen. \subsubsection{Verknüpfungen\index{Verknüpfungen}} \begin{itemize} \item Negation\index{Negation}\\ $\neg a$: nicht\index{nicht} $a$ \item Implikation\index{Implikation}\\ $a\Rightarrow b$: aus $a$ folgt\index{folgt} $b$ \item Äquivalenz\index{Äquivalenz}\\ $a\Longleftrightarrow b$: $a$ und $b$ sind äquivalent\index{äquivalent} (gleichwertig\index{gleichwertig}) \item Konjunktion\index{Konjungtion}\\ $a\wedge b$: $a$ und\index{und} $b$ \item Disjunktion\index{Disjunktion}\\ $a\vee b$: $a$ oder\index{oder} $b$ \item Antivalenz\index{Antivalenz} (XOR\index{XOR})\\ $a\ \dot{\vee}\ b$: entweder $a$ oder\index{oder} $b$ \end{itemize} \subsubsection{Rechenregeln} \begin{itemize} \item Kommutativgesetz\index{Kommutativgesetz}\\ $a\wedge b=b\wedge a$\\ $a\vee b=b\vee a$ \item Assoziativgesetz\index{Assoziativgesetz}\\ $\left(a\wedge b\right)\wedge c=a\wedge\left(b\wedge c\right)$\\ $\left(a\vee b\right)\vee c=a\vee\left(b\vee c\right)$ \item Distributivgesetz\index{Distributivgesetz}\\ $a\wedge\left(b\vee c\right)=\left(a\wedge b\right)\vee\left(a\wedge c\right)$\\ $a\vee\left(b\wedge c\right)=\left(a\vee b\right)\wedge\left(a\vee c\right)$ \item De Morgan\index{De Morgan}\\ $\neg\left(a\vee b\right)=\left(\neg a\right)\wedge\left(\neg b\right)$\\ $\neg\left(a\wedge b\right)=\left(\neg a\right)\vee\left(\neg b\right)$ \item doppelte Negation\\ $\neg\left(\neg a\right)=a$ \item neutrales Element\index{Neutrales Element}\\ $a\vee\textrm{f}=a$\\ $a\wedge\textrm{f}=\textrm{f}$\\ $a\vee\textrm{w}=\textrm{w}$\\ $a\wedge\textrm{w}=a$ \item inverses Element\index{inverses Element}\\ $a\vee\left(\neg a\right)=\textrm{w}$\\ $a\wedge\left(\neg a\right)=\textrm{f}$ \end{itemize} \subsubsection{Quantoren\index{Quantifikatoren}} \begin{itemize} \item Allquantor\index{Allquantor} $\forall x:\varphi(x)$ \\ für alle $x$ gilt $\varphi(x)$.\\ z.B. $\forall x\in\mathbb{N}:x^{2}\in\mathbb{N}=\forall_{\mathbb{N}}^{x}:x^{2}\in\mathbb{N}$ \item Existenzquantor\index{Existenzquantor} $\exists x:\varphi(x)$ \\ es gibt (mindestens) ein $x$ für das $\varphi(x)$ gilt.\\ z.B. $\exists x\in\mathbb{N}:\varphi(x)=\exists_{\mathbb{N}}^{x}:\varphi(x)$ \item $\exists!x:\varphi(x)$ oder $\exists^{1}x:\varphi(x)$\\ es gibt genau ein $x$ für das $\varphi(x)$ gilt. \item Negation\index{Negation} $\forall x:H(x)\Leftrightarrow\neg\exists x:\neg H(x)$\\ Es gilt für alle $x$, $H(x)$ $\Leftrightarrow$ Es gibt nicht ein $x$, für das $H(x)$ nicht gilt. \end{itemize} \subsubsection{Eigenschaften von Aussagen} \begin{description} \item [Widerspruch](Symbol: Blitz (\textbackslash{}lightning)) heißt eine zusammengesetzte Aussage, wenn sie \emph{immer falsch} ist.\\ z.B. $A\wedge\neg A$ \item [Tautologie]heißt eine Aussage, wenn sie \emph{immer wahr} ist.\\ z.B. $A\vee\neg A$ \end{description} \subsection{Mengen\index{Mengen}} Eine \emph{Menge} ist die Gesamtheit\index{Gesamtheit} einer Zahl von Objekten\index{Objekten} unserer Anschauung oder Intuition (nach dem Mathematiker Cantor)). Die Objekte heißen Elemente\index{Elemente} und wir schreiben $a\in M$ ($a$ ist Element der Menge $A$) bzw. $a\notin A\Leftrightarrow\neg\left(a\in M\right)$. \subsubsection{Beschreibung} \begin{description} \item [Aufzählung\index{Aufzählung}]$W=\left\{ Montag,Dienstag,\ldots\right\} $ \item [Beschreibung\index{Bescheibung}]$\mathbb{Z}=$Menge der ganzen Zahlen \item [Auswahl\index{Auswahl}]$M=\left\{ x\in\mathbb{Z}|x\; ist\; gerade\right\} $ \end{description} \begin{itemize} \item $|$ mit der Eigenschaft \end{itemize} \subsubsection{\label{sub:Standdardmengen}Standardmengen\index{Standdardmengen}} \begin{itemize} \item Leere~Menge\index{Menge}\\ $\textrm{Ø}=\{\}$ \item Natürlichen~Zahlen\index{Zalen}\index{Natürliche Zalen}\\ $\mathbb{N}=\left\{ 1,2,3,\ldots\right\} $ \begin{itemize} \item Natürlichen~Zahlen mit $0$\\ $\mathbb{N}_{0}=\left\{ 0,1,2,3,\ldots\right\} $ \end{itemize} \item Ganzen~Zahlen\index{Ganze Zalen} \\ $\mathbb{Z}=\left\{ \ldots,-2,-1,0,1,2,\ldots\right\} $ \item Rationalen~Zahlen\index{Rationale Zalen}\\ $\mathbb{Q}=\left\{ \frac{p}{q}|p\in\mathbb{Z}\wedge q\in\mathbb{N}\right\} $ \item Reellen~Zahlen\index{Reelle Zahlen}\\ $\mathbb{R}=\left\{ \textrm{jeder\ Punkt\ auf\ dem\ Zahlenstrahl}\right\} $ \begin{itemize} \item positiven reellen Zahlen\\ $\mathbb{R}_{>0}=\left\{ x\in\mathbb{R}|x>0\right\} $ \end{itemize} \item Komplexen~Zahlen\index{Komplexe Zahlen}\\ $\mathbb{Z}=\left\{ x+iy|x,y\in\mathbb{R},\; i=\sqrt{-1}\right\} $ \item $\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}$ \end{itemize} \subsubsection{Intervalle\index{Intervall}} \begin{itemize} \item offenes Intervall\index{offenes Intervall}\\ $\left(a,b\right):=\left\{ x\in\mathbb{R}|a\left|T\right|$, so ist $f$ nicht injektiv\index{injektiv}. \subsection{Permutationen\index{Permutationen}} \subsubsection{Definition} Eine Permutation ist eine Auswahl von $n$ Elementen aus einer $n$-elementigen Menge mit Berücksichtigung der Reihenfolge. Eine Permutation ist eine bijektive\index{bijektiv} Abbildung $\sigma:\left\{ 1,\ldots,n\right\} \rightarrow\left\{ 1,\ldots,n\right\} $. Die Menge aller solchen Permutationen heißt \emph{symmetrische Gruppe\index{symmetrische Gruppe}} und wir bezeichnen sie mit $S_{n}$ \begin{itemize} \item $\left|S_{n}\right|=n!$ \end{itemize} \subsubsection{Zyklus\index{Zyklus}} Ein \emph{Zyklus\index{Zyklus}} $\left(i_{1},\ldots,i_{t}\right)$ der Länge $t$ einer Permutation $\sigma$ ist ein Tupel mit $\sigma\left(i_{j}\right)=i_{j+1}$, $\sigma\left(i_{t}\right)=i_{1}$. \begin{itemize} \item Jede Permutation lässt sich aus Zyklen zusammensetzen, wo jede Ziffer insgesamt nur einmal vorkommt \item Ein Zweierzyklus\index{Zweierzyklus} wird auch Transposition\index{Transposition} genannt. \item Ein Zyklus der Länge $t$ kann man auf $t$ verschiedene weisen schreiben, die wir aber miteinander Identifizieren \item Ein Zyklus ist eine Art {}``Ring-Rechtsshift'' der dazugehörigen Einträge in der Permutation \item Zyklen sind elementfremd\index{elementfremd}, wenn sie keine Ziffer gemeinsam haben \item elementfremde Zyklen lassen sich in ihrer Reihenfolge vertauschen \item Einerzykel (enthalten nur eine Ziffer) ändern nicht die Reihenfolge, und müssen nicht hingeschrieben werden, wohl aber mitgezählt \item z.B: eine 6er Permutation aus 3 Zyklen\\ \begin{eqnarray*} \sigma & = & \left(\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 5 & 3 & 4 & 6\end{array}\right)\\ & = & \left(1,2\right)\left(3,5,4\right)\left(6\right)\end{eqnarray*} \end{itemize} \subsubsection{Stirlingzahl\index{Stirlingzahl}} Die Anzahl $s_{n,k}$ von Permutationen $\sigma\in S_{n}$, die aus genau $k$ Zyklen besteht, heißt \emph{Stirlingzahl} 1.Art (jede Ziffer taucht nur einmal auf / Zyklen sind elementfremd\index{elementfremd}) \begin{itemize} \item $s_{n,n}=1$\\ nur identische Abbildung möglich $\sigma=\left(1\right)\left(2\right)\ldots\left(n\right)$ \item Für $n,k\in\mathbb{N}\left(n\geq k\right)$ gilt: \\ $s_{n,k}=s_{n-1,k-1}+\left(n-1\right)s_{n-1,k}$ \item $\sum_{k=1}^{n}s_{n,k}x^{k}=\frac{\left(x+n-1\right)!}{\left(x-1\right)!}$ \end{itemize} \section{Rekursionen\index{Rekursionen}} \subsection{Lineare Rekursionsgleichungen\index{Rekursionsgleichungen!Lineare}\index{Rekursionsgleichungen}} \subsubsection{Definition} Eine Gleichung der Form\[ a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\ldots+c_{k}a_{n-k}+b_{k}\left(n\geq k\right)\] mit den Anfangsbedingungen\[ a_{0}=b_{0},\ a_{1}=b_{1},\ \ldots\ ,\ a_{k-1}=b_{k-1}\] heißt lineare Rekursionsgleichung (RG\index{RG}) $k$-ter Ordnung. Für $b_{k}=0$ heißt die Gleichung homogen\index{homogen}, sonst inhomogen\index{inhomogen}. Ziel ist es einen geschlossenen Ausdruck\index{geschlossener Ausdruck} zu finden. \subsubsection{lineare Rekursionsgleichung 1.~Ordnung} Eine (inhomogene) lineare RG 1.Ordnung\[ a_{0}=b_{0},\; a_{n}=c_{1}a_{n-1}+b_{1}\quad\left(n\geq1\right)\] hat die Lösung\[ a_{n}=\left\{ \begin{array}{cc} c_{1}^{n}b_{0} & \left(b_{1}=0\right)\\ b_{0}+nb_{1} & \left(c_{1}=1\right)\\ c_{1}^{n}b_{0}+\frac{c_{1}^{n}-1}{c_{1}-1}b_{1} & \left(sonst\right)\end{array}\right.\] \subsubsection{lineare Rekursionsgleichung 2.~Ordnung} Eine \emph{homogene} lineare RG 2. Ordnung hat\[ a_{0}=b_{0},\; a_{1}=b_{1},\; a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}\left(n\geq2\right)\] \begin{itemize} \item bei $c_{1}^{2}+4c_{2}>0$ die Reelle Lösung:\[ a_{n}=A\alpha^{n}-B\beta^{n}\] wobei $\alpha,\beta$ die zwei (verschiedenen) Lösungen der Gleichung \\ $t^{2}-c_{1}t-c_{2}=0$ sind \[ \alpha=\frac{c_{1}}{2}+\sqrt{\frac{c_{1}^{2}}{4}+c_{2}}\quad\beta=\frac{c_{1}}{2}-\sqrt{\frac{c_{1}^{2}}{4}+c_{2}}\] und \[ A=\frac{b_{1}-b_{0}\beta}{\alpha-\beta}\quad B=\frac{b_{1}-b_{0}\alpha}{\alpha-\beta}\] \item bei $c_{1}^{2}+4c_{2}=0$ die Reelle Lösung:\[ a_{n}=\left(nb_{1}-\left(n-1\right)\alpha b_{0}\right)\alpha^{n-1}\quad\alpha=\frac{c_{1}}{2}\] \item bei $c_{1}^{2}+4c_{2}<0$ die komplexe Lösungen. Formeln siehe bei $c_{1}^{2}+4c_{2}>0$. \end{itemize} \subsubsection{Fibonacci-Folge\index{Fibonacci-Folge}} Die Fibonacci-Folge\[ F_{0}=0,\; F_{1}=1,\; F_{n}=F_{n-1}+F_{n-2}\left(n\geq2\right)\] hat die Lösung:\[ F_{n}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}\] \begin{itemize} \item $F_{n+1}=\sum_{k=0}^{n}\left(\begin{array}{c} n-k\\ k\end{array}\right)$ \item $F_{2n-1}=F_{n-1}^{2}+F_{n}^{2}$ \item $F_{2n}=F_{n}\left(2F_{n-1}+F_{n}\right)$ \item $\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^{n}=\left(\begin{array}{cc} F_{n+1} & F_{n}\\ F_{n} & F_{n-1}\end{array}\right)\quad\left(n\geq1\right)$ \end{itemize} \subsection{Erzeugende Funktionen\index{Erzeugende Funktionen}} \subsubsection{Definition} Sei $\left(a_{n}\right)_{n\in\mathbb{N}_{0}}$ eine Folge\index{Folge}. Die formale Potenzreihe\index{Potenzreihe} \[ A\left(x\right):=\sum_{n\geq0}a_{n}x^{n}\] heißt \emph{erzeugende Funktion} zur Folge $\left(a_{n}\right)$. \subsubsection{Rechenregeln} Sind $\left(a_{n}\right),\left(b_{n}\right)$ zwei Folgen mit entsprechenden Funktionen $A\left(x\right),B\left(x\right)$, dann: \begin{description} \item [Summe\index{Summe}]$\left(c_{n}\right):=\left(a_{n}+b_{n}\right)$\\ Hat erzeugende Funktion $C\left(x\right)=\sum_{n\geq0}c_{n}x^{n}$ und wir schreiben $C\left(x\right)=A\left(x\right)+B\left(x\right)$ \item [Produkt\index{Produkt}]$\left(c_{n}\right):=\left(\sum_{k=0}^{n}a_{k}b_{n-k}\right)$\\ Hat erzeugende Funktion $C\left(x\right)=\sum_{n\geq0}c_{n}x^{n}$ und wir schreiben $C\left(x\right)=A\left(x\right)B\left(x\right)$ \end{description} \begin{itemize} \item Erzeugende Funktionen lassen sich gliedweise Integrieren\index{Integrieren} und Differenzieren\index{Differenzieren}, um so neue erzeugende Funktionen zu konstruieren. \end{itemize} \subsubsection{Inverse\index{Inverse}} Sei $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ erzeugende Funktion zu $\left(a_{n}\right)$. Dann heißt die erzeugende Funktion $B\left(x\right)=\sum_{n\geq0}b_{n}x^{n}$ \emph{invers zu} $A\left(x\right)$, falls $A\left(x\right)B\left(x\right)=1$ \begin{itemize} \item Hier ist $1$ die erzeugende Funktion zur Folge $\left(1,0,0,\ldots\right)$ \item Die erzeugende Funktion $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ hat eine inverse erzeugende Funktion (auch: $A\left(x\right)$ ist invertierbar) genau dann, wenn $a_{0}\neq0$ \end{itemize} \subsubsection{Wichtige Erzeugende Funktionen} \begin{itemize} \item geometrische Reihe\index{geometrische Reihe}\\ $\sum_{n\geq0}\left(\alpha x\right)^{n}=\frac{1}{1-\alpha x}$ \item $\sum_{n\geq0}\left(n\right)x^{n}=\frac{x}{\left(1-x\right)^{2}}$ \item $\sum_{n\geq0}\left(n+1\right)x^{n}=\frac{1}{\left(1-x\right)^{2}}$ \item $\sum_{n\geq0}\left(\begin{array}{c} n+k\\ k\end{array}\right)x^{n}=\frac{1}{\left(1-x\right)^{k+1}}$ \item $\sum_{n\geq0}n^{2}x^{n}=\frac{x\left(x+1\right)}{\left(1-x\right)^{3}}$ \item $b_{n}=\sum_{k=0}^{n}a_{k}$ die Folgen zu den erzeugenden Funktionen $A\left(x\right),B\left(x\right)$\\ $B\left(x\right)=\frac{A\left(x\right)}{1-x}$ \end{itemize} \subsubsection{Lösen von linearen Rekursionsgleichungen durch erzeugende Funktionen} \begin{description} \item [Gegeben]ist eine lineare Rekursionsgleichung $k$-ter Ordnung\[ {\scriptstyle a_{0}=b_{0},\ldots,a_{k-1}=b_{k-1}\quad a_{n}=\sum_{i=1}^{k}c_{i}a_{n-i}\ \left(n\geq k\right)}\] \item [Ansatz](Siehe Algorithmus 1 auf der nächsten Seite) Hierbei ersetzt man $A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ durch die Rekursionsdefinition. Dabei entstehen Terme die wieder nur ein $a_{n}$ mit verschobenen Summationsbereich enthalten. Hier kann man nun durch Umformung das ganze wieder in ein Polynom plus $A\left(x\right)$ bringen. \end{description} % \begin{algorithm*}[th] \caption{: Ansatz zum Lösen von LRG mit erzeugenden Funktionen} \begin{description} \item [Ansatz]$A\left(x\right)=\sum_{n\geq0}a_{n}x^{n}$ \item [Startwerte~einsetzten]$A\left(x\right)=\sum_{i=0}^{k-1}b_{i}x^{i}+\sum_{n\geq k}a_{n}x^{n}$ \item [Rekursion~einsetzten]$A\left(x\right)=\sum_{i=0}^{k-1}b_{i}x^{i}+\sum_{i=1}^{k}\left(\sum_{n\geq k}c_{i}a_{n-i}x^{n}\right)$ \item [Index~verschieben]$A\left(x\right)=\sum_{i=0}^{k-1}b_{i}x^{i}+\sum_{i=1}^{k}\left(c_{i}x^{i}\sum_{n\geq k-i}a_{n}x^{n}\right)$ \item [Ergänzen~und~$A\left(x\right)$~ersetzen]~\\ $A\left(x\right)=\sum_{i=0}^{k-1}b_{i}x^{i}+\sum_{i=1}^{k-1}\left(c_{i}x^{i}\left(A\left(x\right)-\sum_{n=0}^{k-i-1}a_{n}x^{n}\right)\right)+c_{k}x^{k}A\left(x\right)$ \end{description} \end{algorithm*} \begin{description} \item [Koeffizienten~Zusammenfassen](aus letzter Gleichung) zu $d_{i}$\begin{eqnarray*} A\left(x\right) & = & \sum_{i=0}^{k-1}d_{i}x^{i}+A\left(x\right)\sum_{i=1}^{k}\left(c_{i}x^{i}\right)\\ & = & \frac{\sum_{i=0}^{k-1}d_{i}x^{i}}{1-\sum_{i=1}^{k}\left(c_{i}x^{i}\right)}\end{eqnarray*} \item [Faktorisieren~des~Nenners](Bestimmen von $\alpha_{i}$ und $m_{i}$)\[ 1-\sum_{i=1}^{k}\left(c_{i}x^{i}\right)=\prod_{i=1}^{r}\left(1-\alpha_{i}x\right)^{m_{i}}\] \item [Partialbruchbruchzerlegung](Bestimmen von $g_{i}\left(x\right)$)\\ $A\left(x\right)=\sum_{i=1}^{r}\frac{g_{i}\left(x\right)}{\left(1-\alpha_{i}x\right)^{m_{i}}}$\\ $g_{i}\left(x\right)$ wird von $x$ unabhängig, wenn beim Faktorisieren des Nenners komplexe Lösungen zugelassen werden. Dies erleichtert die Anwendung des nächsten Punktes. \item [Erstellen~von~Erzeugenden~Funktion]für $A\left(x\right)$\\ \end{description} \[ {\scriptscriptstyle A\left(x\right)=\sum_{n\geq0}\left(\underbrace{\sum_{i=1}^{r}\left(g_{i}\left(x\right)\left(\begin{array}{c} m_{i}-1+n\\ n\end{array}\right)\alpha_{i}^{n}\right)}_{f}x^{n}\right)}\] \begin{description} \item [Koeffizientenvergleich]~\\ Wenn alle $g_{i}$ nicht von $x$ abhängig sind, so ist $f=a_{n}$, wenn nicht muss diese Formel noch etwas umgestellt werden. Hiermit wäre ein geschlossener Ausdruck für $a_{n}$ gefunden. \end{description} \section{Graphentheorie\index{Graphentheorie}} \subsection{Grundlagen} \subsubsection{Definition Graph} Ein \emph{schlichter Graph\index{schlichter Graph}} ist ein Paar $G=\left(E,K\right)$, wobei $E=\left\{ v_{1},\ldots,v_{n}\right\} $ eine endliche nicht leere Menge von \emph{Ecken\index{Ecken}} und $K\subseteq\left\{ \left\{ v_{i},v_{j}\right\} |i\neq j\right\} $ eine Menge von \emph{Kanten\index{Kanten}} ist. Ein \emph{Graph\index{Graph}} (manchmal auch {}``\emph{Multipgraph\index{Multipgraph}''} genannt) erlaubt zusätzlich \emph{Schleifen\index{Schleifen}} (d.h. $\left\{ v_{i},v_{i}\right\} $) und auch \emph{Mehrfachkanten\index{Mehrfachkanten}} (d.h. $\left\{ v_{i},v_{j}\right\} _{n}$ hat eine Vielfachheit von $n$) mit einer gewissen Vielfachheit. \begin{itemize} \item $G$ schlicht und $\left|E\right|=n\Rightarrow\left|k\right|\leq\left({{n\atop 2}}\right)$ \item $V_{n}=$ \emph{vollständiger (schlichter) Graph}\index{vollstaendiger schlichter Graph}. D.h. das alle Ecken über kanten mit jeder anderen Ecke verbunden sind. \begin{itemize} \item $V_{2n+1}$ ist eulersch \item $V_{n}$ ist $\left(n-1\right)$-regulär \item $V_{n}$ ist mit $n\geq5$ nicht plättbar \end{itemize} \item \emph{Hyperwürfel}\index{Hyperwuerfel} \begin{itemize} \item der $0$-dimensionale Hyperwürfel hat eine Ecke, und keine Kante \item jeder Hyperwürfel ist hamiltonisch \item Hat der $d$-dimensionale Hyperwürfel $\left(E,K\right)$ die Ecken $v_{1},\ldots,v_{2^{d}}$, so hat der $\left(d+1\right)$-dimensionale Hyperwürfel die Ecken $w_{1},\ldots,w_{2^{d}},w'_{1},\ldots,w'_{2^{d}}$ und die Kanten \begin{eqnarray*} & {\scriptstyle \left\{ \left\{ w_{i},w_{j}\right\} ,\left\{ w_{i},w_{j}\right\} |i\neq j\wedge\left\{ v_{i},v_{j}\right\} \in K\right\} }\\ & {\scriptstyle \cup\left\{ \left\{ w_{i},w'_{i}\right\} |1\leq i\leq2^{d}\right\} }\end{eqnarray*} \item ein $d$-dimensionaler Hyperwürfel ist $d$-regulär \item ein $2n$-dimensionaler Hyperwürfel ist ist eulersch \end{itemize} \end{itemize} \subsubsection{Grad \& Gradfolge} Sei $G=\left(E,K\right)$ ein Graph mit $E=\left\{ v_{1},\ldots,v_{n}\right\} $. Der \emph{Grad}\index{Grad} der Ecke $v$ ist \[ \deg\left(v\right)=\left|\left\{ z\in G|v\in z\right\} \right|\] Schleifen müssen hierbei doppelt gezählt werden! Der Grad gibt die Anzahl der Kanten an, die $v$ als Ecke haben. Das $n$-Tupel $\left(\deg\left(v_{1}\right),\ldots\deg\left(v_{n}\right)\right)$ heißt \emph{Gradfolge\index{Gradfolge}} von $G$. \begin{itemize} \item $\sum_{v\in E}\deg\left(v\right)=2\left|K\right|$ \item Die Anzahl der Ecken mit ungeradem Grad ist gerade \item Es gibt einen schlichten Graphen $G$ mit der Gradfolge $\left(d_{1},\ldots,d_{n}\right)$ mit $d_{1}\geq\ldots\geq d_{n}$ genau dann, wenn es einen Graphen mit der Gradfolge $\left(d_{2}-1,\ldots,d_{d_{1}+1}-1,d_{d_{1}+2},\ldots,d_{n}\right)$ gibt. \end{itemize} \subsubsection{Regulär\index{Regulär}} Der Graph $G=\left(E,K\right)$ heißt \emph{$k$-regulär\index{regulär}}, falls alle Ecken von G den selben Grad $k$ haben. \begin{itemize} \item $V_{n}$ ist $\left(n-1\right)$-regulär \end{itemize} \subsection{Eulersche und hamiltonische Graphen} \subsubsection{Weg \& Eigenschaften} Sei $G=\left(E,K\right)$ ein Graph, und $v,e\in E$. Ein \emph{Weg\index{Weg}} von $v$ nach $w$ ist eine Folge von Ecken $\left(v=v_{1},v_{2},\ldots,v_{m}=w\right)$ mit der Eigenschaft, dass alle $\left\{ v_{i},v_{i+1}\right\} \in K$ (Kanten von $G$) sind. Der Weg heißt \emph{geschlossen\index{geschlossener Weg}} (bzw. \emph{offen\index{offener Weg}}), falls $v=w$ (bzw. $v\neq w$). Der Weg heißt \emph{(Kanten-)einfach\index{kanteneinfach}\index{einfach}}, falls alle Kanten $\left\{ v_{i},v_{i+1}\right\} $ paarweise verschieden sind. Der Weg heißt \emph{eckeneinfach\index{eckeneinfach}}, falls alle Ecken $v_{i}$ paarweise verschieden sind (für $i=1,\ldots,m-1$). Die \emph{Länge\index{Laenge}} eines Weges, ist die Anzahl der Kanten, die er enthält. \begin{itemize} \item eckeneinfach $\Rightarrow$ kanteneinfach \end{itemize} \subsubsection{Abstand \& Durchmesser} Bei einem zusammenhängenden Graphen ist der \emph{Abstand\index{Abstand}} zweier Ecken die Länge des kürzesten Weges, der diese Ecken verbindet. Der \emph{Durchmesser\index{Durchmesser}} ist der maximale Abstand zweier Ecken. \subsubsection{eulerscher Graph} $G$ heißt \emph{eulerscher Graph\index{eulerscher Graph}}, falls es in $G$ einen geschlossenen (Kanten-)einfachen Weg gibt, der jede Kante von $G$ enthält. Diesen Weg nennen wir \emph{eulersche Linie\index{eulersche Linie}}. \begin{itemize} \item $G$ ist eulerscher Graph $\Leftrightarrow$ jede Ecke von $G$ hat geraden Grad und $G$ ist zusammenhängend \item Problem der Königsberger Brücken \end{itemize} \subsubsection{zusammenhängend} Ein Graph $G$ heißt \emph{zusammenhängend\index{zusammenhängend}}, falls je $2$ verschiedene Ecken durch einen (offenen) eckeneinfachen Weg verbunden werden können. \subsubsection{Kreis} Sei $G=\left(E,K\right)$ ein Graph. Ein geschlossener eckeneinfacher Weg in $G$ heißt \emph{Kreis\index{Kreis}}. \subsubsection{Teilgraph} Sei $G=\left(E_{G},K_{G}\right)$ ein Graph. Ein Graph $H=\left(E_{H},K_{H}\right)$ heißt \emph{Teilgraph\index{Teilgraph}} von $G$, falls $E_{H}\subseteq E_{G}$ und $K_{H}\subseteq K_{G}$. \subsubsection{hamiltonischer Graph} Sei $G$ ein Graph. Falls es in $G$ einen Kreis gibt, der alle Ecken von $G$ enthält, so heißt $G$ ein \emph{hamiltonischer Graph\index{hamiltonischer Graph}} und der Kreis heißt \emph{Hamiltonkreis\index{Hamiltonkreis}}. \begin{itemize} \item Ist $G$ ein hamiltonischer Graph, so besitzt $G$ einen Teilgraphen $H$ mit: \begin{itemize} \item $E_{H}=E_{G}$ \item $H$ ist zusammenhängend \item $\left|E_{H}\right|=\left|K_{H}\right|$ \end{itemize} \item Traveling Salesman Problem \end{itemize} \subsubsection{Adjazenzmatrix} Die \emph{Adjazenzmatrix\index{Adjazenzmatrix}} zu einem Graphen mit $v_{1},\ldots,v_{n}$ ist die $n\times n$-Martix $M=\left(a_{ij}\right)$, wobei $a_{ij}$die Anzahl der Kanten zwischen der Ecke $v_{i}$ und $v_{j}$ ist. $M^{k}=\left(b_{ij}\right)$ gibt mit $b_{ij}$ an, wie viele Wege der Länge $k$ es zwischen $i$ und $j$ gibt. \subsection{Bipartite Graphen} \subsubsection{bipartit \& Matching} Ein Graph $G=\left(E,K\right)$ heißt \emph{bipartit\index{bipartit}}, falls $E=E_{1}\dot{\cup}E_{2}$ und $K$ nur aus Knoten besteht, die jeweils eine Ecke aus $E_{1}$ mit einer aus $E_{2}$ verbinden. Eine Teilmenge $K'\subseteq K$ heißt \emph{Matching\index{Matching}}, falls keine zwei Kanten aus $K'$ eine gemeinsame Ecke besitzen. Ein Matching heißt \emph{perfekt\index{perfekt}}, falls $\left|K'\right|=\left|E_{1}\right|$ oder $\left|K'\right|=\left|E_{2}\right|$. \begin{itemize} \item ein bipartiter Graph $G_{m,n}$ (mit $\left|E_{1}\right|=n$ und $\left|E_{2}\right|=m$), heißt \emph{vollständig\index{vollstaendig}}, wenn je zwei Ecken aus verschiedenen Ecken durch eine Kante verbunden sind. \begin{itemize} \item für $n,m$ gerade $\Leftrightarrow$ $G_{m,n}$ ist eulersch\index{eulersch} \item für $n=m\geq2\Leftrightarrow G_{m,n}$ hamiltonisch\index{hamiltonisch} \item GEW\index{GEW}-Graph: $n=3\; m=3$ \item für $n,m\geq3$ ist $G_{m,n}$ nicht plättbar \end{itemize} \end{itemize} \subsubsection{Heiratssatz\index{Heiratssatz} / Existenz eines perfekten\index{perfekt} Matching\index{Matching}} Sei $G=\left(E_{1}\dot{\cup}E_{2},K\right)$ ein bipartiter Graph. Für jede Teilmenge $U\subseteq E_{1}$ definieren wir $\deg\left(U\right):=$ Anzahl der Ecken aus $E_{2}$, die mit einer Ecke aus $U$ verbunden sind. Dann gilt: $U$ besitzt ein perfektes Matching, genau dann wenn $\forall U\subseteq E_{1}:\deg\left(U\right)\geq\left|U\right|$. \begin{itemize} \item $\deg\left(U\right)\leq\sum_{v\in U}\deg\left(v\right)$ \item jeder bipartite $k$-reguläre Graph hat ein perfektes Matching \item Wenn $\left|E_{1}\right|\neq\left|E_{2}\right|\Rightarrow$ Kanten weglassen und Teilgraph betrachten \end{itemize} \subsection{Bäume} \subsubsection{Baum \& Blätter} Ein \emph{Baum\index{Baum}} ist ein zusammenhängender Graph ohne Kreis. Die Ecken vom Grad $1$ heißen \emph{Blätter}\index{Blaetter}. \begin{itemize} \item Jeder Baum mit mehr als einer Ecke, hat (mindestens) ein Blatt \item Jeder zusammenhängende Graph $G$ mit $n$ Ecken ist genau dann ein Baum, wenn er $n-1$ Kanten hat. \end{itemize} \subsubsection{aufspannender Baum} Sei $G=\left(E,K\right)$ ein Graph. Ein Teilgraph von G heißt \emph{aufspannender Baum von $G$\index{aufspannender Baum}}, falls es ein Baum ist, der alle Ecken von $G$ enthält. \begin{itemize} \item jeder zusammenhängende Graph besitzt einen aufspannenden Baum \end{itemize} \subsection{Eulerscher Satz} \subsubsection{Äquivalenz von Graphen / ebene Graphen} Ein zusammenhängender Graph heißt \emph{eben\index{eben}}, falls sich keine Kanten kreuzen. Zwei Graphen $G=\left(E,K\right)$ und $G'=\left(E',K'\right)$ heißen \emph{äquivalent\index{aequivalenz von Graphen}}, falls es eine bijektive Abbildung $\varphi:E\rightarrow E'$ gibt, so dass $\left\{ v,w\right\} $ eine Kante von $G$ ist, genau dann wenn $\left\{ \varphi\left(v\right),\varphi\left(w\right)\right\} $ eine Kante von $G'$ ist. Ein Graph, der zu einem ebenen Graphen äquivalent ist, heißt \emph{plättbar\index{plaettbar}}. \subsubsection{Eulerscher Satz\index{Eulerscher Satz}} In einem Graphen mit $e$ Ecken, $k$ Kanten und $f$ Flächen (von den Kanten abgetrennt) gilt stets\[ e-k+f=2\] \begin{itemize} \item Maximale Kantenanzahl bei einem plättbaren Graphen mit $n$ ($\geq3$) Ecken.\[ k\left(n\right)=3\left(n-2\right)\] \end{itemize} \subsubsection{Satz von Kuratowski\index{Kuratowski}} Ein Graph ist genau dann nicht plättbar, wenn er $V_{5}$ oder $GEW$ als Teilgraphen enthält. \begin{itemize} \item Der $GEW$-Graph\index{GEW-Graph} (der vollständige bipartite $3$-Graph, $G_{3,3}$) ist nicht plättbar \begin{itemize} \item Problem 3 Häuser mit 3 Versorgern (\emph{G}aß\emph{, E}lektrizität, \emph{W}asser) kreuzungsfrei zu verbinden. \end{itemize} \item $V_{5}$ ist nicht plättbar \end{itemize} \section{Wahrscheinlichkeitstheorie\index{Wahrscheinlichkeitstheorie}} \subsection{Diskrete Wahrscheinlichkeitstheorie\index{Wahrscheinlichkeitstheorie!Diskrete}} \subsubsection{Definitionen} Sei $\Omega$ eine höchstens abzählbare Menge (d.h. es gibt eine surjektive Abbildung $f:\mathbb{N}\rightarrow\Omega$) und sei $P:\mathcal{P}\left(\Omega\right)\rightarrow\left[0,1\right]$ ($P$ von \emph{P}robability = Wahrscheinlichkeit) eine Abbildung mit den Eigenschaften: \begin{itemize} \item $P\left(\Omega\right)=1$ \item $P$ ist additiv auf disjunkten Mengen:\\ $P\left(\dot{\cup}_{n\geq0}A_{n}\right)=\sum_{n\geq0}P\left(A_{n}\right)$ \end{itemize} Dann heißt $\left(\Omega,P\right)$ ein \emph{diskreter Wahrscheinlichkeitsraum\index{diskreter Wahrscheinlichkeitsraum}\index{Wahrscheinlichkeitsraum!diskreter}\index{Wahrscheinlichkeitsraum}} (\emph{endlicher Wahrscheinlichkeitsraum\index{Wahrscheinlichkeitsraum!endlicher}\index{endlicher Wahrscheinlichkeitsraum}\index{Wahrscheinlichkeitsraum}}, falls $\Omega$ endlich), und $P$ heißt die \emph{Wahrscheinlichkeitsverteilung\index{Wahrscheinlichkeitsverteilung}} auf $\Omega$. $P\left(A\right)$ nennen wir die \emph{Wahrscheinlichkeit\index{Wahrscheinlichkeit}} von $A$. Wir nennen $A\in\mathcal{P}\left(\Omega\right)$ ein \emph{Ereignis in $\Omega$\index{Ereignis}}, und falls $\left|A\right|=1$, \emph{Elementarereignis\index{Elementarereignis}}. $\bar{A}=\Omega\backslash A$ heißt \emph{Gegenereignis\index{Gegenereignis}} zu $A$. $\emptyset$ heißt \emph{unmögliches Ereignis \index{unmoegliches Ereignis}} und $\Omega$ \emph{sicheres Ereignis\index{sicheres Ereignis}}. \begin{itemize} \item $A\subseteq B\subseteq\Omega:$ \begin{itemize} \item $P\left(B\backslash A\right)=P\left(B\right)-P\left(A\right)$ \item $P\left(A\right)\leq P\left(B\right)$ \end{itemize} \item $P\left(\bar{A}\right)=1-P\left(A\right)$ \item $P\left(A\cup B\right)=P\left(A\right)+P\left(B\right)-P\left(A\cap B\right)$ \end{itemize} \subsubsection{Laplacescher Wahrscheinlichkeitsraum} $\left(\Omega,P\right)$ heißt \emph{Laplacescher Wahrscheinlichkeitsraum\index{Laplacescher Wahrscheinlichkeitsraum}}, falls $\left|\Omega\right|<\infty$ und $\forall_{\mathcal{P}\left(\Omega\right)}^{A}:P\left(A\right)=\frac{\left|A\right|}{\left|\Omega\right|}$. \begin{itemize} \item insbesondere $\forall_{\Omega}^{w}:P\left(\left\{ w\right\} \right)=\frac{1}{\left|\Omega\right|}$ \end{itemize} \subsubsection{bedingte Wahrscheinlichkeit} Sei $\left(\Omega,P\right)$ ein diskreter W-Raum, $A,B\subseteq\Omega$, $P\left(B\right)>0$.\[ P_{B}\left(A\right)=\frac{P\left(A\cap B\right)}{P\left(B\right)}=\frac{P_{A}\left(B\right)P\left(A\right)}{P\left(B\right)}\] heißt bedingte W-keit von $A$ bezüglich $B$ (d.h. die W-keit von $A$, falls man schon weiß, dass $B$ erfüllt ist). \begin{itemize} \item $\left(\Omega,P\right)$ ein diskreter W-Raum, $A_{1},\ldots,A_{n}\subseteq\Omega$, $P\left(A_{1}\cap\ldots\cap A_{n-1}\right)>0$. \end{itemize} \[ P\left(A_{1}\cap\ldots\cap A_{n}\right)=P\left(A_{1}\right)\prod_{i=2}^{n}P_{A_{1}\cap\ldots\cap A_{i-1}}\left(A_{i}\right)\] \subsubsection{Formel von der vollständigen Wahrscheinlichkeit\index{vollstaendige Wahrscheinlichkeit}} $\left(\Omega,P\right)$ ein diskreter W-Raum, $A_{1},\ldots,A_{n}\subseteq\Omega$ mit $\Omega=A_{1}\dot{\cup}A_{2}\dot{\cup}\ldots\dot{\cup}A_{n}$, P$\left(A_{i}\right)>0$, $B\subseteq\Omega$ mit $P\left(B\right)>0$. Dann: \[ P\left(B\right)=\sum_{i=1}^{n}P\left(A_{i}\right)P_{A_{i}}\left(B\right)\] \[ P_{B}\left(A_{i}\right)=\frac{P\left(A_{i}\right)P_{A_{i}}\left(B\right)}{\sum_{i=1}^{n}P\left(A_{i}\right)P_{A_{i}}\left(B\right)}\] \begin{itemize} \item Für $n=2$:\\ $P\left(B\right)=P\left(A\right)P_{A}\left(B\right)+P\left(\bar{A}\right)P_{\bar{A}}\left(B\right)$ \end{itemize} \subsection{Unabhängigkeit\index{Unabhaengigkeit} und Wahrscheinlichkeitsverteilung\index{Warscheinlichkeitsverteilung}} \subsubsection{Definition} Sei $\left(\Omega,P\right)$ ein diskreter W-Raum. Wir nennen zwei Ereignisse $A,B\subseteq\Omega$ \emph{unabhängig voneinander\index{unabhaengig voneinander}}, falls $P\left(B\right)=0$ oder $P\left(A\right)=P_{B}\left(A\right)$. Diese Aussage ist Äquivalent zu $P\left(A\cap B\right)=P\left(A\right)P\left(B\right)$. Allgemein heißen $A_{1},A_{2},\ldots,A_{n}\subseteq\Omega$ \emph{unabhängig voneinander\index{unabhaenig voneinander}}, falls für alle $\left\{ i_{1},\ldots,i_{k}\right\} \subseteq\left\{ 1,\ldots,n\right\} $ mit $k\geq2$ gilt:\[ P\left(A_{i_{1}}\cap\ldots\cap A_{i_{k}}\right)=\prod_{j=1}^{k}P\left(A_{i_{j}}\right)\] Eine Verteilungsfunktion $P^{n}:\Omega^{n}\rightarrow\left[0,1\right]$ die jedem $\left(A_{1},\ldots,A_{n}\right)\mapsto P^{n}\left(\left(A_{1},\ldots,A_{n}\right)\right)=\prod_{i=1}^{n}P\left(A_{i}\right)$ Tupel von Ereignissen eine Wahrscheinlichkeit zuordnet. \subsubsection{Binomialverteilung\index{Binomialverteilung}} Wir betrachten $\Omega=\left\{ 0,1\right\} $ mit $P\left(0\right)=p$ und $P\left(1\right)=1-p$. Die \emph{Binomialverteilung} \[ b_{n,p}\left(k\right)=\left({{n\atop k}}\right)p^{k}\left(1-p\right)^{n-k}\] gibt an, wie groß die Wahrscheinlichkeit ist, das bei $n$-maligen Wiederholen genau $k$-mal ein Ereigniss mit der Wahrscheinlichkeit $p$ auftritt. \begin{itemize} \item z.B. 10-maliger Münzwurf. Wie groß ist die Wahrscheinlichkeit, das genau 7 Mal Zahl kommt: $b_{10,\frac{1}{2}}\left(7\right)$ \item ist bezüglich verschiedenen $k$ disjunkt \item $E\left(X\right)=np$ \item $V\left(X\right)=np\left(1-p\right)=npq$ \end{itemize} \subsubsection{Hypergeometrische Verteilung\index{Hypergeometrische Verteilung}} Situation: Urne mit $n$ Kugeln, davon seien $n_{1}$ ausgezeichnet. Wir ziehen $r$ Kugeln $\left(r\leq n\right)$. Wie viele dieser $r$ Kugeln gehören zu den $n_{1}$ ausgezeichnet?\[ h_{n,n_{1},r}\left(k\right)=\frac{\left({{n_{1}\atop k}}\right)\left({{n-n_{1}\atop r-k}}\right)}{\left({{n\atop r}}\right)}\] \begin{itemize} \item ist bezüglich verschiedenen $k$ disjunkt \item Bei großen Zahlen $\left(r\ll n_{1}\right)$ lässt sich $h_{n,n_{1},r}\left(k\right)\approx b_{r,\frac{n_{1}}{n}}\left(k\right)$ annähern \item $E\left(X\right)=\frac{n_{1}}{n}r$ \end{itemize} \subsection{Erwartungswert und Varianz} \subsubsection{Zufallsvariable} Eine \emph{Zufallsvariable\index{Zufallsvariable}} ist eine Funktion $X:\Omega\rightarrow\mathbb{R}$. \subsubsection{Erwartungswert} Sei $\left(\Omega,P\right)$ ein diskreter W-Raum. Eine Zufallsvariable $X:\Omega\rightarrow\mathbb{R}$ gibt den Ausgang eines Zufallsexperiments in $\Omega$ an. Sie besitzt die Wertemenge $W=\left\{ X\left(a\right)|a\in\Omega\right\} $. Der \emph{Erwartungswert\index{Erwartungswert}} von $X$ ist \begin{eqnarray*} E\left(X\right) & = & \sum_{\mathrm{Werte}\ x\ \mathrm{von}\ X}x\ P\left(X\ \mathrm{nimmt}\ x\ \mathrm{an}\right)\\ & = & \sum_{x}x\ P\left(X=x\right)\\ & = & \sum_{x\in W}x\ P\left(X^{-1}\left(x\right)\right)\end{eqnarray*} \begin{itemize} \item $E\left(E\left(X\right)\right)=E\left(X\right)$ \item $E\left(aX+b\right)=aE\left(X\right)+b\quad\left(a\neq0\right)$ \item $E\left(X_{1}+X_{2}\right)=E\left(X_{1}\right)+E\left(X_{2}\right)$ \item Wenn $X_{1},X_{2}$ unabhängig sind:\\ $E\left(X_{1}X_{2}\right)=E\left(X_{1}\right)E\left(X_{2}\right)$ \end{itemize} \subsubsection{Varianz} Sei $\left(\Omega,P\right)$ ein diskreter W-Raum. Eine Zufallsvariable $X:\Omega\rightarrow\mathbb{R}$ gibt den Ausgang eines Zufallsexperiments in $\Omega$ an. Sie besitzt die Wertemenge $W=\left\{ X\left(a\right)|a\in\Omega\right\} $. Die \emph{Varianz\index{Varianz}} von $X$ ist \begin{eqnarray*} V\left(X\right) & = & E\left(\left(X-E\left(X\right)\right)^{2}\right)\\ & = & E\left(X^{2}\right)-\left(E\left(X\right)\right)^{2}\end{eqnarray*} \begin{itemize} \item $V\left(aX+b\right)=a^{2}V\left(X\right)\quad\left(a\neq0\right)$ \item Wenn $X_{1},X_{2}$ unabhängig sind:\\ $V\left(X_{1}+X_{2}\right)=V\left(X_{1}\right)+V\left(X_{2}\right)$ \end{itemize} \printindex{} \end{document}