%
\begin{bibunit}[my-siam]
%
\Vorlesungskopf{Stefan Felsner}                           % your name
           {15.11.2013}                                   % lecture date
           {33}                                            % lecture number
           {Elektrische Netze und aufspannende Bäume}     % lecture title
%%           {Elektrische Netze \&\\[6pt] aufspannende Bäume}     % lecture title

In der 6. Vorlesung haben wir das Spiel {\tt Bridg-It} kennengelernt
und gesehen, dass aufspannende Bäume hier bei der Beschreibung einer
Gewinnstrategie hilfreich sind. Das zweite Thema der Vorlesung
war der Satz von
Cayley über die Anzahl der aufspannenden Bäume vollständiger Graphen.
F\"ur diesen Satz haben wir drei sehr unterschiedliche Beweise besprochen.
In diesem Kapitel\footnote{Zu diesem Kapitel gab es im WS13/14 keine
  Vorlesung. Das Kapitel ist zu Beginn des Projekts als Beispiel und Anregung  f\"ur die
  Ausarbeitungen der Studenten entstanden.}
wird es um eine weitere Anwendung aufspannender Bäume gehen. Wir beginnen
mit elektrischen Netzen und Graphen, die aufspannenden Bäume kommen
später überraschend ins Spiel. 

\section{Elektrische Netze}

Ein \term{elektrisches Netz} ist ein Graph (gegebenenfalls auch ein Multigraph)
in dem jeder Kante $e_i$ ein \term{Widerstand} (resistance) $r_i$ 
zugeordnet ist. Um den Stromfluß im Netz zu beschreiben sprechen wir
über \term{Stromstärken} und \term{Potentialdifferenzen} (Spannungen). 

Sei $e_i=(u,v)$, $p_i$ die Potentialdifferenz 
und $w_i$ die Stärke des Stroms von $u$ nach $v$, dann gilt
\vbox{}\vskip-15mm\vbox{}

\begin{align}
r_i\cdot w_i &= p_i\tag{Ohmsches Gesetz}
\end{align}

Für das Weitere ist es nützlich orientierte Kanten 
also Kanten mit Start- und Zielknoten zu betrachten.
Oben haben wir für $e_i$ eine Orientierung
durch die Notation $e_i=(u,v)$ schon unter der Hand als $u\to v$ 
vorgegeben. 

Ströme und Spannungen sind antisymmetrisch, d.h.
$$
w_{uv} = -w_{vu} \quad\text{und}\quad 
p_{uv} = -p_{vu}.
$$
Ströme und Spannungen in elektrischen Netzen genügen den
Kirchhoffschen%
\footnote{Übung: Wikipedia[Gustav Robert Kirchhoff]
lesen und sein Grab in Schöneberg besuchen.}%
\hbox{\hskip3pt}Gesetzen:

\Item(KG~I) Für einen Knoten $x$ mit Nachbarn
$v_1,v_2,\ldots,v_d$ und Quellstärke $q_x$ gilt:\\
$w_{x,v_1} +  w_{x,v_2} +\ldots+ w_{x,v_d} = q_x$.

\Item(KG~II) Für jeden Kreis $u_1,u_2,\ldots,u_k$ gilt:\\
$p_{u_1,u_2}+p_{u_2,u_3}+\ldots+p_{u_{k-1},u_k}+p_{u_k,u_1} = 0$.
\medbreak

Das Potenzialgesetz KG~II erlaubt es den Knoten absolute Potentiale
zuzuordnen, so dass $p_{u,v}$ die Differenz der
Potentiale von $v$ und $u$ ist.
Das beweisen wir in einem Lemma.

\begin{lemma}
  Sei $G$ zusammenhängend und $p$ eine antisymmetrische Abbildung von $E$ nach
  $\RR$ die KG~II erfüllt. Zu einem ausgewählten Knoten $v_0\in V$ gibt es dann
  eine eindeutige Abbildung $\mu: (V-v_0) \to \RR$ mit $\mu(v_0) = 0$ und
  $p_{u,v} = \mu(u)-\mu(v)$ für alle $uv\in E$.
\end{lemma}

\Beweis Um $\mu(v)$ festzulegen wähle einen Weg (hier benötigen wir den
Zusammenhang) $v_0,v_1,v_2,\ldots,v_{a-1},v_a=v$ und bestimme $\mu(v) =
\mu(v_0) + p_{v_0v_1}+p_{v_1v_2}+\ldots+p_{v_{a-1}v_a}$.  Zu zeigen ist nun,
dass das wohldefiniert ist, also nicht von der Wahl des Weges abhängt. Zwei
Wege $v_0,v_1,\ldots,v_a=v$ und $v_0,u_1,\ldots,u_b=v$ können zu einem
geschlossenen Kantenzug $v_0,u_1,\ldots,u_b,v_a,\ldots,v_1,v_0$ verknüpft
werden. Aus KG~II folgt (da kann durchaus ein Argument ausgearbeitet werden),
dass $p_{v_0v_1}+p_{v_1v_2}+\ldots+p_{v_{a-1}v_a}+
p_{u_bu_{b-1}}+\ldots+p_{u_1v_0} = 0$ gilt. Daraus folgt, dass die Wahl des
Weges irrelevant ist.\qed

Wir betrachten ein Beispiel.  In der Abbildung~\ref{fig:stromnetz}
sind links die Widerstände $r_e$ an den Kanten festgelegt.  In der
Mitte sind die Flüsse mit den Quellstärken $q_s = 1$, $q_t= -1$ und $q_i= 0$ sonst, wobei die nicht verschwindenden Quellstärken
durch Halbkanten dargestellt werden. Die Flüsse $\neq e,f$ können dank
der Flusserhaltung (KG~I) eliminiert werden (durch $e$, $f$ und $1$
ausgedrückt werden).  Rechts schliesslich sind die Potentiale mit der
Ohmschen Gleichung $r_{uv}w_{uv} = \mu(u) -\mu(v)$ und der Normierung
$\mu(t)=0$ entlang der fetten Kanten berechnet worden. Das Ohmsche
Gesetz für die beiden übrigen Kanten liefert $3f= e-2(1-e)$ und
$4(1-e-f) = (6e+5f) - 2(1-e)$.  Diese zwei Gleichungen in zwei
Variablen haben die Lösung $e=4/7$ und $f = -2/21$. Die
Potentialdifferenz die man benötigt um den Flusswert 1 zu erhalten ist
der \term{effektive Wiederstand}. In unserem Fall ist $6e+5f = 62/21$
der effektive Wiederstand zwischen $s$ und $t$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\PdfFigCap{24}{stromnetz}{Ein Stromnetz mit Widerständen, Flüssen und
  Potentialen (von links nach rechts).}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Eine heuristische Nebenüberlegung: Sei $(V,E)$ ein zusammenhängendes Netz mit
$m$ Kanten, $n$ Knoten und Wiederständen $r:E \to \RR_+$.  Wir setzen $m$
Variablen $w_e$ für die Flusswerte an. Die Flusserhaltung (KG~I) liefert
$n-1$ linear unabhängige Bedingungen (Dimension des Schnittraumes).
Diese verwenden wir zur Elimination, es bleiben $m-n+1$ Variablen.
Benutze einen aufspannenden Baum um ausgehend von $\mu(v_0)=0$ ausgehend
die Potenziale zu bestimmen. Jede Kante, die nicht im Baum ist, schlie\ss t mit den
Baumkanten einen Kreis, in dem das Potenzialgesetz (KG~II) gelten muss (das
entspricht der Ohmschen Gleichung $r_{uv}w_{uv} = \mu(u) -\mu(v)$ für die
Nichtbaumkante $uv$!). Insgesamt liefert das $m-n+1$ Gleichungen.
Das lineare Gleichungssystem ist also quadratisch, wenn es nicht-degeneriert
ist bekommen wir eine eindeutige Lösung. Die Physik sagt, dass die Lösung
tatsächlich eindeutig ist. Im folgenden Satz werden wir das
für den Fall in dem alle Wiederstände $r_e=1$ sind bewiesen.

Sei $N=(V,E)$ ein zusammenhängendes Netz mit ausgezeichneten Knoten
$s$ und $t$. Für eine Kante $(u,v)$ sei $T(u,v)$ die Anzahl der
aufspannenden Bäume $S$ von $N$, in denen der Pfad von $s$ nach $t$ die
Kante $u,v$ enthält, anders gesagt $S$ enthält $(u,v)$ und in $S - (u,v)$
sind $s$ mit $u$ sowie $v$ mit $t$ in gemeinsamen Komponenten. 

\begin{satz}[Kirchhoff]\label{satz:KH}
Sei $N=(V,E)$ ein zusammenhängendes Netz mit ausgezeichneten Knoten
$s$ und $t$ und Wiederständen $r_e=1$ für alle $e$.
Die Werte $w_{(u,v)} := T(u,v) - T(v,u)$ definieren einen elektrischen Fluss
von $s$ nach $t$ in $N$ mit Flussstärke 
$q_s= -q_t = \#$({\it aufspannender Bäume von} $N$).
\end{satz}

\Beweis
Wir müssen die beiden Gesetze KG~II und KG~I nachweisen.
Für KG~I ist das ganz einfach: Jeder aufspannende Baum $S$
trägt eine Einheit Fluss entlang des eindeutigen $s\to t$
Pfades in $S$ bei, der Gesamtfluss ergibt sich als Summe
der einzelnen Pfadflüsse. Flusserhaltung gilt für jeden Pfad
und auch für die Summe der Pfade, also den Gesamtfluss.

Um KG~II nachzuweisen müssen wir ein bisschen mehr tun.
Zuerst beobachten wir, dass wegen $w_e = p_e/r_e$ und
$r_e=1$ aus dem Potenzialgesetz ein Kreisflussgesetz
wird. Das heißt, es genügt nachzurechnen, dass für
jeden Kreis $u_1,u_2,\ldots,u_k$ in $N$ gilt:
$w_{u_1,u_2}+w_{u_2,u_3}+\ldots+w_{u_{k-1},u_k}+w_{u_k,u_1} = 0$.

Wir nennen einen aufspannenden Wald mit zwei Komponenten
$F_s,F_t$ mit $s\in F_s$ und $t\in F_t$ ein \term{Dickicht}.

\Beobachtung
$$
T_{(u,v)} = \#(\textit{ Dickichte mit $u\in F_s$ und $v\in F_t$})
$$

\Beobachtung
Ein Dickicht, $(F_s,F_t)$ kann mit jeder Kante $(u,v)$ mit 
$u\in F_s$ und $t\in F_t$ zu einem Baum erweitert werden.
Die Kante $(u,v)$ liegt dann natürlich auf dem $s\to t$ Pfad
des Baumes.

Wenn wir nun einen  Kreis 
$u_1,u_2,\ldots,u_k$ und ein Dickicht $(F_s,F_t)$ betrachten,
dann gilt:
\begin{align}
\tag{i}\label{ali:i}
\#(i \;:\; u_i\in F_s\text{ und }u_{i+1}\in F_t)
- \#(i \;:\; u_i
\in F_t\text{ und }u_{i+1}\in F_s) =& 0
\end{align}
\noindent
Dies gilt, weil sich Indizes $i$, die einen positiven Beitrag
leisten, und Indizes, die einen negativen Beitrag leisten, abwechseln.

Um unser ``double counting'' Argument griffig kodieren zu können hier
noch ein bisschen Notation: Für einen Baum $S$ sei 
$w_{u,v}^S$ der Beitrag von $S$ zu $w_{u,v}$, d.h. abhängig von der 
Orientierung von $(u,v)$ auf dem $s \to t$ Pfad in $S$ kann $w_{u,v}$
die Werte $+1$, $-1$, $0$ annehmen. Für ein Dickicht $F$ sei $w_{u,v}^F:=
w_{u,v}^{F + (u,v)}$, das ist $0$ wenn  $F + (u,v)$ kein Baum ist und
sonst über den Baum $F + (u,v)$ definiert. 

Sei also $u_1,u_2,\ldots,u_k$ ein Kreis in $N$. Mit der soeben
eingeführten Notation ist
\ref{ali:i} dasselbe wie $\sum_i w^F_{u_i,u_{i+1}} = 0$, für jedes Dickicht
$F$. Daher gilt:
$w_{u_1,u_2}+w_{u_2,u_3}+\ldots+w_{u_{k-1},u_k}+w_{u_k,u_1} = 
\sum_i w_{u_i,u_{i+1}} = \sum_i \sum_T w^T_{u_i,u_{i+1}} =
\sum_i \sum_F w^F_{u_i,u_{i+1}} =  \sum_F \sum_i w^F_{u_i,u_{i+1}} 
= \sum_F 0 = 0$.
Damit ist der Satz bewiesen.
\qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Squaring the Square}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\glqq Squaring the Square\grqq\ ist der Titel einer Kolumne von
Martin Gardner in der er Ergebnisse der Arbeit~\cite{bsst-drs40} von
Brooks, Smith und Tutte \glqq The Dissection of Rectangles into Squares\grqq\
zusammenfasst.

Eine \glqq{\it Dissection of Rectangles into Rectangles}\grqq\ (wir werden
es \term{Rechteckszerlegung} nennen) ist eine Partition eines Basisrechtecks
in Teilrechtecke wie in Abb.~\ref{fig:squared-rd}, links. In~\cite{bsst-drs40}
fragen sich die Autoren unter welchen Umständen eine solche Zerlegung in Rechtecke
zu einer äquivalenten Zerlegung in Quadrate (\term{Quadratzerlegung}) gehört.
Eine zu der in Abb.~\ref{fig:squared-rd} links dargestellten
Rechteckszerlegung äquivalente Quadratzerlegung ist in derselben
Abbildung rechts dargestellt. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{squared-rd}
\caption{\label{fig:squared-rd}Eine Rechteckszerlegung 
mit einer äquivalenten Quadratzerlegung.}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Aus dem Vergleich der beiden Zerlegungen 
erschliesst sich der hier verwendete Begriff der Äquivalenz, den wir
zunächst formal definieren wollen. 

Zwei \term{Rechteckszerlegungen sind äquivalent}, wenn es eine Bijektion
zwischen den Segmenten gibt, die die {\it Orientierung} (horizontal, vertikal)
und die {\it endet auf} Relation erhält sowie die Rahmensegmente links,
rechts, oben und unten auf die entsprechenden Rahmensegmente abbildet.  Eine
alternative Definition der Äquivalenz bekommen wir indem wir mit der
Rechteckszerlegung ihren \term{H-Graphen} betrachten. Die Knoten des H-Graphen
sind die horizontalen Segmente der Zerlegung. Die Kanten des H-Graphen
entsprechen den Rechtecken der Zerlegung, sie verbinden jeweils das untere mit
dem oberen Segment. Zusätzlich gibt es eine Kante, die das untere 
Rahmensegment $s$ mit dem oberen Rahmensegment $t$ verbindet. 
Abbildung~\ref{fig:s-graph-1} illustriert die Konstruktion des
H-Graphen.
%
\Tatsache A. Der H-Graph einer Rechteckszerlegung hat eine natürliche 
planare (kreuzungsfreie) Einbettung.
%
\Tatsache B. Zwei Rechteckszerlegungen sind äquivalent $\iff$ ihre H-Graphen
sind als planar eingebettete Graphen mit $s$ und $t$ identisch.

\goodbreak

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\PdfFigCap{19}{s-graph-1}{Der H-Graph der Rechteckszerlegung
aus Abb.~\ref{fig:squared-rd}.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Wir nehmen an, dass Kanten des H-Graphen  Widerstand  1 haben und
nennen den Graphen, den wir durch Löschen der Kante $(s,t)$ im
H-Graphen erhalten den H$'$-Graphen. Einen elektrischen Fluss im
H$'$-Graphen bekommen wir mit $w_{(u,v)} := T(u,v) - T(v,u)$ 
(vergl.\ den Beweis von Satz~\ref{satz:KH}). Wir erinnern uns,
dass es einfach war die Flusserhaltung (KG~I) für 
diese $w_{(u,v)}$ nachzuweisen. Wir werden im Folgenden zeigen, dass
das Potentialgesetz (KG~II) in unserem Fall genauso leicht
hergeleitet werden kann.  

Zunächst definieren wir den V-Graphen zur Rechteckszerlegung
ganz analog zum H-Graphen, nur dass wir diesmal die vertikalen
Segmente zu Knoten des Graphen machen. Die Konstruktion
ist in Abb.~\ref{fig:s-graph-2} dargestellt.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\PdfFigCap{19}{s-graph-2}{Der H-Graph und der V-graph der Rechteckszerlegung.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Wir beobachten, dass der H-Graph und der V-Graph dual\footnote{Die Dualität planarer
  Graphen werden wir später noch genauer kennenlernen} zueinander sind,
d.h. wir haben Bijektionen: H-Knoten $\leftrightarrow$ V-Flächen, H-Flächen
$\leftrightarrow$ V-Knoten und H-Kanten $\leftrightarrow$ V-Kanten. 
Diese Bijektionen $\sigma$ haben die Eigenschaft, dass wenn 
$(u,v)$ eine H-Kante ist und $f$, $g$ die angrenzenden Flächen, dann ist
$\sigma((u,v)) = (\sigma(f),\sigma(g))$ die zugehörige V-Kante mit
angrenzenden Flächen $\sigma(u)$, $\sigma(v)$. (Für die duale Kante
zu $(u,v)$ schreibt man statt $\sigma((u,v))$ meistens $(u,v)^*$). 

Ohne Beweis werden wir die folgende Dualität aufspannender Bäume verwenden:
\Bitem Ist $S \subset E_H$ ein aufspannender Baum im H-Graphen, dann ist
$S^\star = E_V\setminus S^*$ ein aufspannender Baum von $V$.
\medskip

Wir definieren
\begin{align}
\notag
T_{(u,v)} &= \#(\textit{Bäume von $H'$ mit Pfad $s\to u,v\to t$})\\
\notag
T^*_{(f,g)} &= \#(\textit{Bäume von $V'$ mit Pfad $s'\to f,g\to t'$})
\end{align}

\begin{lemma}
Wenn $f$ und $g$ die Flächen links und rechts der Kante $u\to v$ 
im H-Graphen sind,
dann gilt  $T^*_{(f,g)} = T_{(u,v)}$.
\end{lemma}
 
\Beweis Sei $S$ ein aufspannender Baum des H$'$-Graphen mit einem Pfad $s\to
u,v\to t$. Wir fassen $S$ als aufspannenden Baum des H-Graphen auf und
betrachten den dualen Baum $S^\star$, dieser enthält die Kante $(s',t')$. Wir
definieren $\hat{S}=S^\star - (s',t') + (f,g)$, dies ist ein Baum des
V$'$-Graphen mit einem Pfad $s'\to f,g\to t'$.  Beispiele für die Abbildung $S
\leftrightarrow \hat{S}$ zusammengestellt.  Das Lemma wird bewiesen indem man
zeigt, dass die Abbildung eine Bijektion ist.
\qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\PdfFigCap{19}{duale-paare}{Drei Beispiele für die Abbildung $S
\leftrightarrow \hat{S}$ bezüglich des Kantenpaars das sich im unterlegten Kreis schneidet.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Die Flusserhaltung für den dualen Fluss $w^*_{(f,g)} = T^*(f,g) - T^*(g,f)$
liefert mit $w^*_{(f,g)} = w_{(u,v)}$, wenn wie im Lemma $(f,g) = (u,v)^*$,
das Kreisflussgesetz (KG~II) für $w$ und Flächenkreise. Das Kreisflussgesetz kann als
$w^T\cdot k = 0$ für $k\in Z$ geschrieben werden. Da die Flächenkreise eine
Basis des Zyklenraumes $Z$ sind erhält man das Kreisflussgesetz für $w$ auf
beliebigen Kreisen durch lineare Fortsetzung.

Repräsentiert man den Fluss $w_e$ in einer Kante des H-Graphen durch die 
Breite des zugehörigen Rechtecks und den dualen Fluss $w^*_{e^*}$ durch
die Höhe des Rechtecks, dann erhält man das Resultat von  
Brooks, Smith, Stone und Tutte:
\begin{satz}
Zu jeder Rechteckszerlegung gibt es eine äquivalente Quadratzerlegung. 
\end{satz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Literatur und Hintergrund}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Das Interesse der Autoren von~\cite{bsst-drs40} galt in erster Linie
Quadratzerlegungen, in denen die Rahmensegmente ein Quadrat bilden und
die Quadrate paarweise verschiedene Seitenlängen haben, solche
Quadratzerlegungen werden \term{perfekt} genannt, 
Abb.~\ref{fig:perfect-square} zeigt ein Beispiel.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{wrapfigure}[16]{r}{0.44\textwidth}%
\centering
\includegraphics[width=0.4\textwidth]{squaring112x112}
\caption{\label{fig:perfect-square}Die kleinste perfekte Quadratzerlegung.}
\end{wrapfigure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
Das zweite Kapitel von Bollobas~\cite{B02} heißt ``{\it Electrical
  Networks}\/'', dort findet man mehr zum Thema.  Verschiedenste Aspekt
der Beziehung zwischen Graphen und Rechteckszerlegungen werden in
meinem Übersichts\-artikel~\cite{f-rsrpg-13} besprochen.

Von elektrischen Netzen und effektivem Widerstand gibt es auch
wichtige Verbindungen zu Markov Ketten und Random Walks
(Zufallsspaziergängen): Wenn eine Einheit Strom von $s$ nach $t$ durch
ein Netz $N$ fliesst, dann ist der Fluss in einer Kante $(u,v)$
proportional zur erwarteten Anzahl von Passagen Zufallsspaziergänger
durch $(u,v)$ (Passagen $v\to u$ werden negativ gezählt) der das Netz
in $s$ betritt und beim ersten Besuch von $t$ verlässt. Der
Proportionalitätsfaktor ist gerade der effektivem Widerstand.
Mehr dazu findet man bei Doyle und Snell~\cite{ds-rwen06}
und auch bei Motwani und Raghavan~\cite{mr-ra95}.

Nicht direkt mit elektrischen Flüssen im Zusammenhang steht der
folgende Satz von Dehn. 
\begin{satz}
Wenn jedes Rechteck einer Rechteckszerlegung zumindest eine
ganzzahlige Seitenlänge hat, dann hat auch das
umschließende Rechteck mindestens eine ganzzahlige Seitenlänge.
\end{satz}
Ich erwähne den Satz hier, weil es zahlreiche schöne, mehr oder weniger
kombinatorische Beweise für ihn gibt, vergl.~\cite[Kap.~26]{AZ10}
und die dort angegebenen Literaturhinweise.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{center}
%\includegraphics[width=0.5\textwidth]{nerd_sniping.png}
%\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begingroup
\small
\putbib[skriptbib]
\end{bibunit}
\endgroup
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\endinput

