diff options
| author | Paul Jungeblut <paul.jungeblut@gmail.com> | 2016-10-29 13:13:39 +0200 |
|---|---|---|
| committer | Paul Jungeblut <paul.jungeblut@gmail.com> | 2016-10-29 13:13:39 +0200 |
| commit | 5884ca78ecba6074ed828a83fb39fc8a3d9b317f (patch) | |
| tree | ea0e574525de475e6463d77e5641cd66ccdaed60 | |
| parent | 5a1fe131d72534a00817d4526b849fabdc568712 (diff) | |
Moving 2-SAT to graph section.
| -rw-r--r-- | graph/graph.tex | 8 | ||||
| -rw-r--r-- | other/other.tex | 8 |
2 files changed, 8 insertions, 8 deletions
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} diff --git a/other/other.tex b/other/other.tex index 66a65c5..0b1922a 100644 --- a/other/other.tex +++ b/other/other.tex @@ -1,13 +1,5 @@ \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} - \subsection{Zeileneingabe} \lstinputlisting{other/split.cpp} |
