IB107 úkol 3, příklad 2 Odevzdání: 9. 12. 2022, 23:59
Jméno: Nesmáčivá Plotice UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [3 body] Omezenou soustavou rovnic nazveme soustavu lineárních rovnic tvaru
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
...
am1x1 + am2x2 + . . . + amnxn = bm
kde m, n > 0 a všechny lineární koeficienty a11, a12, . . . , amn a absolutní členy b1, b2, . . . , bm jsou nezáporná
celá čísla. Uvažme problém rozhodnout, zda má omezená soustava rovnic řešení x1, x2, . . . , xn ∈
{0, 1}, tedy problém
OSR = { S | S je omezená soustava rovnic, která má řešení využívající pouze hodnot {0, 1}}.
Dokažte, že problém OSR je NP-těžký. (K důkazu můžete využít znalost NP-úplných problémů z přednášky.
Pokud budete chtít využít NP-těžkost nějakého jiného problému, tak ji také dokažte.)
V důkazu ukážeme, že NP-úplný problém
VERTEX-COVER = { G, k | G je graf s vrcholovýmm pokrytím obsahujícím právě k vrcholů}
lze polynomiálně zredukovat na OSR, z čehož ihned plyne, že OSR je NP-těžký.
Redukci VERTEX-COVER ≤p OSR lze realizovat například redukční funkcí f popsanou vztahem
f(x) =



0x = 1 pokud x není tvaru G, k , kde G je neorientovaný graf a k ∈ N,
S pokud x = G, k pro nějaký neorientovaný graf G a k ∈ N,
kde S je omezená soustava rovnic definovaná následovně. Předpokládejme, že G má n vrcholů a m
hran. Vrcholům přiřadíme proměnné x1, . . . , xn a hranám proměnné y1, . . . , ym. Proměnná xi značí,
zda je i-tý vrchol ve vrcholovém pokrytí. Soustava bude mít m + 1 rovnic. Intuitivní význam první
rovnice
x1 + x2 + . . . + xn = k
je, že pokrytí má obsahovat právě k vrcholů. Dále bude soustava obsahovat jednu rovnici pro každou
z m hran. Pokud l-tá hrana spojuje i-tý a j-tý vrchol, pak odpovídající rovnice
xi + xj + yl = 2
říká, že alespoň jeden z těchto vrcholů je v pokrytí. Soustava obsahuje m + 1 rovnic, m + n proměnných
a konstanty 0, 1, 2, k. Funkci f lze jistě počítat deterministickým Turingovým strojem v
polynomiálním čase.
Zbývá dokázat ekvivalenci x ∈ VERTEX-COVER ⇐⇒ f(x) ∈ OSR. Pokud x není tvaru G, k ,
kde G je neorientovaný graf a k ∈ N, vrací f(x) kód jednoduché soustavy, která nemá řešení. V
tomto případě ekvivalence platí, protože x ∈ VERTEX-COVER a f(x) ∈ OSR. V dalším budeme
předpokládat, že x = G, k pro nějaký neorientovaný graf G a k ∈ N a tedy f(x) = S .
“=⇒” Nechť G má vrcholové pokrytí o k vrcholech. Řešení soustavy S odvodíme následovně.
– Je-li i-tý vrchol grafu G v uvažovaném prokrytí, pak xi = 1, jinak xi = 0. Takové
ohodnocení proměnných je zjevně řešením rovnice x1 + x2 + . . . + xn = k.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 3, příklad 2 Odevzdání: 9. 12. 2022, 23:59
Jméno: Nesmáčivá Plotice UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
– Pro l-tou hranu spojující i-tý a j-tý vrchol grafu G položíme yl = 2 − (xi + xj). Jelikož
uvažované vrcholové pokrytí obsahuje alespoň jeden z těchto vrcholů, platí 1 ≤ xi+xj ≤ 2
a proto 0 ≤ yl ≤ 1.
Snadno vidíme, že toto ohodnocení proměnných je vskutku řešením soustavy S.
“⇐=” Předpokládejme, že S má řešení x1, . . . , xn, y1, . . . , ym ∈ {0, 1} a uvažme množinu vrcholů, pro
které má odpovídající proměnná hodnotu 1. První rovnice říká, že těchto vrcholů je právě k.
Rovnice pro každou hranu pak říká, že alespoň jeden z jejích vrcholů je v této množině. Tedy
tato množina tvoří vrcholové pokrytí obsahující právě k vrcholů.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.