Drobna vylepseni prevodu nezavisle mnoziny na SAT.

[ads2.git] / 10-prevody / 10-prevody.tex

diff --git a/10-prevody/10-prevody.tex b/10-prevody/10-prevody.tex
index 9e638dcb0d5ddd8ab1b1126ea5bfb3888d8ae9af..9e55361c13f39b9f0d73ee38aa4e9add42fce29b 100644 (file)
--- a/10-prevody/10-prevody.tex
+++ b/10-prevody/10-prevody.tex
@@ -64,7 +64,7 @@ v~p
 \>Splnitelnost logických formulí, tj. dosazení \<true> èi \<false> za promìnné v logické formuli tak, aby formule dala výsledek \<true>.
 
 \>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF).
-$$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ 
+$$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
 
 \>{\I Vstup:} Formule $\varphi$ v konjunktivní normální formì.
 
@@ -76,7 +76,7 @@ $$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\l
 \:{\I formule} je zadána pomocí {\I klauzulí} oddìlených $\land$,
 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
-\endlist 
+\endlist
 
 \>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
 
@@ -124,10 +124,10 @@ takov
 \s{Poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina. Proto je potøeba zadat i minimální velikost hledané mno¾iny.
 
 \>Uká¾eme, jak na~tento probém pøevést 3-SAT.
- 
+
 \s{Pøevod:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$.
 
-\s{Pøíklad:} 
+\s{Pøíklad:}
 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
 
 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} hrany, tj. $x$ a $\lnot x$.
@@ -163,20 +163,24 @@ M
   x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
 \endlist
 
-\figure{matice.eps}{Výsledná matice}{3in}
+\s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny.
+Nech» jsou vrcholy grafu oèíslované zleva a ze zhora. Hledáme nezávislou mno¾inu velikosti $2$.
+Matice pak bude vypadat následovnì:
+$$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$
+\s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním øádku a v prvním sloupci bude $1$. Jako druhý ($k$-tý) vrchol mno¾iny bude vybrán vrchol $v_4$, proto na druhém ($k$-tém) øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$.
 
 \h{4. problém: Klika}
 
 \>{\I Vstup:} Graf $G, k \in N$.
 
 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
-\figure{klika.eps}{Pøíklad kliky}{3in}
+\figure{klika.eps}{Pøíklad kliky}{2in}
 
 \s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ hledání nezávislé mno¾iny.
 
 \s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~\uv{invertovaném} grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu.
 
-\figure{doplnek_nm.eps}{Prohození hran a nehran}{3in}
+\figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
 
 \h{5. problém: 3D párování (3D matching)}
 
@@ -214,7 +218,7 @@ $$
 (x_k \Rightarrow x_1).
 $$
 
-Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu. Navíc si lze v¹imnout, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát. 
+Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu. Navíc si lze v¹imnout, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát.
 
 \s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
 \figure{prevody.eps}{Pøevody mezi problémy}{3in}