From 5884ca78ecba6074ed828a83fb39fc8a3d9b317f Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 29 Oct 2016 13:13:39 +0200
Subject: Moving 2-SAT to graph section.

---
 graph/graph.tex | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'graph')

diff --git a/graph/graph.tex b/graph/graph.tex
index 6b29b3c..f62d6a7 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -99,6 +99,14 @@ Gut bei sehr dicht besetzten Graphen.
 \subsection{Maximal Cardinatlity Bipartite Matching}\label{kuhn}
 \lstinputlisting{graph/maxCarBiMatch.cpp}
 
+\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}
+
 % \subsection{TSP}
 % \lstinputlisting{graph/TSP.cpp}
 
-- 
cgit v1.2.3