From 1db14f605259b1e38372fa815ec4076ef3710518 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 23 Dec 2011 21:20:30 +0100 Subject: [PATCH] Prevody: Korektury po nedavnem prepisu --- 8-prevody/8-prevody.tex | 164 ++++++++++++++++++++++++---------------- 1 file changed, 97 insertions(+), 67 deletions(-) diff --git a/8-prevody/8-prevody.tex b/8-prevody/8-prevody.tex index d59df9a..e4e33e9 100644 --- a/8-prevody/8-prevody.tex +++ b/8-prevody/8-prevody.tex @@ -11,9 +11,9 @@ s~polynomi polynomialita docela dobøe vystihuje praktickou pou¾itelnost algoritmu.% \foot{Jistì vás napadne spousta protipøíkladù, jako tøeba algoritmus se slo¾itostí $\O(1.001^n)$, který nejspí¹ je pou¾itelný, aèkoliv není polynomiální, -a~jiný se slo¾itostí $\O(n^{100})$, u~kterého je tomu naopak. V¹ak jsme -øíkali, ¾e nám jde o~první pøiblí¾ení, které navíc u~vìt¹iny problémù -funguje pøekvapivì dobøe.} +a~jiný se slo¾itostí $\O(n^{100})$, u~kterého je tomu naopak. Ukazuje se, +¾e tyto pøípady jsou velmi øídké, tak¾e u~vìt¹iny problémù ná¹ zjednodu¹ený +pohled funguje pøekvapivì dobøe.} Existují tedy polynomiální algoritmy pro v¹echny úlohy? Zajisté ne, jsou dokonce i takové úlohy, je¾ ¾ádným algoritmem vyøe¹it nelze. @@ -22,7 +22,7 @@ pro kter dokázat, ¾e neexistuje). Takové úlohy jsou pøekvapivì èasté, proto se na této pøedná¹ce podíváme na nìkolik typických pøíkladù. -Navíc uvidíme, ¾e aèkoliv tyto úlohy neumíme efektivnì øe¹it, lze mezi +Navíc uvidíme, ¾e aèkoliv tyto úlohy neumíme efektivnì øe¹it, jde mezi nimi nalézt zajímavé vztahy a pomocí tìchto vztahù obtí¾nost problémù vzájemnì porovnávat. Z~tìchto úvah vyrùstá i skuteèná teorie slo¾itosti se svými hierarchiemi slo¾itostních tøíd. Mù¾ete tedy následující kapitolu @@ -42,15 +42,18 @@ nul a jedni mno¾inu $A\subseteq \{0,1\}^*$ vstupù, na nì¾ je odpovìï~1. Tento pøístup mají rádi v~teorii automatù.} -\s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$ (respektive nìjaké -jejich kódování øetìzci bitù). Existuje v $G$ párování, které obsahuje alespoò $k$ -hran? (Také bychom se mohli ptát, zda existuje párování o~právì~$k$ hranách, -co¾ je toté¾, nebo» pøebyteèné hrany mù¾eme prostì odstranit.) +\s{Pøíklad problému:} {\I Bipartitní párování} -- je dán bipartitní graf +a èíslo $k \in {\bb N}$. Zapí¹eme je pomocí øetìzce bitù: graf tøeba maticí +sousednosti, èíslo dvojkovì (detaily kódování budeme nadále vynechávat). Máme +odpovìdìt, zda v~zadaném grafu existuje párování, které obsahuje alespoò $k$ +hran. -\s{Odboèka:} Ve~vìt¹inì pøípadù bychom chtìli nejen zjistit, jestli takové -párování existuje, ale také nìjaké konkrétní najít. Obvykle ale bývá snadné -pomocí rozhodovací verze problému hledaný objekt sestrojit. Uka¾me si, jak -to udìlat u~párování. +(Otázka, zda existuje párování o~právì~$k$ hranách, je ekvivalentní, +proto¾e mù¾eme libovolnou hranu z~párování vypustit a bude to stále párování.) + +\s{Odboèka:} Èasto nás samozøejmì nejen zajímá, zda párování existuje, ale také +chceme nìjaké konkrétní najít. I~to jde pomocí rozhodovací verze problému snadno +zaøídit. Podobný postup funguje pro mnoho dal¹ích problémù. Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu @@ -65,7 +68,7 @@ do hledan mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.% \foot{Zde se skrývá hlavní dùvod, proè informatici mají tak rádi polynomiální algoritmy. Tøída v¹ech polynomù je toti¾ nejmen¹í tøídou funkcí, která obsahuje -v¹echny \uv{základní} funkce (konstanty, $n$, $n^2$) a je uzavøená na sèítání, +v¹echny \uv{základní} funkce (konstanty, $n$, $n^2$, \dots) a je uzavøená na sèítání, odèítání, násobení i skládání funkcí.} \s{Zpìt z~odboèky:} Jak párovací problém vyøe¹it? Vìrni matfyzáckým vtipùm, @@ -79,11 +82,12 @@ Takov \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, øíkáme, ¾e $A$ lze {\I pøevést} (neboli {\I redukovat}) na~$B$ (pí¹eme $A \rightarrow B$) právì tehdy, -kdy¾ existuje funkce $f: \{0,1\}^* \rightarrow \{0,1\}^*$, spoèitatelná v~polynomiálním -èase, taková, ¾e pro $\forall x\in \{0,1\}^*: A(x) = B(f(x))$. +kdy¾ existuje funkce $f: \{0,1\}^* \rightarrow \{0,1\}^*$ taková, ¾e pro v¹echna +$x\in \{0,1\}^*$ platí $A(x) = B(f(x))$, a~navíc lze funkci~$f$ spoèítat v~polynomiálním +èase. \s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký -jako problém~$A$. Tím myslíme, ¾e kdykoliv umíme øe¹it~$B$, je vyøe¹it~$A$ nejvý¹e +jako problém~$A$. Tím myslíme, ¾e kdykoliv umíme vyøe¹it~$B$, je vyøe¹it~$A$ nejvý¹e polynomiálnì obtí¾nìj¹í. Speciálnì platí: \s{Lemma:} Pokud $A\rightarrow B$ a $B$~lze øe¹it v~polynomiálním èase, @@ -94,13 +98,17 @@ Nech délka vstupu tohoto problému a $k$~konstanta. Mìjme dále funkci~$f$ pøevádìjící $A$ na~$B$ v~èase $\O(a^\ell)$ pro vstup délky~$a$. Chceme-li nyní spoèítat $A(x)$ pro nìjaký vstup~$x$ délky~$a$, spoèítáme nejprve $f(x)$. To bude trvat -$\O(a^\ell)$ a vyjde výstup délky takté¾ $\O(a^\ell)$ -- del¹í v~daném èase -funkce~$f$ nestihne vypsat. Tento vstup pak pøedáme algoritmu pro problém~$B$, -který nad ním stráví èas $\O((a^\ell)^k) = \O(a^{k\ell})$, co¾ je polynom -v~délce pùvodního vstupu. +$\O(a^\ell)$ a vyjde výstup délky takté¾ $\O(a^\ell)$ -- del¹í bychom v~daném èase +ani nestihli vypsat. Tento vstup pak pøedáme algoritmu pro problém~$B$, +který nad ním stráví èas $\O((a^\ell)^k) = \O(a^{k\ell})$. Celkový èas výpoètu +tedy èiní $\O(a^\ell + a^{k\ell})$, co¾ je polynom v~délce pùvodního vstupu. \qed -\s{Pozorování:} O~relaci pøevoditelnosti na mno¾inì v¹ech problémù platí: +Relace pøevoditelnosti jistým zpùsobem porovnává problémy podle obtí¾nosti. +Nabízí se pøedstava, ¾e se jedná o~uspoøádání na mno¾inì v¹ech problémù. Je tomu +doopravdy tak? + +\s{Pozorování:} O~relaci \uv{$\rightarrow$} platí: \itemize\ibull \:{\I Je reflexivní} ($A\rightarrow A$) -- úlohu mù¾eme pøevést na tuté¾ identickým zobrazením. \:{\I Je tranzitivní} ($A\rightarrow B \land B\rightarrow C \Rightarrow A\rightarrow C$) -- @@ -109,28 +117,28 @@ p vyèíslitelná funkce, jak u¾ jsme zpozorovali v~dùkazu pøedchozího lemmatu. \:{\I Není antisymetrická} -- napøíklad problémy \uv{na vstupu je øetìzec zaèínající nulou} a \uv{na vstupu je øetìzec konèící nulou} lze mezi sebou pøevádìt obìma smìry. -\:Existují {\I navzájem nepøevoditelné problémy} -- tøeba pro problémy $A(x)=0$ a $B(y)=1$ -nemù¾e existovat pøevod ani jedním smìrem. +\:Existují {\I navzájem nepøevoditelné problémy} -- tøeba mezi problémy \uv{na ka¾dý vstup +odpovìz~0} a \uv{na ka¾dý vstup odpovìz~1} nemù¾e existovat pøevod ani jedním smìrem. \endlist \>Relacím, které jsou reflexivní a tranzitivní, ale obecnì nesplòují antisymetrii, se øíká {\I kvaziuspoøádání}. Pøevoditelnost je tedy èásteèné kvaziuspoøádání na mno¾inì v¹ech problémù.\foot{Kdybychom z~nìj chtìli vyrobit opravdové (by» èásteèné) uspoøádání, mohli bychom definovat ekvivalenci $A\sim B \equiv A\rightarrow B \land B\rightarrow A$ -a relaci pøevoditelnosti zavést jen na tøídách této ekvivalence. Taková pøevoditelnosti +a relaci pøevoditelnosti zavést jen na tøídách této ekvivalence. Taková pøevoditelnost by u¾ byla slabì antisymetrická. To je v~matematice dost bì¾ný trik, øíká se mu {\I faktorizace} kvaziuspoøádání.} Nyní se ji¾ podíváme na pøíklady nìkolika problémù, které se obecnì pova¾ují za tì¾ké. Uvidíme, ¾e ka¾dý z~nich je mo¾né pøevést na v¹echny ostatní, tak¾e z~na¹eho \uv{polynomiálního} pohledu jsou stejnì obtí¾né. -\prob{SAT -- Splnitelnost logických formulí v~CNF} +\prob{SAT -- splnitelnost (satisfiability) logických formulí v~CNF} -Splnitelnost (satisfiability) spoèívá v~tom, ¾e dostaneme logickou formuli -s~promìnnými a logickými spojkami a ptáme se, zda lze za promìnné dosadit -0 a~1 tak, aby formule dala výsledek 1 (byla splnìna). +Mìjme nìjakou logickou formuli s~promìnnými a logickými spojkami. Zajímá +nás, je-li tato formule {\I splnitelná,} tedy zda lze za promìnné dosadit +0 a~1 tak, aby formule dala výsledek~1 (byla {\I splnìna}). -Zamìøíme se na speciální formu zadání formulí, takzvanou {\I konjunktivní normální +Zamìøíme se na formule ve~speciálním tvaru, v~takzvané {\I konjunktivní normální formu (CNF):} \itemize\ibull @@ -138,13 +146,17 @@ formu (CNF):} \: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 -\>Formule mají tedy tvar -$$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ \inp Formule $\psi$ v konjunktivní normální formì. \outp Existuje-li dosazení 0 a~1 za promìnné tak, aby $\psi(\ldots) = 1$. +\s{Pøíklad:} Formule $(x\lor y\lor z) \land (\lnot x \lor y \lor z) \land (x \lor \lnot y \lor z) \land (x \lor y \lor \lnot z)$ +je splnitelná, staèí nastavit napøíklad $x=y=z=1$ (jaká jsou ostatní splòující +ohodnocení?). Naproti tomu formule $(x\lor y) \land (x\lor \lnot y) +\land \lnot x$ splnitelná není, co¾ snadno ovìøíme tøeba vyzkou¹ením v¹ech +ètyø mo¾ných ohodnocení. + \s{Poznámka:} Co kdybychom chtìli zjistit, zda je splnitelná nìjaká formule, která není v~CNF? V~logice se dokazuje, ¾e ke~ka¾dé formuli lze najít ekvivalentní formuli v~CNF, ale pøi tom se bohu¾el formule mù¾e a¾ exponenciálnì prodlou¾it. @@ -152,10 +164,12 @@ Pozd která je splnitelná právì tehdy, kdy¾ je $\chi$ splnitelná. Formule $\chi'$ pøitom bude dlouhá $\O(\vert\chi\vert)$, ale budou v~ní nìjaké nové promìnné. -\prob{3-SAT -- Splnitelnost formulí s~krátkými klauzulemi} +\prob{3-SAT -- splnitelnost formulí s~krátkými klauzulemi} + +Pro SAT zatím není známý ¾ádný polynomiální algoritmus. Co kdybychom zkusili +problém trochu zjednodu¹it a uva¾ovat pouze formule ve~speciálním tvaru? -Uva¾ujme variantu SATu, ve~které mno¾inu mo¾ných formulí je¹tì omezíme. -Povolíme na vstupu pouze takové formule v~CNF, jejich¾ ka¾dá klauzule obsahuje +Povolíme tedy na vstupu pouze takové formule v~CNF, jejich¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály. Uká¾eme, ¾e tento problém je stejnì tì¾ký jako pùvodní SAT. \s{Pøevod 3-SATu na SAT:} @@ -167,27 +181,30 @@ Nech Mù¾eme ji zapsat ve~tvaru $(\alpha\lor\beta)$, kde $\alpha$ obsahuje 2~literály a $\beta$ $k-2$ literálù. Poøídíme si novou promìnnou~$x$ a klauzuli nahradíme dvìma novými $(\alpha\lor x)$ a $(\beta\lor\lnot x)$. První z~nich obsahuje 3~literály, -tedy je dobrá. Druhá má $k-1$ literálù, tak¾e sice mù¾e být ¹patná, ale aspoò je +tedy je dobrá. Druhá má $k-1$ literálù, tak¾e mù¾e být stále ¹patná, ale aspoò je krat¹í, tak¾e mù¾eme postup opakovat. Takto postupnì nahradíme v¹echny ¹patné klauzule dobrými, co¾ bude trvat nejvý¹e -polynomiálnì dlouho: klauzuli délky~$k$ rozbijeme po $k-3$ krocích, ¹patných -klauzulí je jistì polynomiálnì s~délkou formule. Staèí ukázat, ¾e ka¾dý jednotlivý -krok zachovává splnitelnost formule. +polynomiálnì dlouho: klauzuli délky~$k$ rozebereme po $k-3$ krocích, ¹patných +klauzulí je lineárnì s~délkou formule. + +Zbývá ukázat, ¾e nová formule je splnitelná právì tehdy, byla-li splnitelná +formule pùvodní. K~tomu staèí ukázat, ¾e ka¾dý jednotlivý krok pøevodu splnitelnost +zachovává. Pokud pùvodní formule byla splnitelná, uva¾me nìjaké splòující ohodnocení promìnných. Uká¾eme, ¾e v¾dy mù¾eme novou promìnnou~$x$ nastavit tak, aby vzniklo splòující ohodnocení nové formule. Víme, ¾e klauzule $(\alpha\lor\beta)$ byla splnìna. Proto v~daném ohodnocení: \itemize\ibull -\:Buïto $\alpha=1$. Pak polo¾íme $x=0$, tak¾e $(\alpha\lor x)$ bude splnìno díky~$\alpha$ +\:Buïto $\alpha=1$. Pak polo¾íme $x=0$, tak¾e $(\alpha\lor x)$ bude splnìna díky~$\alpha$ a $(\beta\lor\lnot x)$ díky~$x$. -\:Anebo $\alpha=0$. Pak polo¾íme $x=1$, tak¾e $(\alpha\lor x)$ bude splnìno díky~$x$, +\:Anebo $\alpha=0$, a~tedy $\beta=1$. Pak polo¾íme $x=1$, èím¾ bude $(\alpha\lor x)$ splnìna díky~$x$, zatímco $(\beta\lor\lnot x)$ díky~$\beta$. \endlist -\>Splnìnost ostatních klauzulí na¹e transformace nijak neovlivnila. +\>Ostatní klauzule budou stále splnìny. -A~naopak: pokud dostaneme splòující ohodnocení nové formule, umíme z~nìj získat +V~opaèném smìru: pokud dostaneme splòující ohodnocení nové formule, umíme z~nìj získat splòující ohodnocení formule pùvodní. Uká¾eme, ¾e staèí zapomenout promìnnou~$x$. V¹echny klauzule, kterých se na¹e transformace netýká, jsou nadále splnìné. Co klauzule $(\alpha\lor\beta)$? @@ -200,16 +217,16 @@ Co klauzule $(\alpha\lor\beta)$? \>Tím je pøevod hotov, SAT a 3-SAT jsou tedy ekvivalentní. -\prob{NzMna -- Nezávislá mno¾ina vrcholù v~grafu} +\prob{NzMna -- nezávislá mno¾ina vrcholù v~grafu} \s{Definice:} Mno¾ina vrcholù grafu je {\I nezávislá,} pokud ¾ádné dva -vrcholy le¾ící v~této mno¾inì nejsou spojeny hranou. (Jinými slovy pokud -tato mno¾ina indukuje podgraf bez hran.) +vrcholy le¾ící v~této mno¾inì nejsou spojeny hranou. (Jinými slovy nezávislá +mno¾ina indukuje podgraf bez hran.) \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{0.7in} \>Na samotnou existenci nezávislé mno¾iny se nemá smysl ptát -- prázdná mno¾ina -èi libovolný jeden vrchol jsou v¾dy nezávislé. Zajímavé ale je, jestli má graf +èi libovolný jeden vrchol jsou v¾dy nezávislé. Zajímavé ale je, jestli graf obsahuje dostateènì velkou nezávislou mno¾inu. \inp Neorientovaný graf $G$ a èíslo $k \in {\bb N}$. @@ -217,19 +234,21 @@ dostate \outp Zda existuje nezávislá mno¾ina $A \subseteq V(G)$ velikosti alespoò~$k$. \s{Pøevod 3-SAT $\rightarrow$ NzMna:} +Dostaneme formuli a máme vytvoøit graf, v~nìm¾ se bude nezávislá mno¾ina +urèené velikosti nacházet právì tehdy, je-li formule splnitelná. My¹lenka pøevodu bude jednoduchá: z~ka¾dé klauzule budeme chtít vybrat jeden literál, jeho¾ nastavením klauzuli splníme. Samozøejmì si musíme dát pozor, abychom v~rùzných klauzulích nevybírali konfliktnì, tj. jednou~$x$ a podruhé~$\lnot x$. Jak to pøesnì zaøídit: -pro ka¾dou z~$k$~klauzulí zadané formule vytvoøíme trojúhelník a ka¾dému z~jeho -vrcholù pøiøadíme jeden z~literálù pøíslu¹né klauzule. (Pokud by klauzule obsahovala -ménì literálù, prostì nìkteré vrcholy trojúhelníka vynecháme.) Navíc spojíme -hranami v¹echny dvojice konfliktních literálù ($x$ a~$\lnot x$). +pro ka¾dou z~$k$~klauzulí zadané formule vytvoøíme trojúhelník a jeho vrcholùm +pøiøadíme literály klauzule. (Pokud by klauzule obsahovala ménì literálù, +prostì nìkteré vrcholy trojúhelníka sma¾eme.) Navíc spojíme hranami v¹echny +dvojice konfliktních literálù ($x$ a~$\lnot x$) z~rùzných trojúhelníkù. V~tomto grafu se budeme ptát po nezávislé mno¾inì velikosti alespoò~$k$. Jeliko¾ z~ka¾dého trojúhelníka mù¾eme do~nezávislé mno¾iny vybrat nejvý¹e jeden vrchol, -jediná mo¾nost, jak splnit po¾adovanou velikost, je vybrat z~ka¾dého právì jeden +jediná mo¾nost, jak dosáhnout po¾adované velikosti, je vybrat z~ka¾dého právì jeden vrchol. Uká¾eme, ¾e taková nezávislá mno¾ina existuje právì tehdy, je-li formule splnitelná. Máme-li splòující ohodnocení formule, mù¾eme z~ka¾dé klauzule vybrat jeden splnìný @@ -240,17 +259,21 @@ nem A~opaènì: Kdykoliv dostaneme nezávislou mno¾inu velikosti~$k$, vybereme literály odpovídající vybraným vrcholùm a pøíslu¹né promìnné nastavíme tak, abychom tyto literály splnili. Díky hranám mezi konfliktními literály se nikdy nestane, ¾e bychom -potøebovali souèasnì splnit literál a jeho negaci. Zbývající promìnné nastavíme +potøebovali promìnnou nastavit souèasnì na~0 a na~1. Zbývající promìnné ohodnotíme libovolnì. Jeliko¾ jsme v~ka¾dé klauzuli splnili alespoò jeden literál, jsou splnìny v¹echny klauzule, a~tedy i celá formule. Pøevod je tedy korektní, zbývá rozmyslet, ¾e bì¾í v~polynomiálním èase: Poèet vrcholù grafu odpovídá poètu literálù ve formuli, poèet hran je maximálnì -kvadratický, tak¾e celý pøevod je polynomiální. +kvadratický. Ka¾dý vrchol i hranu pøitom sestrojíme v~polynomiálním èase, tak¾e +celý pøevod je také polynomiální. \figure{nezmna_graf.eps}{Graf pro formuli $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p)$}{3in} \s{Pøevod NzMna $\rightarrow$ SAT:} +Dostaneme graf a èíslo~$k$, chceme vytvoøit formuli, která je splnitelná právì +tehdy, pokud se v~grafu nachází nezávislá mno¾ina o~alespoò~$k$ vrcholech. +Tuto formuli sestrojíme následovnì. Vrcholy grafu oèíslujeme od~1 do~$n$ a poøídíme si pro nì promìnné $v_1, \ldots, v_n$, které budou indikovat, zda byl pøíslu¹ný vrchol vybrán do nezávislé mno¾iny @@ -260,26 +283,30 @@ Aby mno $(\lnot v_i \lor \lnot v_j)$. Je¹tì potøebujeme zkontrolovat, ¾e mno¾ina je dostateènì velká. To neumíme provést -pøímo, ale pou¾ijeme lest: vyrobíme matici $X$ tvaru~$k\times n$, která bude popisovat +pøímo, ale pou¾ijeme lest: vyrobíme matici promìnných~$X$ tvaru~$k\times n$, která bude popisovat oèíslování vrcholù nezávislé mno¾iny èísly od~1 do~$k$. Konkrétnì $x_{ij}$ bude øíkat, ¾e v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$j$. K~tomu potøebujeme zaøídit: \itemize\ibull \:Aby v~ka¾dém sloupci byla nejvý¹e jedna jednièka. Na to si poøídíme klauzule - $(x_{i,j} \Rightarrow \lnot x_{i',j})$ pro $1\le i 3$ literálech, nahradíme její výskyty novými promìnnými $x_1, \ldots , x_k$ @@ -322,7 +351,8 @@ M (tedy ¾e ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude -vyskytovat jak pozitivnì, tak negativnì. +vyskytovat jak pozitivnì, tak negativnì (opìt pøipomínáme, ¾e $a\Rightarrow b$ +je jen zkratka za $\lnot a\lor b$). \prob{3D-párování} @@ -330,7 +360,7 @@ vyskytovat jak pozitivn mno¾ina~$T$ kompatibilních trojic (tìch, kteøí se spolu snesou), tedy $T \subseteq K\times H\times Z$. -\outp Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která v~ní¾ se ka¾dý +\outp Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, v~ní¾ se ka¾dý prvek mno¾in $K$, $H$ a~$Z$ vyskytuje právì jednou. \figure{3d_parovani.eps}{Ukázka 3D-párování}{3in} -- 2.39.2