8.9 Řekneme, že podmnožina vrcholů neorientovaného grafu G je nezávislá, pokud žádná dvojice vrcholů z této podmnožiny není spojená hranou. Ukažte, že problém
INDSET = {{G, k) | G je graf s podmnožinou alespoň k nezávislých vrcholů}
jeNP-úplný.
Aš^s-tT  „    j. MP-fe^ y/ sj{y foch?-. jL^^F
^c^; ^yéi ^ykL^-\[^\\^Q
s^^^jCi   Opisy <j>-í^K.^
5i^^É^
far   (*,^ <?
r
míro
8.10 Ukažte, že problém
DOUBLESAT = {(ip) \ ip je výroková formule splněná alespoň dvěma různými přiřazeními} je NP-úplný.
-  H M (l
I /
7
2 * Z
4t. vj^ty
míro
8.11 Ukažte, že problém
HALFCLIQUE = {(G) \ G je graf [m/21 -klikou, kde m je počet vrcholů v G} je NP-úplný.
WC
WC
5
i\c   Jl. fe^ý
c
ív/
o
«s wsti^ ^wsy m^t-i
8.10 Ukažte, že prt DOUBLESA je NP-úplný.
st
y—i \
s_
ayý>
Jit i