\documentclass[11pt]{article}
\usepackage{A4,amsmath,amssymb,german}
\pagestyle{empty}
\parindent0em
\begin{document}
Prof. Dr. Volker Strehl \hfill 22.7.1999
\\
IMMD-8
\begin{center}
\Large
\"Ubungen zur\\
Einf\"uhrung in die Theoretische Informatik III\\
SS 1999
\end{center}

Zur Terminologie: 
Ist $G =(V,E)$ ein ungerichteter Graph, d.h.
$E \subseteq \binom{V}{2}$ = Menge der zweielementigen
Teilmengen von $V$, und ist $v \in V$ ein Knoten 
von $G$, so bezeichne 
$\Delta(v) = \Delta_G(v)$ die Menge der \textit{Nachbarn} von $v$ in $G$,
d.h. $\Delta_G(v) = \{u \in V; \{u,v\} \in E \}$,
sowie $\delta(v) = \delta_G(v) = \sharp \Delta_G(v)$ 
den \textit{Grad} von $v$ in $G$, also die Anzahl der Nachbarn.

\begin{itemize}

\item[27.]

\begin{enumerate}
\item
F\"ur $i=0,1,2$ seien ``Graphen vom Typ $i$'' definiert
als Graphen $G$ mit \\
$\max_{v \in V} \delta_G(v) = i$. 
Beschreiben Sie anschaulich die Graphen $G$ dieser drei Typen.
\item
Zeigen Sie, dass ein (ungerichteter) Graph genau dann
einen Eulerschen Kreis besitzt, wenn er zusammenh\"angend ist und
jeder Knoten einen \textit{geraden} Grad hat.
\item
Zeigen Sie, dass ein (ungerichteter) Graph $G$ genau dann 2-f\"arbbar ist,
wenn jeder Kreis (geschlossene Pfad) in $G$ \textit{gerade}
L\"ange hat. Formulieren Sie einen effizienten Algorithmus zum
Testen der 2-F\"arbbarkeit von Graphen.
\item
Zeigen Sie, dass das Problem 2-(CNF)-SAT der Erf\"ullbarkeit von
Klauselmengen, bei denen jede Klausel aus h\"ochstens zwei Literalen
besteht, effizient entscheidbar ist.\\
Hinweis: Ist $X$ die Menge der in den Klauseln vorkommenden Variablen, so untersuchen Sie den (gerichteten) Graphen, dessen Knotenmenge
aus allen Literalen $x$ und $\overline{x}$ ($x \in X$) besteht und wo
jeder Klausel $\{\overline{\alpha},\beta\}$ eine Kante
$\alpha \rightarrow \beta$ und eine Kante 
$\overline{\beta} \rightarrow \overline{\alpha}$ zugeordnet wird.
Beachte $\overline{\overline{\alpha}}=\alpha$.
Wie formuliert sich die (Un-)Erf\"ullbarkeit als Eigenschaft
dieses Graphen?

\end{enumerate}



\item[28.]
Ist $G = (V,E)$ ein ungerichteter Graph, so bezeichnet man jede
Teilmenge $C \subseteq V$ mit $\binom{C}{2} \subseteq E$ als
\textit{Clique} von $G$, sowie jede Teilmenge 
$C \subseteq V$ mit $\binom{C}{2} \cap E = \emptyset$ als
\textit{Co-Clique} von $G$. (Der \"Ubergang vom Graphen $G$
zum komplement\"aren Graphen $\overline{G} = (V, \binom{V}{2} \setminus E)$
transformiert Cliquen in Co-Cliquen und umgekehrt --- 
in diesem Sinne sind diese
Begriffe als gleichwertig).\\
Die \textit{Cocliquenzahl} $\alpha(G)$ eines Graphen $G$ ist die maximale
Gr\"osse einer Co-Clique von $G$. Das Problem der Berechnung von $\alpha(G)$
ist offenbar (mindestens) so schwierig wie das NP-vollst\"andige
Entscheidungsproblen \textsc{Coclique}. 

\begin{enumerate}
\item
Wie berechnet man (effizient!) $\alpha(G)$ f\"ur Graphen der
Typen $0,1,2$ (siehe oben)?
\item
Ein \textit{divide-and-conquer}-Ansatz zur Berechnung von $\alpha(G)$
sieht so aus: Ist $G = (V,E)$ ein (ungerichteter) Graph und $v \in V$
ein Knoten von $G$, so bezeichne:\\
--- $G_v^{1}$ den Graphen, der entsteht, wenn man aus $G$
den Knoten $v$ und die zugeh\"origen Kanten entfernt (aber nicht die
anderen Endpunkte, also die Nachbarn von $v$ in $G$), d.h.
\[
G_v^1 = \left( V \setminus \{v\}, E \cap \binom{V \setminus \{v\}}{2}
\right)
\]
--- $G_v^{2}$ den Graphen, der entsteht, wenn man aus $G$
den Knoten $v$, dessen Nachbarn $\Delta_G(v)$
und die zugeh\"origen Kanten entfernt, d.h. 
\[
G_v^1 = \left( 
V \setminus N, 
E \cap \binom{V \setminus N}{2}
\right)
\]
mit $N = \Delta_G(v) \cup\{v\}$.\\
Zeigen Sie:
\[
\forall v \in V\;:\;
\alpha(G) = \max \left( \alpha(G_v^1),1 + \alpha(G_v^2) \right)
\]
\item
Formulieren Sie einen \textit{divide-and-conquer}-Algorithmus
zur Berechnung von $\alpha(G)$.\\
Hinweis: Sie m\"ussen sich festlegen, bei welchen ``einfachen'' Graphen
die obige Zerlegung nicht mehr weitergef\"uhrt werden soll. 
Daf\"ur bieten sich die Graphen der Typen $0,1,2$ an.
\item
Untersuchen Sie die \textit{worst-case}-Komplexit\"at Ihres Verfahrens!\\
Eine rekursive Absch\"atzung f\"ur die Zeit-Komplexit\"at
$t(n)$ (f\"ur Graphen mit $n$ Knoten) sollte folgende Gestalt haben
\[
t(n) \leq t(n-1) + t(n-2-i) + c n^2~~(i \in \{0,1,2\})
\]
wobei der Parameter $i$ angibt, bei welchem Typ von
``einfachen'' Graphen man das divide-and-conquer stopt. \\
Zeigen Sie, dass sich L\"osungen dieser Rekursion exponentiell verhalten,
also von der Form $\mathcal{O}(\beta_i^n)$ sind, wobei
$\beta_0 = 1.61 \ldots$,
$\beta_1 = 1.46 \ldots$,
$\beta_2 = 1.38 \ldots$ ist.

\end{enumerate}

\item[29.]
Zum Problen \textsc{Satisfiability}
\begin{enumerate}
\item
Es seien $x_1,x_2,\ldots,x_k,z_1,z_2,\ldots,z_{k-3}$
Boolesche Variable. Betrachten Sie die folgenden Disjunktionen (Klauseln)
\begin{align*}
c   &\equiv x_1 \vee x_2 \vee \ldots \vee x_k \\
c_1 &\equiv x_1 \vee x_2 \vee z_1 \\
c_j &\equiv x_{j+1} \vee \overline{z_{j-1}} \vee z_j ~~(2 \leq j \leq k-3) \\
c_{k-2} &\equiv x_{k-1} \vee \overline{z_{k-3}} \vee x_k
\end{align*}
und zeigen Sie:
\begin{itemize}
\item[--]
jede Boolesche Bewertung von $x_1, \ldots,x_k$, welche die Klausel
$c$ erf\"ullt, kann zu eine Booleschen Bewertung von
$x_1, \ldots,x_k, z_1,\ldots z_{k-3}$ erweitert werden, die alle
Klauseln $c_1, \ldots, c_{k-2}$ erf\"ullt.
\item[--]
die Bewertung $x_i = \mathtt{false} ~(1 \leq i \leq k)$, welche die
Klausel $c$ nicht erf\"ullt, kann auf keine Weise zu einer Bewertung
von $x_1, \ldots,x_k, z_1,\ldots z_{k-3}$ erweitert werden,
die alle Klauseln $c_1, \ldots,c_{k-2}$ erf\"ullt.
\end{itemize}

\item
\"Uberlegen Sie sich, wie man zu jedem Booleschen Schaltkreis
(oder straight-line Programm) mit input-Variablen $x_1,\ldots,x_n$
eine Klauselmenge (mit Literalen zu den Variablen $x_1,\ldots,x_n$
und zus\"atzlichen Variablen f\"ur jeden input- bzw. output-Knoten und
jedes Gatter) mit maximal drei Literalen pro Klausel konstruieren kann,
so dass Instanzen von \textsc{Circuit Value} in Instanzen von
\textsc{Satisfiabiltiy} transformiert werden. Stellen Sie sicher, dass
Ihre Konstruktion mit logarithmischem Platz auskommt.
\end{enumerate}
\end{itemize}

\end{document}