32 lines
1.3 KiB
TeX
32 lines
1.3 KiB
TeX
\newcommand{\indeg}{\mathrm{indeg}}
|
|
\newcommand{\outdeg}{\mathrm{outdeg}}
|
|
|
|
\section{Wurzelspannbäume und ungerichtete Bäume}
|
|
\begin{quote}
|
|
Sei $G = \tup{V, E}$ ein gerichteter Graph und $s$ ein ausgezeichneter Knoten. Zeigen Sie:
|
|
|
|
Der gerichtete Graph $G$ ist ein $s$-Wurzelspannbaum $\iff$ Der $G$ zugrunde
|
|
liegende ungerichtete Graph $G'$ ist ein Baum, für jedes
|
|
$v \in V \setminus \set{s} : \indeg(v) = 1$ und $\indeg(s) = 0$.
|
|
\end{quote}
|
|
|
|
\begin{itemize}
|
|
\item[$\Rightarrow$]
|
|
Wenn der Graph $G$ ein $s$-Wurzelspannbaum ist, dann erfüllt er die
|
|
Eigenschaften eines $s$-Wurzelbaums, also $G$ azyklisch, $v \in V \setminus \set{s} : \indeg(v) = 1$ und $\indeg(s) = 0$. Der zugrunde liegende
|
|
ungerichtete Graph $G'$ muss also auch azyklisch, also ein Baum, sein.
|
|
\item[$\Leftarrow$]
|
|
Fall 1: $G'$ ist kein Baum.
|
|
|
|
Dann existiert in $G$ entweder ein gerichteter Kreis, was die erste $s$-\-Wurzel\-baum-\-Eigenschaft verletzt, oder ein Knoten $u$
|
|
hat $indeg(u) > 1$.
|
|
|
|
Fall 2: Es existiert ein Knoten $v \in V \setminus \set{s}$ mit $\indeg(v) > 1$.
|
|
|
|
Das verletzt die zweite $s$-Wurzelbaum-Eigenschaft. Also kann $G$ kein $s$-\-Wurzel\-spann\-baum sein.
|
|
|
|
Fall 3: Der Knoten $s$ hat $\indeg(s) > 0$.
|
|
|
|
Das verletzt die dritte $s$-Wurzelbaum-Eigenschaft. Also kann $G$ kein $s$-\-Wurzel\-spann\-baum sein.
|
|
\points{4}
|
|
\end{itemize}
|