blob: 09ea14c3d46c43a573f6d98e7682a6d0361ccb47 (
plain)
1
2
3
4
5
6
7
8
9
|
\section{Sonstiges}
\subsection{2-SAT}
\begin{enumerate}
\item Bedingungen in 2-CNF formulieren.
\item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$.
\item Finde die starken Zusammenhangskomponenten.
\item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt.
\end{enumerate}
|
