From 14cb8236d25b6858226fa755890ff53931198276 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 30 Jan 2007 16:50:53 +0100 Subject: [PATCH] Sjednoceni jmena U-F problemu. --- 9-decomp/9-decomp.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index e36a55b..467a046 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -9,7 +9,7 @@ na~my které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním èase. -\h{Union-Find problem} +\h{Union-Find Problem} \s{Problém:} Udr¾ování tøíd ekvivalence: na~poèátku máme $N$ jednoprvkových ekvivalenèních tøíd, provádíme operace \ (zji¹tìní, zda dva prvky jsou ekvivalentní) a \ @@ -61,7 +61,7 @@ p \h{Union-Find s~pøedem známými Uniony} -Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe +Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí? Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních @@ -223,7 +223,7 @@ algoritmus, kter \proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed -\s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením +\s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik}, nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù a pøebarvovací struktury na~hrany mezi clustery. -- 2.39.2