notes/school/di-ma/uebung/08/08_4.tex

\documentclass[12pt,a4paper,german]{article}
\usepackage{url}
%\usepackage{graphics}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{ngerman}
\usepackage{float}
\usepackage{diagbox}
\usepackage[utf8]{inputenc}
\usepackage{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{cancel}
\usepackage{wasysym}
\usepackage{csquotes}
\usepackage{stmaryrd}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{paralist}
\usepackage{tikz}
\geometry{left=2.0cm,textwidth=17cm,top=3.5cm,textheight=23cm}

%%%%%%%%%% Fill out the the definitions %%%%%%%%%
\def \name {Valentin Brandl}					%
\def \matrikel {108018274494}				%
\def \pname {Marvin Herrmann}				%
\def \pmatrikel {108018265436}				%
\def \gruppe {2 (Mi 10-12 Andre)}
\def \qname {Pascal Brackmann}
\def \qmatrikel {108017113834}				%
\def \uebung {8}								%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 % DO NOT MODIFY THIS HEADER
\newcommand{\hwsol}{
\vspace*{-2cm}
\noindent \matrikel \quad \name \hfill \"Ubungsgruppe: \gruppe \\
\noindent \pmatrikel \quad \pname \\
\noindent \qmatrikel \quad \qname \\
\begin{center}{\Large \bf L\"osung f\"ur \"Ubung \# \uebung}\end{center}
}

\begin{document}
%Import header
\hwsol

\section*{Aufgabe 8.4}

Abhängig, d.h. $v$ vor $u \Rightarrow O_v > O_u$ und $I_v < I_u$
\\
Unabhängig, d.h. $\begin{cases}
    \includegraphics[scale=0.3]{build/school/di-ma/uebung/08/08_4_1.png} \\
    \includegraphics[scale=0.3]{build/school/di-ma/uebung/08/08_4_3.png}
\end{cases}$
\\
\\
Beweis durch Widerspruch: $\mathbb{A}: v,u \in V$, $v$ und $u$ sind unabhängig

\begin{enumerate}[1.]

    \item Fall: $I_v < I_u$ aber $O_v > O_u$.

        Da Einstiegspunkt von $v$ kleiner ist als $u$, wurde $v$ vor $u$ durchlaufen. Weil $v$ und $u$ unabhängig, gibt
        es ein $x \in V$, das die beiden Äste vereint. Für diesen muss dann nach Definition der Tiefensuche gelten, dass
        er vor $v$ und $u$ gefunden wurde ($I_x < I_v$ und $I_x < I_u$). Weiterhin gilt, dass $v$ vor $x$ vom Stack
        gepopt wird, genauso wie $u$. Also $O_v < O_x$ und $O_u < O_x$

        Insgesamt folgt somit nach Annahme

        \begin{itemize}
            \item $v$ vor $u$ durchlaufen
            \item $x$ vor $v$ und $u$ durchlaufen
            \item $v$ vor $x$ vom Stack gepopt
            \item $u$ vor $x$ vom Stack gepopt
            \item $u$ vor $v$ vom Stack gepopt
        \end{itemize}

        Somit bleibt nur die folgende Darstellung übrig, welche ein Widerspruch zur Unabhängigkeit ist.

        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.3]{build/school/di-ma/uebung/08/08_4_2.png}
        \end{figure}

    \item Fall: $I_v > I_u$ und $O_v < O_u$

        $u$ wurde vor $v$ durchlaufen, aber $v$ wurde vor $u$ vom Stack gepopt.

        Dies ist genau dann der Fall, wenn ein $v$ Nachfolger von $u$ ist (es liegt im Graphen tiefer). Das heißt, dass
        $v$ und $u$ im gleichen Ast sind.

        $\lightning$ zu Unabhängigkeit.

\end{enumerate}

\noindent
$\mathbb{A}: v,u \in V$ und $v$ und $u$ sind abhängig

\begin{enumerate}[1.]

    \item Fall: $I_v < I_u$ und $O_v < O_u$

        Da $v$ vor $u$ durchlaufen wurde und sie abhängig sind, müsste $u$ vor $v$ vom Stack genommen werden, nach
        Definition der Tiefensuche, welches somit im Widerspruch zu $O_v < O_u$ steht.

    \item Fall: $I_v > I_u$ und $O_v > O_u$

        Dann wurde $u$ vor $v$ durchlaufen, allerdings wurde $u$ vor $v$ vom Stack gelöscht. Nach Definition der
        Tiefensuche werden aber Knoten die in einem Ast liegen von unten nach oben vom Stack gepopt. Somit Widerspruch
        zur Abhängigkeit

\end{enumerate}

\end{document}