diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/graph.tex | 8 |
1 files changed, 8 insertions, 0 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} |