SAT-Kodierung: Independent Set

Def: Graph G = (V, E), Menge M $ \subseteq$ V heißt unabhängig, falls $ \forall$x, y $ \in$ M : xy $ \notin$E.

Entscheidungsproblem:

Optimierungsproblem:



2009-06-22